6 ms·

A tutorial quantum interpreter in 150 lines of Lisp

232 points by varjag 3y ago

mighmi 3y ago
Any recommendations on a textbook to understand this kind of math?
- prezjordan 3y ago
  Might be of use! https://quantum.country/ https://quantum.country/
  - reikonomusha 3y ago
    One of the authors, Michael Nielson, also wrote the "bible" of quantum computing, as referenced in a sibling comment. The remains one of the most popular and cited introductory texts to the subject, though today there are many more options on the market.
- abdullahkhalids 3y ago
  Quantum Computation and Quantum Information by Nielson and Chuang is the standard textbook for quantum computing. It has excellent background chapters on linear algebra and quantum mechanics, that will get you a lot of mileage. Another book that I would recommend is Introduction to Classical and Quantum Computing by Thomas Wong. It's recent and has lots of examples, including lots of code, to show how to work with the math.
- hackandthink 3y ago
  Ronald de Wolf: Quantum Computing: Lecture Notes Ronald de Wolf: https://arxiv.org/abs/1907.09415 https://arxiv.org/abs/1907.09415 David Bacon: https://courses.cs.washington.edu/courses/cse599d/06wi/ https://courses.cs.washington.edu/courses/cse599d/06wi/ Scott Aaronson: https://en.wikipedia.org/wiki/Quantum_Computing_Since_Democritus https://en.wikipedia.org/wiki/Quantum_Computing_Since_Democr...
- jksk61 3y ago
  maybe not of your interest, but if one is more from a ML background, there's this nice book/overview by Maria Schuld and Francesco Petruccione, called Machine Learning with Quantum Computers, which is mostly regarding variational algorithm and quantum kernel machine. However, the best intro material is the one by Nielsen and Chuang. Moreover, if you feel more comfortable by running examples there are qiskit, pennylane and other libraries which shares a lot of tutorials and notebook (and some can be run on a true quantum computer if you have the money or the time to wait in queue!)
Strilanc 3y ago
The hardest part of implementing a quantum state vector simulation is understanding how the tensor product expands an n-qubit gate to apply to an m-qubit system. (A third of the linked post is dedicated to it; appropriately.) If you use a language or framework that's based on tensors to start with, things can be quite succinct (though you still need to understand the concepts). For example, in numpy, if you store the state vector in an array of shape (2,) * num_qubits, you can apply gates as one-liners using np.einsum: import numpy as np # Init 4-qubit system with all amplitude in the 0000 state. state = np.zeros(shape=(2,) * 4, dtype=np.complex64) state[(0,) * 4] = 1 # Unitary matrix of Hadamard gate H = np.array([[1, 1], [1, -1]], dtype=np.complex64) / 2**0.5 # Apply Hadamard gate to third qubit of four qubit system. state = np.einsum('XY,abXd->abYd', H, state) Here's a post explaining what np.einsum does: https://obilaniu6266h16.wordpress.com/2016/02/04/einstein-summation-in-numpy/ https://obilaniu6266h16.wordpress.com/2016/02/04/einstein-su... . In the above einsum string 'XY,abXd->abYd' the 'XY' part is naming the input and output axes of the Hadamard matrix, and the 'abXd->abYd' part is saying to multiply the matrix into the third axis of the state tensor. The notation is pretty general, able to permute and repeat axes in order to express things like traces and transposes and dot products and etc.
- reikonomusha 3y ago
  "einsum" in Lisp [1]. It uses S-expressions instead of strings, and compiles to native loops. [1] https://github.com/quil-lang/magicl/blob/master/src/high-level/einsum.lisp#L15 https://github.com/quil-lang/magicl/blob/master/src/high-lev...
  - lionsdan 3y ago
    (Link didn't work for me) https://github.com/quil-lang/magicl/blob/master/src/high-level/einsum.lisp https://github.com/quil-lang/magicl/blob/master/src/high-lev...
- jxf 3y ago
  > The hardest part of implementing a quantum state vector simulation is understanding how the tensor product expands an n-qubit gate to apply to an m-qubit system. (A third of the linked post is dedicated to it; appropriately.) This feels like it could be the "git gets easier once you understand branches are homeomorphic endofunctors mapping submanifolds of a Hilbert space" of physics.
adamisntdead 3y ago
I wrote something similar a couple of years ago - https://github.com/adamisntdead/QuSimPy https://github.com/adamisntdead/QuSimPy Happy to answer any questions people have, including on other simulation methods other than state vector!
- reikonomusha 3y ago
  One of the aspects emphasized in TFA is being able to simulate gates of any dimension/number of qubits (like a 3-qubit Toffoli or a 5-qubit Molmer-Sorensen), instead of just 1- and 2-qubit gates. Have you thought about extending your simulator to support gates of greater than two qubits?
  - adamisntdead 3y ago
    I guess back when I wrote it I didn't see the need given that single qubit gates along with CNOT are universal and they're implemented. I think airing on the side of 'as few features as is educational' was my mentality on this.
  - JBits 3y ago
    I know about the conventional 2-qubit Molmer-Sorensen but not the 5-qubit version. Could I ask what it is?
    - reikonomusha 3y ago
      See e.g. equations (5) and (6) from [1], where any qubit subset of a system might undergo the action of the M–S gate. But definitely the usual presentation of the physics of M–S is on a two qubit system. [1] https://arxiv.org/abs/1601.06819 https://arxiv.org/abs/1601.06819
eggy 3y ago
I'm deciding between Common Lisp and Mojo, so maybe I will try to implement this in Mojo and compare. Anybody have any thoughts on this, since I am a mediocre Lisper and a beginning Mojo person. I am familiar with Numpy and I also program in APL and J.
- Archit3ch 3y ago
  May I suggest Julia? Efficient and capable of (Common Lisp style) abstractions. Unsurprisingly, there are more than a few quantum projects in the ecosystem already.
  - eggy 3y ago
    I've used Julia with Pluto and Weave to create engineering calculations and reports when I was working at an engineering company, but I want something more general purpose. I've used CL for little scripts and utilities with Portacle, and I find I am more comfortable with the Lisp way of doing things. I had used Mathlab before, so Julia's syntax is very familiar. I do like the Models.jl library.
- daniel-cussen 3y ago
  Dude Common Lisp 100%! Don't fret if you think you're mediocre. I myself have been trying to get through On Lisp since 2008. Then, after that, Let over Lambda. Not better, but v strong book, i can tell the guy while not the best at humblebragging has so much cool stuff there. ANSI Common Lisp n that's plenty to not be mediocre! I did get through the whole thing in 2009, what a great book!
  - gjvc 3y ago
    the back-cover blurb of Let over Lambda is worth reading.
  - eggy 3y ago
    Thanks for the motivation. I love Lisp, and even was into Shen[0] for a while, but Common Lisp has all the libraries and legacy tutorials and books that I will stick it out a bit more. Which matrix/math libraries do you recommend to compete with the likes of Numpy and Mojo for ML apps? Because I love APL, April, Array Programming Re-Imagined in Lisp[1]. [0] https://shenlanguage.org/ https://shenlanguage.org/ [1] https://github.com/phantomics/april https://github.com/phantomics/april
adamnemecek 3y ago
Recently, I have been working on some things that sometimes overlap with quantum computation and I have realized that the way all the quantum languages approach this wrong. If you are programming explicitly with CNOT gates, you are doing it wrong. A Python programmer doesn't care about logical gates, and neither should a quantum programmer. To that end, I'm convinced that the interplay between coinduction and induction, or coalgebra and algebra is the way forward.
- reikonomusha 3y ago
  This very well may be true, in the same sense that a Python programmer doesn't (usually) care about assembly language. But at their lowest levels, quantum computers are executing a sequence of gates, and much of the work and sophistication of a quantum compiler is to optimize said sequences for rapid and accurate execution. So while gate sequences may not be the end-game to the programmers of tomorrow, they're undoubtedly a necessary component in any software stack.
  - adamnemecek 3y ago
    I never said that they weren't. It's just that most programming language don't deal with gates as a part of their API.
    - taeric 3y ago
      This is true, but at that point, the goal would be to have a higher level language above the quantum gates. And at that point, I'd guess the code is less educational? That is, at the end of the day, something like Shor's algorithm can be reduced to some math constructs we roughly know. The speedup comes from these only being efficient using quantum gates. Implementing the code using abstract quantum gates isn't to try and compete, but to try and understand the gates and how they work at a logical level. This is like learning how boolean gates work to understand some ideas of how computers work. The only people that really think in many of those terms are the CPU designers. Teaching the next round of the designers does so by working with boolean models to get there. And you are correct that we may have other quantum constructs someday. Just like much of what goes into a CPU isn't strictly OR/AND/etc. With the way gates are wired, it can be confusing to folks as the input signal can also be seen as destroyed in the circuit, but a deterministic signal is captured on the other side. Now, the above is all from my weak intuition here. I would not be shocked to find I'm wrong on parts.
frankdejonge 3y ago
You had me until Lisp.
- mepian 3y ago
  Not everyone is using PHP, sorry. I promise that once you get past the syntax shock, Lisp is not that difficult to grok. It looks like some people here took your comment the wrong way but please don't be discouraged by that. There is a genuine lack of good Lisp outreach, compounded by trolls and bombastic essays that are high on platitudes and low on actual insight, and I'm slowly working on correcting that in my spare time.
  - macintux 3y ago
    > It looks like some people here took your comment the wrong way HN discourages low-effort snark. If someone is going to complain about Lisp, they should explain why.
robbywashere_ 3y ago
"Thanks for interviewing with us today at xyz... please click on that link I just sent you in the chat. Today we will be doing a little quantum coding question. Try to speak out loud so I know what your thinking and your thought process."
- wohlgejm 3y ago
  "Senior React Developer"
jramirezpr 3y ago
On the X gate, the more relevant identity regarding X being its own inverse is X*X=I, the other one is true for all invertible matrices
da39a3ee 3y ago
> In Common Lisp, the matrix <a 2x2 matrix with 1 2 in first row and 3 4 in second row> is written #2A((1 2) (3 4)). I do understand that the row view and column view are symmetrical in linear algebra. But nevertheless, unless I'm really getting something wrong, matrices are typically (at least in undergraduate mathematics courses) introduced as collections of _column vectors_: the matrix is a linear transformation that sends a vector into the space spanned by those column vectors. And you can see this by how common it is to define vectors to be column vectors, e.g. using x^T notation to indicate that, or saying it explicitly. So, if I'm not wrong there, why do all programming languages define matrices as collections of rows??
- reikonomusha 3y ago
  Programming languages usually have arrays, not matrices, and I think row-ordered array data has been a natural way to think in many fields (e.g., databases, finance, etc.), especially when you consider that adding a row ought to be less burdensome than adding a column in these contexts.
  - da39a3ee 3y ago
    I see, thanks I guess you're right. I'd been thinking of languages with matrices that support matrix operations but yes I think perhaps I'd been missing the point you make that it would be confusing for those to be list-of-column if list-of-row is used elsewhere in the language. It's a bit of a shame for working with matrices.

232 points by varjag 3y ago

mighmi 3y ago

Any recommendations on a textbook to understand this kind of math?

prezjordan 3y ago
Might be of use! https://quantum.country/ https://quantum.country/
- reikonomusha 3y ago
  One of the authors, Michael Nielson, also wrote the "bible" of quantum computing, as referenced in a sibling comment. The remains one of the most popular and cited introductory texts to the subject, though today there are many more options on the market.
abdullahkhalids 3y ago
Quantum Computation and Quantum Information by Nielson and Chuang is the standard textbook for quantum computing. It has excellent background chapters on linear algebra and quantum mechanics, that will get you a lot of mileage. Another book that I would recommend is Introduction to Classical and Quantum Computing by Thomas Wong. It's recent and has lots of examples, including lots of code, to show how to work with the math.
hackandthink 3y ago
Ronald de Wolf: Quantum Computing: Lecture Notes Ronald de Wolf: https://arxiv.org/abs/1907.09415 https://arxiv.org/abs/1907.09415 David Bacon: https://courses.cs.washington.edu/courses/cse599d/06wi/ https://courses.cs.washington.edu/courses/cse599d/06wi/ Scott Aaronson: https://en.wikipedia.org/wiki/Quantum_Computing_Since_Democritus https://en.wikipedia.org/wiki/Quantum_Computing_Since_Democr...
jksk61 3y ago
maybe not of your interest, but if one is more from a ML background, there's this nice book/overview by Maria Schuld and Francesco Petruccione, called Machine Learning with Quantum Computers, which is mostly regarding variational algorithm and quantum kernel machine. However, the best intro material is the one by Nielsen and Chuang. Moreover, if you feel more comfortable by running examples there are qiskit, pennylane and other libraries which shares a lot of tutorials and notebook (and some can be run on a true quantum computer if you have the money or the time to wait in queue!)

Strilanc 3y ago

The hardest part of implementing a quantum state vector simulation is understanding how the tensor product expands an n-qubit gate to apply to an m-qubit system. (A third of the linked post is dedicated to it; appropriately.) If you use a language or framework that's based on tensors to start with, things can be quite succinct (though you still need to understand the concepts). For example, in numpy, if you store the state vector in an array of shape (2,) * num_qubits, you can apply gates as one-liners using np.einsum: import numpy as np # Init 4-qubit system with all amplitude in the 0000 state. state = np.zeros(shape=(2,) * 4, dtype=np.complex64) state[(0,) * 4] = 1 # Unitary matrix of Hadamard gate H = np.array([[1, 1], [1, -1]], dtype=np.complex64) / 2**0.5 # Apply Hadamard gate to third qubit of four qubit system. state = np.einsum('XY,abXd->abYd', H, state) Here's a post explaining what np.einsum does: https://obilaniu6266h16.wordpress.com/2016/02/04/einstein-summation-in-numpy/ https://obilaniu6266h16.wordpress.com/2016/02/04/einstein-su... . In the above einsum string 'XY,abXd->abYd' the 'XY' part is naming the input and output axes of the Hadamard matrix, and the 'abXd->abYd' part is saying to multiply the matrix into the third axis of the state tensor. The notation is pretty general, able to permute and repeat axes in order to express things like traces and transposes and dot products and etc.

reikonomusha 3y ago
"einsum" in Lisp [1]. It uses S-expressions instead of strings, and compiles to native loops. [1] https://github.com/quil-lang/magicl/blob/master/src/high-level/einsum.lisp#L15 https://github.com/quil-lang/magicl/blob/master/src/high-lev...
- lionsdan 3y ago
  (Link didn't work for me) https://github.com/quil-lang/magicl/blob/master/src/high-level/einsum.lisp https://github.com/quil-lang/magicl/blob/master/src/high-lev...
jxf 3y ago
> The hardest part of implementing a quantum state vector simulation is understanding how the tensor product expands an n-qubit gate to apply to an m-qubit system. (A third of the linked post is dedicated to it; appropriately.) This feels like it could be the "git gets easier once you understand branches are homeomorphic endofunctors mapping submanifolds of a Hilbert space" of physics.

adamisntdead 3y ago

I wrote something similar a couple of years ago - https://github.com/adamisntdead/QuSimPy https://github.com/adamisntdead/QuSimPy Happy to answer any questions people have, including on other simulation methods other than state vector!

reikonomusha 3y ago
One of the aspects emphasized in TFA is being able to simulate gates of any dimension/number of qubits (like a 3-qubit Toffoli or a 5-qubit Molmer-Sorensen), instead of just 1- and 2-qubit gates. Have you thought about extending your simulator to support gates of greater than two qubits?
- adamisntdead 3y ago
  I guess back when I wrote it I didn't see the need given that single qubit gates along with CNOT are universal and they're implemented. I think airing on the side of 'as few features as is educational' was my mentality on this.
- JBits 3y ago
  I know about the conventional 2-qubit Molmer-Sorensen but not the 5-qubit version. Could I ask what it is?
  - reikonomusha 3y ago
    See e.g. equations (5) and (6) from [1], where any qubit subset of a system might undergo the action of the M–S gate. But definitely the usual presentation of the physics of M–S is on a two qubit system. [1] https://arxiv.org/abs/1601.06819 https://arxiv.org/abs/1601.06819

eggy 3y ago

I'm deciding between Common Lisp and Mojo, so maybe I will try to implement this in Mojo and compare. Anybody have any thoughts on this, since I am a mediocre Lisper and a beginning Mojo person. I am familiar with Numpy and I also program in APL and J.

Archit3ch 3y ago
May I suggest Julia? Efficient and capable of (Common Lisp style) abstractions. Unsurprisingly, there are more than a few quantum projects in the ecosystem already.
- eggy 3y ago
  I've used Julia with Pluto and Weave to create engineering calculations and reports when I was working at an engineering company, but I want something more general purpose. I've used CL for little scripts and utilities with Portacle, and I find I am more comfortable with the Lisp way of doing things. I had used Mathlab before, so Julia's syntax is very familiar. I do like the Models.jl library.
daniel-cussen 3y ago
Dude Common Lisp 100%! Don't fret if you think you're mediocre. I myself have been trying to get through On Lisp since 2008. Then, after that, Let over Lambda. Not better, but v strong book, i can tell the guy while not the best at humblebragging has so much cool stuff there. ANSI Common Lisp n that's plenty to not be mediocre! I did get through the whole thing in 2009, what a great book!
- gjvc 3y ago
  the back-cover blurb of Let over Lambda is worth reading.
- eggy 3y ago
  Thanks for the motivation. I love Lisp, and even was into Shen[0] for a while, but Common Lisp has all the libraries and legacy tutorials and books that I will stick it out a bit more. Which matrix/math libraries do you recommend to compete with the likes of Numpy and Mojo for ML apps? Because I love APL, April, Array Programming Re-Imagined in Lisp[1]. [0] https://shenlanguage.org/ https://shenlanguage.org/ [1] https://github.com/phantomics/april https://github.com/phantomics/april

adamnemecek 3y ago

Recently, I have been working on some things that sometimes overlap with quantum computation and I have realized that the way all the quantum languages approach this wrong. If you are programming explicitly with CNOT gates, you are doing it wrong. A Python programmer doesn't care about logical gates, and neither should a quantum programmer. To that end, I'm convinced that the interplay between coinduction and induction, or coalgebra and algebra is the way forward.

reikonomusha 3y ago
This very well may be true, in the same sense that a Python programmer doesn't (usually) care about assembly language. But at their lowest levels, quantum computers are executing a sequence of gates, and much of the work and sophistication of a quantum compiler is to optimize said sequences for rapid and accurate execution. So while gate sequences may not be the end-game to the programmers of tomorrow, they're undoubtedly a necessary component in any software stack.
- adamnemecek 3y ago
  I never said that they weren't. It's just that most programming language don't deal with gates as a part of their API.
  - taeric 3y ago
    This is true, but at that point, the goal would be to have a higher level language above the quantum gates. And at that point, I'd guess the code is less educational? That is, at the end of the day, something like Shor's algorithm can be reduced to some math constructs we roughly know. The speedup comes from these only being efficient using quantum gates. Implementing the code using abstract quantum gates isn't to try and compete, but to try and understand the gates and how they work at a logical level. This is like learning how boolean gates work to understand some ideas of how computers work. The only people that really think in many of those terms are the CPU designers. Teaching the next round of the designers does so by working with boolean models to get there. And you are correct that we may have other quantum constructs someday. Just like much of what goes into a CPU isn't strictly OR/AND/etc. With the way gates are wired, it can be confusing to folks as the input signal can also be seen as destroyed in the circuit, but a deterministic signal is captured on the other side. Now, the above is all from my weak intuition here. I would not be shocked to find I'm wrong on parts.

frankdejonge 3y ago

You had me until Lisp.

mepian 3y ago
Not everyone is using PHP, sorry. I promise that once you get past the syntax shock, Lisp is not that difficult to grok. It looks like some people here took your comment the wrong way but please don't be discouraged by that. There is a genuine lack of good Lisp outreach, compounded by trolls and bombastic essays that are high on platitudes and low on actual insight, and I'm slowly working on correcting that in my spare time.
- macintux 3y ago
  > It looks like some people here took your comment the wrong way HN discourages low-effort snark. If someone is going to complain about Lisp, they should explain why.

robbywashere_ 3y ago

"Thanks for interviewing with us today at xyz... please click on that link I just sent you in the chat. Today we will be doing a little quantum coding question. Try to speak out loud so I know what your thinking and your thought process."

wohlgejm 3y ago
"Senior React Developer"

jramirezpr 3y ago

On the X gate, the more relevant identity regarding X being its own inverse is X*X=I, the other one is true for all invertible matrices

da39a3ee 3y ago

> In Common Lisp, the matrix <a 2x2 matrix with 1 2 in first row and 3 4 in second row> is written #2A((1 2) (3 4)). I do understand that the row view and column view are symmetrical in linear algebra. But nevertheless, unless I'm really getting something wrong, matrices are typically (at least in undergraduate mathematics courses) introduced as collections of _column vectors_: the matrix is a linear transformation that sends a vector into the space spanned by those column vectors. And you can see this by how common it is to define vectors to be column vectors, e.g. using x^T notation to indicate that, or saying it explicitly. So, if I'm not wrong there, why do all programming languages define matrices as collections of rows??

reikonomusha 3y ago
Programming languages usually have arrays, not matrices, and I think row-ordered array data has been a natural way to think in many fields (e.g., databases, finance, etc.), especially when you consider that adding a row ought to be less burdensome than adding a column in these contexts.
- da39a3ee 3y ago
  I see, thanks I guess you're right. I'd been thinking of languages with matrices that support matrix operations but yes I think perhaps I'd been missing the point you make that it would be confusing for those to be list-of-column if list-of-row is used elsewhere in the language. It's a bit of a shame for working with matrices.