For the uninitiated - to simulate a basic quantum computer, all you need is the following:
* A product state vector, which is a vector of size 2^n filled with complex numbers where n is the number of qbits you're using. You derive the product state from a series of individual qbits by taking their tensor product; this exponential term is why simulating quantum computers takes exponential space.
* A set of common quantum logic gates, which are (2^n)x(2^n) matrices you multiply against the product state vector to derive the new product state vector; these matrices must be unitary (their conjugate-transpose is their inverse) (edited, see [0]) and therefore reversible (quantum computers are reversible computers). The full (2^n)x(2^n) matrices are derived by taking the tensor products of several 2x2 and 4x4 matrices.
* The measurement logic, where you calculate how the product state collapses by taking the square of the absolute value of each entry in the product state (these entries are called amplitudes).
This project is an implementation of those three things in Python. There is nothing special about the above mathematical constructs save that they match the observed semantics of a quantum system. This is good! Quantum computing is accessible to anyone who has taken a basic undergraduate course in linear algebra.
[0] I previously believed all quantum operators were their own inverses (Unitary and Hermitian) but apparently that is not the case; see comments below.
That's pretty much it! There obviously is loads of optimizations that can be done, but it obscures the pretty standard linear algebra that is used to represent and calculate the states of the quantum computer!
A well-written version using OpenCL and written in rust is also available: http://github.com/qcgpu/qcgpu-rust if you are interested! Always looking for feedback
>these matrices must be their own inverse (in mathematical terms, Unitary and Hermitian)
Not necessarily. The only requirement on quantum operators is that they must be unitary. Only observables have to be Hermitian (so they have real eigenvalues).
This is awesome. Over time I have came across too many posts claiming to explain QCs to hackers and they go on pages and pages without distilling this simple little thing. It would be great if you can also implement something like Shore's algo with your simulator.
> these matrices must be their own inverse (in mathematical terms, Unitary and Hermitian). The full (2^n)x(2^n) matrices are derived by taking the tensor products of several 2x2 and 4x4 matrices.
Gates don't have to be Hermitian right? Like NOT^(1/2) is not Hermitian.
Thanks for the description but that made very little sense to a 'regular' developer like me. Any chance you could break it down and bring it down to my level?
Cool! My April fools day joke this year was a quantum programming language made up entirely of "entanglement" and "superposition":
https://github.com/dabacon/qsel
The simulator takes about 150 lines of python as well.
There is this quote by Jürgen Schmidhuber, director at the Swiss AI Lab IDSIA , creator of LSTM Neural Nets that power many of our current machine learning applications.
" General purpose quantum computation won’t work (my prediction of 15 years ago is still standing). Related: The universe is deterministic, and the most efficient program that computes its entire history is short and fast, which means there is little room for true randomness, which is very expensive to compute. What looks random must be pseudorandom, like the decimal expansion of Pi, which is computable by a short program. Many physicists disagree, but Einstein was right: no dice. There is no physical evidence to the contrary randomness.html[http://people.idsia.ch/~juergen/randomness.html].
For example, Bell’s theorem does not contradict this. And any efficient search in program space for the solution to a sufficiently complex problem will create many deterministic universes like ours as a by-product. Think about this. More here computeruniverse.html [http://people.idsia.ch/~juergen/computeruniverse.html] and here.
"
I am out of depth with regards to quantum theory and quantum computation. If anyone with better knowledge with regards to quantum computation can clarify it would be great.
Is there any rationale to support Schmidhuber's argument, and has any advance in making actual quantum computers disprove his theory?
I have looked into this somewhat deeply and he might have a point, but it's a bit subtle. First, current computers are not powerful enough to show him wrong. Second, the Many Worlds interpretation of QM is both deterministic and quantum, and since Jurgen is assuming his super-program creates a multiverse anyway, it's a logical next step.
The meat of Jurgen's proposal is that "fast" programs are more likely (which makes sense, IMHO) and quantum universes are too wasteful computationally (which seems less obvious).
If you want to read more along these lines, I can recommend something quite interesting from last year. It references Jurgen but argues that computational speed doesn't matter, only the length of the algorithm needed to produce our subjective experiences:
Could the physical world be emergent instead of fundamental, and why should we ask? (short version) by Markus P. Mueller
https://arxiv.org/abs/1712.01816
Whether or not the universe is deterministic, quantum computers will work as long as nature works by wavefunctions and unitary matrices. There are many good reasons for believing this to be true, including experiments. Real randomness is not a requirement.
Schmidhuber doesn't seem to be a physicist, so I'll go with the majority of physicists on this one. Currently there is no reason to assume that quantum computers are impossible. There might be engineering challenges that we can't overcome, but quantum mechanics is a decently well established field and unless its assumptions are fundamentally wrong, quantum computers should work.
Sounds like a crackpot to be honest. QC doesn't work yet because of practical limitations, but individual blocks have been shown to work separately and even small computers [1]. In looking at his wording he may be addressing a straw man, because QC has never aimed to be a general purpose general computer.
The universe is usually thought of as not deterministic. The deterministic interpretations out there come with huge problems: non-locality. Basically, that all particles in the universe are connected with a wave of sorts that acts instantaneously no matter the distance. But this is a philosophical distinction at best. Quantum computers work just fine.
In the short term, yes, while the number of qubits is small and even smaller when you consider logical qubits require multiple real qubits to account for error.
In simplified terms though, for every logical qubit you add to the system, you effectively double the power of the machine. To double the power of your GPU stack, you'd need 2x more GPUSs each time. There is also the additional caveat of the type of problem - not every problem currently suited for a gpu is going to be better run on a qpu.
That depends on the number of qbits you want to simulate. Doing the calculations on classical computers has an exponential slowdown as you need 2^n classical bits to store n qbits. It's pretty unlikely that you will ever be able to simulate a quantum computer with more than a few dozen qbits.
[+] [-] ahelwer|8 years ago|reply
* A product state vector, which is a vector of size 2^n filled with complex numbers where n is the number of qbits you're using. You derive the product state from a series of individual qbits by taking their tensor product; this exponential term is why simulating quantum computers takes exponential space.
* A set of common quantum logic gates, which are (2^n)x(2^n) matrices you multiply against the product state vector to derive the new product state vector; these matrices must be unitary (their conjugate-transpose is their inverse) (edited, see [0]) and therefore reversible (quantum computers are reversible computers). The full (2^n)x(2^n) matrices are derived by taking the tensor products of several 2x2 and 4x4 matrices.
* The measurement logic, where you calculate how the product state collapses by taking the square of the absolute value of each entry in the product state (these entries are called amplitudes).
This project is an implementation of those three things in Python. There is nothing special about the above mathematical constructs save that they match the observed semantics of a quantum system. This is good! Quantum computing is accessible to anyone who has taken a basic undergraduate course in linear algebra.
[0] I previously believed all quantum operators were their own inverses (Unitary and Hermitian) but apparently that is not the case; see comments below.
[+] [-] Moodles|8 years ago|reply
https://www.smbc-comics.com/comic/the-talk-3
[+] [-] adamisntdead|8 years ago|reply
A well-written version using OpenCL and written in rust is also available: http://github.com/qcgpu/qcgpu-rust if you are interested! Always looking for feedback
[+] [-] andrepd|8 years ago|reply
Not necessarily. The only requirement on quantum operators is that they must be unitary. Only observables have to be Hermitian (so they have real eigenvalues).
[+] [-] sytelus|8 years ago|reply
[+] [-] thethirdone|8 years ago|reply
Gates don't have to be Hermitian right? Like NOT^(1/2) is not Hermitian.
[+] [-] keyle|8 years ago|reply
[+] [-] rorykoehler|8 years ago|reply
[+] [-] da-bacon|8 years ago|reply
[+] [-] vtomole|8 years ago|reply
[0]: https://courses.cs.washington.edu/courses/cse599d/06wi/
[1]: https://github.com/QCHackers/qchackers/tree/master/software/...
[+] [-] laughingman2|8 years ago|reply
" General purpose quantum computation won’t work (my prediction of 15 years ago is still standing). Related: The universe is deterministic, and the most efficient program that computes its entire history is short and fast, which means there is little room for true randomness, which is very expensive to compute. What looks random must be pseudorandom, like the decimal expansion of Pi, which is computable by a short program. Many physicists disagree, but Einstein was right: no dice. There is no physical evidence to the contrary randomness.html[http://people.idsia.ch/~juergen/randomness.html].
For example, Bell’s theorem does not contradict this. And any efficient search in program space for the solution to a sufficiently complex problem will create many deterministic universes like ours as a by-product. Think about this. More here computeruniverse.html [http://people.idsia.ch/~juergen/computeruniverse.html] and here.
"
I am out of depth with regards to quantum theory and quantum computation. If anyone with better knowledge with regards to quantum computation can clarify it would be great.
Is there any rationale to support Schmidhuber's argument, and has any advance in making actual quantum computers disprove his theory?
[+] [-] akvadrako|8 years ago|reply
The meat of Jurgen's proposal is that "fast" programs are more likely (which makes sense, IMHO) and quantum universes are too wasteful computationally (which seems less obvious).
If you want to read more along these lines, I can recommend something quite interesting from last year. It references Jurgen but argues that computational speed doesn't matter, only the length of the algorithm needed to produce our subjective experiences:
Could the physical world be emergent instead of fundamental, and why should we ask? (short version) by Markus P. Mueller https://arxiv.org/abs/1712.01816
[+] [-] comicjk|8 years ago|reply
[+] [-] adrianN|8 years ago|reply
[+] [-] Panoramix|8 years ago|reply
The universe is usually thought of as not deterministic. The deterministic interpretations out there come with huge problems: non-locality. Basically, that all particles in the universe are connected with a wave of sorts that acts instantaneously no matter the distance. But this is a philosophical distinction at best. Quantum computers work just fine.
[1]https://www.technologyreview.com/s/609451/ibm-raises-the-bar...
[+] [-] jrochkind1|8 years ago|reply
[+] [-] mentos|8 years ago|reply
[+] [-] ejdanderson|8 years ago|reply
In simplified terms though, for every logical qubit you add to the system, you effectively double the power of the machine. To double the power of your GPU stack, you'd need 2x more GPUSs each time. There is also the additional caveat of the type of problem - not every problem currently suited for a gpu is going to be better run on a qpu.
[+] [-] adrianN|8 years ago|reply
[+] [-] sgillen|8 years ago|reply
[+] [-] nathanshammah|8 years ago|reply
You can subscribe here http://eepurl.com/c10FJz
[+] [-] unknown|8 years ago|reply
[deleted]