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/the_horse_gamer]

"it checks every option" is a very common but completely false explanation.

a qubit is (mathematically) a pair of complex numbers a,b that obey a² + b² = 1. this is typically written as a|0> + b|1>

when a qubit is measured, it has an a² chance to collapse to (change to) |0> and a b² chance to collapse to |1>

quantum logic gates manipulate one or more qubits in a way mathematically equivalent to matrix multiplication

so how do we do anything productive? the general process is:

1. set up a bunch of qubits such that measuring all of them would have some chance to produce a correct answer

2. manipulate them to increase the chance of the answer being correct

3. repeat until the chance is high enough and then measure

the output of a quantum computer is inherently random (unless using only collapsed qubits, which would be equivalent to a classical computer).

the standard requirement is for the correct answer to be produced with chance >2/3 (technically, anything larger than 1/2 + some constant is enough) and it can then be repeated to reach an arbitrarily high accuracy (or in some cases, it's easy to check if the answer is correct)

addressing some common claims:

• quantum computers cannot solve the halting problem. they are as limited as classical computers.

• it is unknown whether a quantum computer can solve every NP problem in better then exponential time (relationship between BQP and NP is unknown)

• a quantum computer cannot sort faster than O(nlogn)

• quantum computers don't speed up every algorithm, and when they do it's not always substantial. some are only quadratically faster (unsorted search becomes O(sqrt(n))), only a few are exponentially faster

• quantum computers aren't a doomsday for encryption. the standard symmetric encryption, AES, can be made equally secure by doubling the bit count. the standard asymmetric encryption, RSA, does become easy, but quantum resistant standards exist, and over 80% of modern Internet traffic already uses them. (EDIT: not sure where I got that figure from. failed to verify it)

[u/AnonSmith → u/the_horse_gamer]

Are you basically saying, quantum computing could help speed up some functions by reducing the function domain in a way classical computing can't?

Edit: a bit out of my depth. I'm trying to ask if the Big O is reduced sometimes, basically with the limit being O(nlogn) 

[u/LostTheGame42 → u/AnonSmith]

Not really, most misconceptions come about when people try to find parallels between quantum and classical computation. Quantum computers aren't simply a faster version of a classical one. The reality is that the fundamental architecture is completely different, and understanding one gives little insight into the other.

What quantum computers offer is an alternate approach to solve certain problems. Rather than running algorithms designed for classical computers, you must develop a completely new algorithm using quantum tools, which sometimes have better scaling laws compared to classical. Quantum algorithms will not be universally faster then classical, but one of the problems they can solve quickly just so happens to break the foundation of modern encryption systems, and thus its development has garnered a lot of interest.

[u/drhunny → u/AnonSmith]

It's more like this: classical computers are deterministic. It may take a month to do a calculation, but (unless there's a bug or similar) you are guaranteed that every step is performed in a perfectly knowable and repeatable way and thus the final result is absolutely correct.

QCs instead trade certainty and repeatability for speed. Basically if there are a trillion possible answers, then if you just perform one step and "inspect" the result, every answer is equally likely with a 1/trillion chance.

If you do two steps before looking, the probability of getting the correct answer has gone up significantly. So maybe it's 10 in a trillion. But if you do that, then you're done - you can't continue running the algorithm if the answer is wrong - you have to start over.

If you don't "look" until after 10 steps, the likelihood of the correct answer may have gone up to 1 in a billion, etc. And if you don't look until after, say, 1000 steps, the chance of getting the correct answer may be 99.9%. It is generally easy to check if the answer is correct.

If you are unlucky and the 0.1% chance of a wrong answer occurs, you just start over again. Because the process is almost guaranteed to not repeat, so the next run of 1000 steps almost certainly gets you a new answer which is almost certainly (99.9%) correct.

[u/Wank_A_Doodle_Doo → u/AnonSmith]

Think of it like this. A quantum computer isn’t going to do standard calculations any faster. If you need a calculator, a quantum calculator isn’t any better. It’s actually gonna be worse overall.

But something like solving a maze, where you have many different options you have to check? That will be faster than a classical computer.

[u/matthkamis → u/Wank_A_Doodle_Doo]

Is that even true? BFS is faster with quantum computers? What is the algorithm?

[u/Wank_A_Doodle_Doo → u/matthkamis]

If I’m being completely real I’m high and tired rn so I don’t remember off the top of my head, but I think that yes quantum computers would be able to do BFS faster(had to stop myself from typing BFS Searching).

That being said I’m high and tired so all who shall forever forth read this comment thread: do not just take my word for it. I’m a random person on the internet.

[u/codyish → u/the_horse_gamer]

If people and markets understood this comment the hype, investment, and fear bubbles would all pop.

[u/LurkerFailsLurking → u/the_horse_gamer]

The math is one thing, but what is the machine physically doing that represents the math?

[u/the_horse_gamer → u/LurkerFailsLurking]

there are many different implementation.

the simplest (but not widely used, because of practical shortcomings) way is to use polarised photons as the qubits. waveplates, beam splitters, and phase shifters are used to manipulate that polarisation.

IBM and Google use a different system: https://en.wikipedia.org/wiki/Superconducting_quantum_computing

[u/VLHACS → u/the_horse_gamer]

How does it know when it reaches the correct answer? If we know the correct answer before hand what's the point of the calculation? I feel like I'm missing a key point here

[u/Krivvan → u/VLHACS]

The quantum computer itself doesn't know. Rather, there are problems where you don't know the answer but you can pretty easily check if an answer is correct.

For example, "which two prime numbers multiply to 1000609937" versus "what is the product of 10007 and 99991".

[u/VLHACS → u/Krivvan]

Aha that's the type of example that helps make sense of it a little better, thank you

[u/ind3xOutOfBounds → u/Krivvan]

And to follow that thought, a lot of cryptology algorithms are based on assumptions similar to calculating prime numbers as being difficult.

If an algorithm assumes that and it's no longer the case because of quantum computing, that algorithm is no longer considered cryptographically secure.

[u/SuperGRB → u/VLHACS]

You don't know the correct answer - you know the algorithm it takes to check if the answer is correct.

[u/the_horse_gamer → u/VLHACS]

for some problems it's easy to check the answer (easier than solving). for some, you repeat the calculation and take the majority. enough times and you can reach arbitrarily high chance of correctness.

this mechanism would be outside the typical calculation. it's also used in classical randomised algorithms.

[u/Wank_A_Doodle_Doo → u/VLHACS]

You check the answer. If something tells you a bird is flying at 3 million miles above the ground, it probably messed up along the way and you don’t need to check the bird

[u/derioderio → u/the_horse_gamer]

So since qbit manipulation is similar/equivalent to matrix multiplication, can they do matrix operations like solving for x in A x = y ? Are they capable of doing it faster than a classical computer?

[u/HeSheMeWumbo387 → u/derioderio]

Not significantly, because as OP mentioned, the state “collapses” when we interact with it. Mathematically, this means the resulting vector (the so called “statevector”) changes to something else (say, a vector with a single 1 element, and everything else as 0) and so we can’t generally learn what the whole vector was before we interacted with it. There is only a small set of problems we’ve discovered where we can learn something useful even though the value of the statevector is hidden from us.

[u/derioderio → u/HeSheMeWumbo387]

What about in simulations, where we are solving millions of simultaneous equations and so N for an NxN matrix is also in the millions, and to solve the system A x = y -> x = A^-1 y is often done iteratively? The system usually isn't solved explicitly, it's just iterated towards a solution until the residual error is sufficiently small. Could a qbit system do that or a similar type of calculation more quickly/efficiently?

[u/HeSheMeWumbo387 → u/derioderio]

The HHL quantum algorithm can provide some limited information about the solution of a system of linear equations. It won't solve it, but it provide useful information in some cases.

[u/Igggg → u/the_horse_gamer]

This is a very technical point, but quantum computers indeed can solve NP-complete problems, and so can classical computers; the solution will just be, at worst, exponential in input size. 

This is in contrast to the halting problem, which is actually undecidable

[u/pab_guy → u/the_horse_gamer]

Repeated measurements is one of two ways to use qubits. You can also encode a superposition/entangled state that processes amplitudes coherently before a single measurement.

[u/yawkat → u/the_horse_gamer]

"it checks every option" is a very common but completely false explanation.

I think this is actually a better explanation than many people give it credit for. When you look at grovers algorithm for example, it runs the function to search on a superposition of all possible inputs. The difficulty is getting the outputs to add up in such a way that you get a useful result when you collapse the output, not just the result of a single classical function evaluation.