6 ms·

Qusim.py – A toy multi-qubit quantum computer simulator written in Python

242 points by adamisntdead 9y ago

ahelwer 9y ago
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.
- adamisntdead 9y ago
  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 http://github.com/qcgpu/qcgpu-rust if you are interested! Always looking for feedback
  - ahelwer 9y ago
    I've wondered - is it a common memory optimization tactic to store the individual qbit values until they become entangled and the product state cannot be factored? Or is entanglement common enough that it wouldn't be worth the overhead?
    - adamisntdead 9y ago
      It depends! If you use a lot of scratch qubits, it can be useful to use sparse vectors, but if you are going to be doing a lot of superpositions / entangling many qubits, this isn't as effective, and performance suffers a lot. Libraries such as libquantum (written in C) use sparse state vectors, whereas the QCGPU library uses dense state vectors (as it is being stored on the GPU, it doesn't really impact the performance of the computer it's being simulated on). I benchmarked it, and the rust one was way faster for everything, apart from the initialization of registers and the application of some controlled gates
- sytelus 9y ago
  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.
  - adamisntdead 9y ago
    You can, but it would be very slow! This implementation gets really really slow around 15/16 qubits. I am currently working on implementing shors algorithm into my main, simulation library. I already have grovers algorithm! https://qcgpu.github.io/qcgpu-rust/book/algorithms/grover.html https://qcgpu.github.io/qcgpu-rust/book/algorithms/grover.ht...
    - AstralStorm 9y ago
      Might it be caused by the use of slow matrix operation algorithms rather than the size?
- thethirdone 9y ago
  > 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.
  - adamisntdead 9y ago
    Yep, observables in quantum mechanics are represented by hermitian matrices
  - ahelwer 9y ago
    Oh wow, am I wrong? I thought all quantum operators were their own inverses, which since they're all unitary means they must be hermitian.
- andrepd 9y ago
  >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).
  - ahelwer 9y ago
    Thanks for the correction! I thought all quantum operators were their own inverse, but I guess I was wrong.
  - comnetxr 9y ago
    Neither unitary or hermitian means that operators are there own inverse. Unitary here means that the inverse is the same as the complex transpose - which means that there is an inverse and it is easy to find. This is important as quantum circuits must be composed of unitaries, i.e. the circuit is reversable. Hermitian operators have no particular special property with respect to inverses.
    - andrepd 9y ago
      Quantum gates are unitary because of conservation of probability (the out state must be remain normalized to 1). If it's also hermitian (equal to conjugate transpose) then it's its own inverse.
- keyle 9y ago
  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?
  - ahelwer 9y ago
    I recommend the textbook Quantum Computing for Computer Scientists.
    - adamisntdead 9y ago
      I would also have to recommend "Quantum Mechanics, The Theoretical Minimum" by Leonard Susskind, if you wish to go a little bit further into general quantum mechanics
  - adamisntdead 9y ago
    You should check out these videos, one of them might give you an understanding! - https://www.youtube.com/watch?v=JhHMJCUmq28 https://www.youtube.com/watch?v=JhHMJCUmq28 | Quantum Computers Explained - https://www.youtube.com/watch?v=IrbJYsep45E https://www.youtube.com/watch?v=IrbJYsep45E | The Mathematics of Quantum Computers - https://www.youtube.com/watch?v=wUwZZaI5u0c https://www.youtube.com/watch?v=wUwZZaI5u0c | Hacking at Quantum Speed with Shor's Algorithm - https://www.youtube.com/playlist?list=PL1826E60FD05B44E4 https://www.youtube.com/playlist?list=PL1826E60FD05B44E4 | A series by the author of the standard textbook These are videos I particularly like!
  - Deestan 9y ago
    This sounds snide, but please believe me my intention is to be helpful. Have you considered instead raising your level? The relevant topic, as stated in the comment, is linear algebra.
    - perl4ever 9y ago
      My experience with linear algebra is that it's possible to get an excellent grade in class, without learning anything, provided the tests are multiple choice...
- Moodles 9y ago
  I'm no expert, but SMBC covers quantum computers quite well too :-) https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3
  - alemhnan 9y ago
    The red button was a nice touch. I genuinely laughed.
  - lorenzorhoades 9y ago
    After reading that article, you pretty much become an expert. I'm going to go apply to dwave now.
- rorykoehler 9y ago
  This is a great succinct explanation. I definitely understand QC's better after reading it. Thanks.
mentos 9y ago
Is it possible that a massive array of GPUs might be more economical than a few real quantum chips that need to be cooled to absolute zero?
- sgillen 9y ago
  That absolutely is the case right now, it may not be in a few decades.
- ejdanderson 9y ago
  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.
- adrianN 9y ago
  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.
  - AstralStorm 9y ago
    Indeed. I'd expect this to top of at about 64 qbits with smart maths. (Mostly due to pointer limitations.) You could try to extend addressing but it'll be even slower...
    - claudius 9y ago
      Just as a data point: Current state-of-the-art methods for Lanczos-type methods on state vectors are around 40 spins/qubits incorporating many symmetries and additional shortcuts one does not have in a generic "quantum computer simulator". Without those symmetries/shortcuts, the limit is likely closer to 30 qubits (i.e. approx. 16-64 GB per state vector), as it’s not only necessary to store these beasts but also do operations on them. If you don’t insist on a single dense state vector but a sparser tensor network-based formulation, you can go to much larger systems (hundreds or thousands of spins) but will be limited by the amount of entanglement you can represent in your system.
da-bacon 9y ago
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 https://github.com/dabacon/qsel The simulator takes about 150 lines of python as well.
- vtomole 9y ago
  Hey Dave, your lecture notes [0] helped us a lot when we were building our simulator [1]. Thank you! [0]: https://courses.cs.washington.edu/courses/cse599d/06wi/ https://courses.cs.washington.edu/courses/cse599d/06wi/ [1]: https://github.com/QCHackers/qchackers/tree/master/software/kite/qvm https://github.com/QCHackers/qchackers/tree/master/software/...
  - da-bacon 9y ago
    That class was so many careers ago. Glad you enjoyed the notes. I wonder if I taught it today: maybe I'd start by having students use a simulator, or maybe trying to write a simple simulator themselves!
  - ejdanderson 9y ago
    Hey that code looks familiar :)
laughingman2 9y ago
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 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 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?
- adrianN 9y ago
  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.
- Panoramix 9y ago
  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. [1]https://www.technologyreview.com/s/609451/ibm-raises-the-bar-with-a-50-qubit-quantum-computer/ https://www.technologyreview.com/s/609451/ibm-raises-the-bar...
deleted 9y ago
[deleted]
nathanshammah 9y ago
If you’re interested in quantum tech, here is my newsletter https://medium.com/quantum-tech https://medium.com/quantum-tech You can subscribe here http://eepurl.com/c10FJz http://eepurl.com/c10FJz

242 points by adamisntdead 9y ago

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.

adamisntdead 9y ago
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 http://github.com/qcgpu/qcgpu-rust if you are interested! Always looking for feedback
- ahelwer 9y ago
  I've wondered - is it a common memory optimization tactic to store the individual qbit values until they become entangled and the product state cannot be factored? Or is entanglement common enough that it wouldn't be worth the overhead?
  - adamisntdead 9y ago
    It depends! If you use a lot of scratch qubits, it can be useful to use sparse vectors, but if you are going to be doing a lot of superpositions / entangling many qubits, this isn't as effective, and performance suffers a lot. Libraries such as libquantum (written in C) use sparse state vectors, whereas the QCGPU library uses dense state vectors (as it is being stored on the GPU, it doesn't really impact the performance of the computer it's being simulated on). I benchmarked it, and the rust one was way faster for everything, apart from the initialization of registers and the application of some controlled gates
sytelus 9y ago
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.
- adamisntdead 9y ago
  You can, but it would be very slow! This implementation gets really really slow around 15/16 qubits. I am currently working on implementing shors algorithm into my main, simulation library. I already have grovers algorithm! https://qcgpu.github.io/qcgpu-rust/book/algorithms/grover.html https://qcgpu.github.io/qcgpu-rust/book/algorithms/grover.ht...
  - AstralStorm 9y ago
    Might it be caused by the use of slow matrix operation algorithms rather than the size?
thethirdone 9y ago
> 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.
- adamisntdead 9y ago
  Yep, observables in quantum mechanics are represented by hermitian matrices
- ahelwer 9y ago
  Oh wow, am I wrong? I thought all quantum operators were their own inverses, which since they're all unitary means they must be hermitian.
andrepd 9y ago
>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).
- ahelwer 9y ago
  Thanks for the correction! I thought all quantum operators were their own inverse, but I guess I was wrong.
- comnetxr 9y ago
  Neither unitary or hermitian means that operators are there own inverse. Unitary here means that the inverse is the same as the complex transpose - which means that there is an inverse and it is easy to find. This is important as quantum circuits must be composed of unitaries, i.e. the circuit is reversable. Hermitian operators have no particular special property with respect to inverses.
  - andrepd 9y ago
    Quantum gates are unitary because of conservation of probability (the out state must be remain normalized to 1). If it's also hermitian (equal to conjugate transpose) then it's its own inverse.
keyle 9y ago
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?
- ahelwer 9y ago
  I recommend the textbook Quantum Computing for Computer Scientists.
  - adamisntdead 9y ago
    I would also have to recommend "Quantum Mechanics, The Theoretical Minimum" by Leonard Susskind, if you wish to go a little bit further into general quantum mechanics
- adamisntdead 9y ago
  You should check out these videos, one of them might give you an understanding! - https://www.youtube.com/watch?v=JhHMJCUmq28 https://www.youtube.com/watch?v=JhHMJCUmq28 | Quantum Computers Explained - https://www.youtube.com/watch?v=IrbJYsep45E https://www.youtube.com/watch?v=IrbJYsep45E | The Mathematics of Quantum Computers - https://www.youtube.com/watch?v=wUwZZaI5u0c https://www.youtube.com/watch?v=wUwZZaI5u0c | Hacking at Quantum Speed with Shor's Algorithm - https://www.youtube.com/playlist?list=PL1826E60FD05B44E4 https://www.youtube.com/playlist?list=PL1826E60FD05B44E4 | A series by the author of the standard textbook These are videos I particularly like!
- Deestan 9y ago
  This sounds snide, but please believe me my intention is to be helpful. Have you considered instead raising your level? The relevant topic, as stated in the comment, is linear algebra.
  - perl4ever 9y ago
    My experience with linear algebra is that it's possible to get an excellent grade in class, without learning anything, provided the tests are multiple choice...
Moodles 9y ago
I'm no expert, but SMBC covers quantum computers quite well too :-) https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3
- alemhnan 9y ago
  The red button was a nice touch. I genuinely laughed.
- lorenzorhoades 9y ago
  After reading that article, you pretty much become an expert. I'm going to go apply to dwave now.
rorykoehler 9y ago
This is a great succinct explanation. I definitely understand QC's better after reading it. Thanks.

mentos 9y ago

Is it possible that a massive array of GPUs might be more economical than a few real quantum chips that need to be cooled to absolute zero?

sgillen 9y ago
That absolutely is the case right now, it may not be in a few decades.
ejdanderson 9y ago
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.
adrianN 9y ago
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.
- AstralStorm 9y ago
  Indeed. I'd expect this to top of at about 64 qbits with smart maths. (Mostly due to pointer limitations.) You could try to extend addressing but it'll be even slower...
  - claudius 9y ago
    Just as a data point: Current state-of-the-art methods for Lanczos-type methods on state vectors are around 40 spins/qubits incorporating many symmetries and additional shortcuts one does not have in a generic "quantum computer simulator". Without those symmetries/shortcuts, the limit is likely closer to 30 qubits (i.e. approx. 16-64 GB per state vector), as it’s not only necessary to store these beasts but also do operations on them. If you don’t insist on a single dense state vector but a sparser tensor network-based formulation, you can go to much larger systems (hundreds or thousands of spins) but will be limited by the amount of entanglement you can represent in your system.

da-bacon 9y ago

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 https://github.com/dabacon/qsel The simulator takes about 150 lines of python as well.

vtomole 9y ago
Hey Dave, your lecture notes [0] helped us a lot when we were building our simulator [1]. Thank you! [0]: https://courses.cs.washington.edu/courses/cse599d/06wi/ https://courses.cs.washington.edu/courses/cse599d/06wi/ [1]: https://github.com/QCHackers/qchackers/tree/master/software/kite/qvm https://github.com/QCHackers/qchackers/tree/master/software/...
- da-bacon 9y ago
  That class was so many careers ago. Glad you enjoyed the notes. I wonder if I taught it today: maybe I'd start by having students use a simulator, or maybe trying to write a simple simulator themselves!
- ejdanderson 9y ago
  Hey that code looks familiar :)

laughingman2 9y ago

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 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 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?

adrianN 9y ago
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.
Panoramix 9y ago
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. [1]https://www.technologyreview.com/s/609451/ibm-raises-the-bar-with-a-50-qubit-quantum-computer/ https://www.technologyreview.com/s/609451/ibm-raises-the-bar...

deleted 9y ago

[deleted]

nathanshammah 9y ago

If you’re interested in quantum tech, here is my newsletter https://medium.com/quantum-tech https://medium.com/quantum-tech You can subscribe here http://eepurl.com/c10FJz http://eepurl.com/c10FJz