Quantum Computers. Not like I'm five, but like I'm a software engineer who has a pretty decent understanding of how a classical turing machine works. I can't tell you how many times I've heard someone say "qubits are like bits except they don't have to be just 1 or 0" without providing any coherent explanation of how that's useful. I've also heard that they can try every possible solution to a problem. What I don't understand is how a programmer is supposed to determine the correct solution when their computer is out in some crazy multiverse. I guess what I want is some pseudo code for quantum software.
I had the same "problem" as you. What finally made me feel I sort of cracked it was those videos. The way I think of it now is: They let you do matrix multiplication. The internal state of the computer is the matrix, and the input is a vector, where each element is represented by a qubit. The elements can have any value 0 to 1, but in the output vector of the multiplication, they are collapsed into 0 or 1. You then run it many times to get statistical data on the output to be able to pinpoint the output values more closely.
I don't know if it's accurate (because I never understand anything I read about it) but this is the most concise and clear explanation I've read on this subject to date. Thank you!
It's accurate. QC is just linear algebra with complex numbers, plus probability extended to the complex domain. Why that's useful is something I'm still struggling with as well.
I'd assume it's the speed advantage, but the only problem I can think of that would require that type of exponential speed is cracking hashing algorithms which just seems destructive and counterproductive, like building a digital nuclear bomb - and from my very limited understanding that's a long ways off from being achieved.
I assume there's probably many more complex computational problems outside of my domain that QC can help with. Does anybody know of any?
Aside from Shor's, the other is Grover's algorithm which deals with search in an unstructured database. There are more and more superpolynomial speedups which have been discovered in application of QC. A good enumeration of these is the quantum algorithm zoo.
Grover's algorithm lets you search an unsorted list of four elements with just one "is this thing in the list?" query. Classically, of course, it requires four queries.
More precisely, given f: 2^n -> {0,1} which is guaranteed to hit 1 exactly once, Grover finds the one input which hits 1, and it does so using about 2^{n/2} queries of f; but the constants happen to line up so that when n=2, exactly one query is required.
Many problems require lots of huge matrix multiplications—think simulations of physical systems, i.e. weather systems or molecular interactions, or numerical optimization.
Optimizing matrix multiplication for classical computers is an open research problem, and according to wikipedia there are algorithms with O(n^2.37) running time. Also according to wikipedia, it is not proven that matrix multiplication can't be done in O(n^2).
I think there's no way to understand quantum computing without first understanding some linear algebra, specifically tensor products. How ten 2-dimensional spaces give rise to a 1024-dimensional space, how the Kronecker product of three 2x2 matrices is an 8x8 matrix, and so on. If you're comfortable with that, here's a simple and precise explanation of quantum computing:
1) The state of an n-qubit system is a 2^n dimensional vector of length 1. You can assume that all coordinates are real numbers, because going to complex numbers doesn't give more computational power.
2) You can initialize the vector by taking an n-bit string, interpreting it as a number k, and setting the k'th coordinate of the vector to 1 and the rest to 0.
3) You cannot read from the vector, but exactly once (destroying the vector in the process) you can use it to obtain an n-bit string. For all k, the probability of getting a string that encodes k is the square of the k'th coordinate of the vector. Since the vector has length 1, all probabilities sum to 1.
4) Between the write and the read, you can apply certain orthogonal matrices to the vector. Namely, if we interpret the 2^n dimensional space as a tensor product of n 2-dimensional spaces, then we'll count as an O(1) operation any orthogonal matrix that acts nontrivially on only O(1) of those spaces, and identity on the rest. (This is analogous to classical operations that act nontrivially on only a few bits, and identity on the rest.)
The computational power comes from the huge size of matrices described in (4). For example, if a matrix acts nontrivially on one space in the tensor product and as identity on nine others, then mathematically it's a 1024x1024 matrix consisting of 512 identical 2x2 blocks - but physically it's a simple device acting on one qubit in constant time and not even touching the other nine.
What about some kind of interactive simulation, kind of like playing with a graphing calculator? People tend to relate to things better by tinkering and playing with parameters to observe the impact on results. Analog experimentation is how we learned most Newtonian physics.
Several years ago, I gave a presentation on quantum computing to the Los Angeles Hacker News Meetup. The slides are at https://jimgarrison.org/quantumcomputingexplained/ . Unfortunately, there is no video recording so they are currently lacking explanations.
My goal was to explain quantum computing in a way that is mathematically precise but doesn't require one to learn linear algebra first. To do this, I implemented a quantum computer simulator in Javascript that runs in the web browser. Conceptually (in mathematical language), in each simulation I present, I've started by enumerating the computational basis of the Hilbert space (all possible states the qubits could be in) and represented the computational state by putting an arrow beside each of them, which really is a complex number. (This similar to how Feynman explains things in his book QED.) The magnitude of the complex number is the length of the arrow, and its phase is the direction it points (encoded redundantly by its color). I've filled out the amplitude symbol with a square so that at any given point, its probability of a measurement resulting in that outcome is proportional to the area of that square. Essentially, in this language, making a measurement makes the experimenter color blind -- only the relative areas of the amplitudes matter and there is no way to learn directly phase information without doing a different experiment.
I could make a further document explaining along these lines if people are interested. The source is on github too: https://github.com/garrison/jsqis
IBM has an amazing tool for this. Not only do they have a great simulator, but you can enter a queue to run your program on their real quantum computer:
If you understand Turing Machines, you probably also understand other automata. So you probably understand nondeterministic automata [1].
A quantum computer is like a very restricted nondeterministic automaton, except that the "do several things a once" is implemented in physics. That means just like a NFA can be exponential faster than a DFA, a QC can be exponential faster than a normal computer. But the restriction on QCs makes that a lot harder to do, and so far it only works for some algorithms.
As to why quantum physics allows some kind of nondeterminism: If you look at particles as waves, instead of a single location you get a probability function that tells you "where the particle is". So a particule can be "in several places at once". In the same way a qbit can have "several states at once".
> What I don't understand is how a programmer is supposed to determine the correct solution when their computer is out in some crazy multiverse.
Because one way to explain quantum physics is to say that the waveform can "collapse" [2] and produce a single result, as least as far as the observers are concerned. There are other interpretations of this effect, and this effect is what makes quantum physics counterintuitive and hard to understand.
You can't, it's a fundamental aspect of quantum mechanics (measuring any entangled system collapses it because you've forced the system into a state by measuring it).
The idea is that you structure the QC system such that the computation is done using entangled states, but when it comes to measuring the qubits (to get the result of the computation) the state is such that you'll get meaningful results. This means the quantum state at the end of the calculation would ideally be along whatever axes you're measuring, so you get the same answer 100% of the time.
OK but this implies that you'll have to know beforehand what a result will look like. Which kind of beats the purpose of a general purpose computational device.
No it doesn't. You know that the result of the computation for an individual qubit will be either 0 or 1 (otherwise it would be useless -- measuring only gives you one bit of information), so you construct the system such that after the computation is done each qubit will be aligned with the |+z> or whatever axis. The key point is that you have to be clever about how you construct the system for a given QC algorithm, not that you cannot do arbitrary computations using the system.
OK but we're back on square one. If you can't read info from qbits without breaking the state of the whole freaking system then what exactly is that you reading? Doesn't the alignment info collapses superposition?
You do "break the state of the whole freaking system". Once you've read the output, you're done. You have to set up your initial state again and run the computation from scratch.
However, even with understanding how a Quantum Computer works at its most basic level I still have difficulty understanding the more useful Quantum Algorithms:
I honestly recommend the following:
1. Pick up the standard textbook by Nielsen and Chuang, Quantum computation and quantum information. read the first two to three chapters.
2. Solve the exercises for the Q# programming language.
It explains in terms a computer scientist can understand. As in: it sets out a computational model and explores it, regardless whether we can physically realize that machine.
I wrote a basic response, but it got longer than I thought it would and HN complained about it being too long, so here's a pastebin: https://pastebin.com/zTJA4bJh
IBM's Quantum Experience is great for this. It walks you through the quantum gates you can use and lets you write small programs for quantum processors.
I've found that to be the clearest way of understanding what qcs do.
Pseudo-code for quantum computers is currently linear algebra. Fortunately, most programmers have the required linear algebra to get a thorough understanding of the basics! Check this out https://quantum.country/qcvc. Fair warning, I did have to brush up on my linear algebra a bit, but it's worth it imo. Friends in the know say that when you understand this article, you understand quantum computers.
I had an aha moment with quantum computers a few months ago when reading an article that explained it as probability distributions. I don't think I have the complete understanding in my mind anymore and I wish I had saved the article, but looking into how quantum computers essentially serve as probability distribution crunching machines might help with your understanding.
So can they still do traditional deterministic(?) calculations? Or would that be somewhat akin to using machine learning to do your taxes; possible but just overkill?
I've often heard it said that Quantum Computers can crack cryptographic keys by trying all the possible inputs for a hashing algorithm or something handwavey like that. Are they just spitting out "probable" solutions then? Do you still have to try a handful of the solutions manually just to see which one works?
"Trying all possible solutions" is generally a bad metaphor for quantum computing and will confuse you. (Its more like you start out with all answers being equal probability, and get the wrong answers to somehow cancel each other out making the "right" answer have a high probability)
I am not a quantum person but i once saw a geometric explanation for grover's algorithm which kind of made it all make sense to me. (grover's algorithm is the quantum algo you use for problems where you dont know any approach better than brute force. It can bruteforce stuff in O(sqrt(n)) guesses instead of O(n) like a normal computer). Basically, the geometric version was that you start with all possibilities being of equal probability (i.e. an even superposition of all possible states), negate the amplitude of the correct answer, then reflect the amplitudes around a line that is the mean of the amplitudes (do that sqrt(n)) times. The end result is the correct answer has a higher probability than the other answers. I unfortunately can't find the thing where i originally saw this, but they visualized it basically as a bar graph (of the amplitudes of possible states) and it seemed much clearer to me than other explanations i have come across
Yeah, they can do deterministic calculations. You just avoid ever putting the quibits in a state where measurement gives probabilistic results. it would, however, be a ridiculous use of technology, like using a Neural net to simulate an XOR
Like probability distributions, but they don't just sum when you combine them, they interfere (probability is the square of amplitude, which can be negative).
Quantum computing is all about finding ways to hack the interference process to compute more than you otherwise would have.
Nobody understands quantum mechanics. Lots of people know how to apply it. I don't think quantum technology is going to go anywhere until physicists revamp the theory & the pedagogy in a way that makes it comprehensible.
I say this as someone who passed 2 semesters of graduate QM.
> I say this as someone who passed 2 semesters of graduate QM.
THat's funny because my EE math concentration was on advanced calculus. I took two semesters of a-calc and got A's, but I only know how to compute a Jacobian and apply it, not its origin story. It's a very weird feeling to understand the motions but not the ... depth?
The basic idea is that by making the amplitudes of the qubits destructively interfere with each other in certain ways, you can eliminate all of the wrong answers to the question you're trying to answer.
not quantum computers per se but I had my aha moment when I saw quantum computing as "linear algebra with probability coefficients". It's mostly working on superpositioned qubits while doing the calculation and then making them (with linear transformations) as likely as possible to collapse on the solution (when "measured").
I looked briefly at QCs and I understood them as kind of a machine that doesn't try every possible solution. It is in every possible solution, and then you can somehow "lock it" in the state that is the solution to your problem. Kind of like NP problems are hard to find a solution but easy to verify a solution.
I think because it has less applications for traditional "software" and more applications for efficiency of embedded systems.
But it could have some bleeding edge new applications from the TCP/IP space for urgent point, new methods for cryptography, or speeding up algorithms for searching. ¯\_(ツ)_/¯
Im not an expert on quantum computers but I'm not aware of any applications in the embedded space.
Generally quantum computers are good for three things
* factoring numbers (and other highly related order-finding problems). RIP RSA, but not that applicable outside of crypto.
* unstructured search (brute forcing a problem in only O(sqrt(n)) gueses instead of an average of n/2 gueses). Certainly useful...but its not a big enough speedup to be earth shattering.
* simulating various quantum systems (so scientists can do experiments easier). Probably by far the most useful/practical application in the near/medium term.
There's not a whole lot else they are good for (that we know of, yet)
Qubit is physical random generator, which quickly oscillates between 0 and 1. It does that so quickly, so scientists must operate with probabilities to perform calculations. They create analog quantum computers, where right solutions are much more probable than wrong ones, then let system to figure them out, then sample solutions periodically.
The basic gist I get is that quantum computing, for a very specific set of problems, like optimization, let's you search the space more efficiently. With quantum mechanics you can associate computations with positive or negative probability amplitudes. With the right design, you cause multiple paths to incorrect answers to have opposite amplitudes, so that interference causes them to cancel out and not actually happen to begin with. That's just my reading of the comic over and over though.
Along those same lines, I once heard a description that went something like: "Imagine a Jenga tower so precisely balanced that, when it falls over, it spells out the answer."
I found the comic not very good either. Kid suddenly blurts "Wait a minute, that means a qubit corresponds to a unit vector in 2 dimensional Hilbert space"
Yeah.
Not quite what I meant. I think the comic is excellent. In case its not painfully obvious, the joke is equating lay people's poor understanding of quantum mechanics to a child's misunderstanding of sex. It's not trying to dumb down the concept of quantum computers at all, it's just trying to point out how incorrect how dumb pop science simplifications of it are. The 'qubits are bits with a range of value between 0 and 1 that use quantum magic to test all possibilities at once' is utter fiction.
Short answer: there isn't an easy answer. Yet. (Give QC another 50 years).
Proof? Just look at all the replies you got: each one is dozens of pages of complex (imaginary) math, control theory, and statistics.
The hardest part of QC is exactly what you described: how to extract the answer. There is no algorithm, per se. You build the system to solve the problem.
This is why QC is not a general purpose strategy: a quantum computer won't run Ubuntu, but it will be one superfast prime factoring coprocessor, for example (or pathfinder, or root solver). You literally have to build an entire machine to solve just one problem, like factoring.
Look at Shor's algorithm: it has a classical algorithm and then a QC "coprocessor" part (think of that like an FPU looking up a transcendental from a ROM: it appears the FPU is computing sin(), but it is not, it is doing a lookup... just an analogy). The entire QC side is custom built just to do this one task:
This feels like the high-level missing piece in my understanding of its use. Do you know any resources that expand on QC’s effective potential more from this point of view?
This project involves a minisatellite (capable of generating entangled photons in space) to establish a space platform with long-distance satellite and ground quantum channel, and to carry out a series of tests about fundamental quantum principles and protocols in space-based large scale
In short I'd say you need to understand the underlying mathematics to intuitively understand the operations that underpinn the algorithms. And since this is quantum mechanics...there's no real ELI5 version that can give you any useful understanding.
