We introduce an abstract machine architecture for classical/quantum computations---including compilation---along with a quantum instruction language called Quil for explicitly writing these computations. With this formalism, we discuss concrete implementations of the machine and non-trivial algorithms targeting them. The introduction of this machine dovetails with ongoing development of quantum computing technology, and makes possible portable descriptions of recent classical/quantum algorithms.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
This is a great question! I've worked a lot on this topic and its crucial to understanding how quantum computers will be used in the near term.
While I don't have an easy answer for the high level interface, the assembly level interface between quantum and classical computing is also important. If you're interested in that then you should check out this paper where we describe Quil, an instruction set architecture for hybrid quantum/classical computing based on shared memory: https://arxiv.org/abs/1608.03355
This instruction set is the basis for Rigetti Computing's Forest quantum programming environment: https://www.rigetti.com/forest
We have a Python library called pyQuil [1] for writing high-level programs for quantum computers. The "assembly" you mentioned is Quil [2], which we don't expect most users to use directly.
Other high-level languages for quantum computing include LIQUi|> [3] and Quipper [4]. Each approach has it's strengths, but we believe Quil/pyQuil is the best choice for near-term applications. See the Quil paper [5] for more details.
[1]: https://pyquil.readthedocs.io/en/latest/
[2]: https://medium.com/@rigetticomputing/introducing-quil-a-prac...
[3]: https://www.microsoft.com/en-us/research/project/language-in...
[4]: http://www.mathstat.dal.ca/~selinger/quipper/
[5]: https://arxiv.org/pdf/1608.03355.pdf
The computing model is given by Quil [0]. Section III-F talks about exactly this idea of "measurement-for-effect". You can use measurement in Quil as a way to project into a state that you want. (You can even use a conditional instruction to get feedback and flip it with an X if it measures into an undesired state.)
[0] https://arxiv.org/abs/1608.03355
They did say "Look for the source for the code soon ..." so I'm guessing it's coming.
You can see some example code in the paper though: http://arxiv.org/abs/1608.03355
That's my doing.
When we started thinking about quantum programming languages, we didn't know what they should look like. Experimenting with different languages efficiently requires a language that makes language-building easy. I find that there are two classes of languages that provide that: Lisp-likes with metaprogramming and ML-likes with a good type system including algebraic data types.
Quil [0], our quantum instruction language, came out of language experimentation in Lisp. In fact, the Quil code:
H 0
CNOT 0 1
MEASURE 0 [0]
used to look like this:
((H 0)
(CNOT 0 1)
(MEASURE 0 (ADDRESS 0)))
This was a no-hassle way to play around without thinking about how…
Read the full comment
to wrangle lex and yacc with shift/shift and shift/reduce issues. If you've ever used them, it takes a while to get what you want, and integrate it into a product you're trying to create.
In addition to the need to construct languages, we also needed to simulate/interpret the language. Simulating the evolution of a quantum state is very expensive (which is why we are building quantum computers!), and is usually relegated to some closer-to-metal language like C.
Unfortunately, in C, high-speed numerical code (that is also blazing fast) is very difficult to experiment with, extend, maintain, etc.
Fortunately, over the past 30 years, Lisp compilers have become excellent at producing native machine code. With a compiler like SBCL [1], you can produce code which is very nearly optimal. For example, we have a function to compute the probability from a wavefunction amplitude. Here it is:
> (disassemble #'probability)
; disassembly for PROBABILITY
; Size: 90 bytes. Origin: #x22B67F5A
; 5A: F20F104901 MOVSD XMM1, [RCX+1]
; 5F: F20F105109 MOVSD XMM2, [RCX+9]
; 64: F20F59C9 MULSD XMM1, XMM1
; 68: F20F59D2 MULSD XMM2, XMM2
; 6C: F20F58D1 ADDSD XMM2, XMM1
; ...
There's some additional code that follows, but it disappears because this function is also inlined at the call sites.
Writing the QVM and associated compiler in Lisp has allowed us to move fast. The code is compact, extremely robust, and extremely fast.
I could say a lot more about this, but that's the gist of why we thought it was a sensible decision.
[0] https://arxiv.org/abs/1608.03355
[1] http://www.sbcl.org/
Rigetti's quantum computers can be operated by way of the means discussed by other commenters (toothpicks and tweezers at the oscilloscope), or can be loaded with a quantum instruction code called Quil [0], which can be written with Python using pyQuil [1,2]. The former is preferred by physicists doing physics experiments, and the latter by software engineers and application developers.
[0] https://arxiv.org/pdf/1608.03355.pdf
[1] http://forest.rigetti.com/
[2] https://github.com/rigetticomputing/pyQuil
Unfortunately, a language like QCL is a bit far away from being a practical language for quantum computers, in the sense that it will be difficult to use on upcoming machines. QCL is of course perfectly fit for experimentation. In my opinion, when you have a quantum computer that has resources akin to a classical computer with RAM measured in tens of bits with stable lifetimes measured in tens of microseconds, using a language that is similar to C gives you a somewhat wrong impression of what you're able to do. While not universally true with C programming, C often abstracts away the idea of finite memory/stack/etc. This is generally a good idea when resources are…
Read the full comment
plentiful. But this very sharply contrasts with near-term quantum computers. Of course, just as with C, one could imagine compiling QCL into a simpler language, with the expectation that QCL programmers can intuit what the compiler will produce as "machine code".
As discussed in a recent paper [1][2], it's pragmatic to think of quantum computation in a coprocessor model. QCL takes a different approach: a high-level language that has a quantum datatype in the midst of the traditional classical datatypes along with their plethora of classical operations. I think that cordoning off the quantum computation as much as possible into a separate processing unit will make eventual adoption much easier. It also makes integration with existing languages much easier. QCL doesn't preclude this idea, but having a quantum coprocessor model implicitly manifest in QCL makes its implementation very difficult.
[1] https://arxiv.org/abs/1608.03355
[2] https://news.ycombinator.com/item?id=12277552
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
In honor of Alan Turing's hundredth birthday, I unwisely set out some thoughts about one of Turing's obsessions throughout his life, the question of physics and free will.