A tutorial quantum interpreter in 150 lines of Lisp

https://www.stylewarning.com/posts/quantum-interpreter/

by varjag • 3 years ago

232 44 3 years ago

stylewarning.com

mighmi• 3 years ago

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

prezjordan• 3 years ago

Might be of use! https://quantum.country/

reikonomusha6• 3 years 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• 3 years 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• 3 years ago

Ronald de Wolf: Quantum Computing: Lecture Notes

Ronald de Wolf:

https://arxiv.org/abs/1907.09415

David Bacon:

https://courses.cs.washington.edu/courses/cse599d/06wi/

Scott Aaronson:

https://en.wikipedia.org/wiki/Quantum_Computing_Since_Democr...

jksk61• 3 years 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• 3 years 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-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.

reikonomusha6• 3 years 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-lev...

lionsdan• 3 years ago

(Link didn't work for me)

https://github.com/quil-lang/magicl/blob/master/src/high-lev...

jxf• 3 years 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.

consilient• 3 years ago

It's not, tensor products are of fundamental importance in QM. Understanding them is a hard requirement.

gcr• 3 years ago

Quantum Country does a good job of explaining the fundamentals like “what is a Hadamard gate”! Highly recommended: https://quantum.country/

adamisntdead2• 3 years ago

I wrote something similar a couple of years ago - https://github.com/adamisntdead/QuSimPy

Happy to answer any questions people have, including on other simulation methods other than state vector!

reikonomusha6• 3 years 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?

adamisntdead2• 3 years 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• 3 years ago

I know about the conventional 2-qubit Molmer-Sorensen but not the 5-qubit version. Could I ask what it is?

eggy3• 3 years 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• 3 years 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.

eggy3• 3 years 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• 3 years 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• 3 years ago

the back-cover blurb of Let over Lambda is worth reading.

eggy3• 3 years 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/

[1] https://github.com/phantomics/april

adamnemecek6• 3 years 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.

reikonomusha6• 3 years 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.

adamnemecek6• 3 years 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.

miguelmurca• 3 years ago

Maybe not your point, but a lot of programmers like to take this as "I should invent the Python of quantum computing", which is just about as silly as trying to approach anyone in 1960 and telling them they shouldn't be thinking about electronics at all.

082349872349872• 3 years ago

the interplay between ... coalgebra and algebra

If you have not already seen it, you may be interested in Squiggol (to get an idea of its age, it probably had some indirect influence upon Python)

cf Charity: https://prism.ucalgary.ca/server/api/core/bitstreams/756b50a...

adamnemecek6• 3 years ago

I have seen Charity yes, total functional programming is the future.

billti• 3 years ago

(disclaimer: I work on the team developing Q# and its tooling)

That's part of the goal of Q#. It's designed to be a language which allows you to build up from quantum gates, efficiently work with quantum concepts such as 'adjoint' and 'controlled' operations, and build that up into a higher level of abstraction. You can see an old post as to some of the reasoning when it was first developed at <https://devblogs.microsoft.com/qsharp/why-do-we-need-q/>.

Another consideration to some of the points raised here, is that even on today's state-of-the-art hardware you typically only get a couple thousand gates at best before noise overwhelms the system and the qubits 'decohere' (https://en.wikipedia.org/wiki/Quantum_decoherence). So you do often want to develop at a level where you can squeeze every last gate out of whatever program you're writing. (If you intend to run it on a quantum computer and not just simulations).

Being that the post is about quantum simulation, you can see the one our team built in Rust at https://github.com/qir-alliance/qir-runner/blob/main/sparses... . This uses 'sparse' simulation, which means any state with a probability of 0 isn't tracked, which turns out to be quite a few in a lot of algorithms. This allows you to simulate many more qubits than you can with a full state simulator (where you need to track 2^n states for n qubits). It also does some other nifty tricks where you can elide or combine gates before they are performed to get even more perf. We use it in our new Q# stack (https://github.com/microsoft/qsharp) to run program simulations in our CLI or in the browser (such as on our new https://quantum.microsoft.com site), or inside VS Code (desktop or web)).

We are looking to evolve the Q# language and improve the quantum development experience, with a focus given to a 'scalable' quantum future where gate count and noise is less of a limit, and moving development higher up in abstraction - as you outline. So if it is something you have an interest in, we're more than happy to get the input on the qsharp GitHub repo linked to above.

adamnemecek6• 3 years ago

TBH I was never quite sold qubits. Is analog quantum out of the question?

frankdejonge• 3 years ago

You had me until Lisp.

mepian• 3 years 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• 3 years 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_• 3 years 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• 3 years ago

"Senior React Developer"

jramirezpr• 3 years 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

da39a3ee2• 3 years 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??

reikonomusha6• 3 years 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.

da39a3ee2• 3 years 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.

A tutorial quantum interpreter in 150 lines of Lisp

Related Stories