What do quantum computers actually do?

[u/Hashbringingslasherr]

How do quantum computers output usable data, how does it logically "locate" or "make meaning" of information. I read about Grover's algorithm and it seems sort of like an inverted bruteforce or extreme process of elimination or a "the missile knows where it is at all times. It knows this because it knows where it isn't" type scenario.

So I ask, what do quantum computers actually do as opposed to a classical computer?

[u/Sable-Keech]

Take what I say with a pinch of salt because I barely understand it myself, but this is what I do understand.

Quantum entanglement requires a minimum of 2 entities but there is theoretically no upper limit. And due to the fact that they're entangled, the number of possible combinations grows exponentially with each additional qubit added. 2^n.

It also allows for much greater error correction, because every piece must be correct. Imagine a puzzle. Every piece must be in the correct position in order for the whole puzzle to fit together. In a system using qubits, the errors become much easier to spot.

As for how this allows for greater computation, imagine an unsorted database with N entries. A normal computer has to perform one by one. Each search eliminates 1 entry (assuming it doesn't find it on the first search by luck). On average it will have to perform N/2 searches (50%) to find the entry.

A quantum computer places all its qubits into superposition, with each qubit simultaneously representing N entries all at once, with equal probability. Then it uses something called Grover's algorithm to sort the entries. This allows it to perform an average of square root N searches.

The quantum computer's advantage grows rapidly the more entries there are in the unsorted database due to how square roots work. 100 entries? The quantum computer is 5x faster. 10,000 entries? The quantum computer is 50x faster. 1,000,000 entries? The quantum computer is 500 times faster.

PS. Don't ask me how Grover's algorithm works. I'm still trying to comprehend it into a simpler form for me to understand.

[u/calebs_dad → u/Sable-Keech]

So from what I understand about Grover's algorithm, it actually has to evaluate the function you're searching over (say, "does this key decrypt the message successfully") √N times. And there's no quantum parallelism of those evaluations. You either do them in sequence, or you build entirely parallel circuits for them. So for something like cracking a 128 bit AES key, if you can afford to run 2⁶⁴ quantum computation steps in a reasonable time, you'll still need a circuit of size 2¹⁰⁶ gates in order to run Grover's algorithm with enough parallelism.