What makes quantum computing powerful is the ability to stop computations partway

What is it about?

Programming languages are designed with a particular view of what computation is all about. For example functions, simulation, or logic. Physics regards computation as a way to model physical processes. Such processes are reversible in that they can always be undone without harm to the input, until the moment of observation. Many existing programming languages can be extended to model classical physics relatively easily. What is the new ingredient needed to go from classical to quantum computing? This research shows that it is the ability to stop some computations partway. A bit more precisely, quantum computations are traditionally formulated as circuits of gates. To understand them, you need to know all sorts of details about matrices, as well as a kind of numbers called complex numbers. This research gives an alternative way to program and understand quantum computers. As before, start with reversible classical computing and the ability to combine gates into circuits. Add to that a square root of the classical NOT gate (which flips a 0 into a 1 and vice versa): this is a new gate, and doing it twice performs the NOT gate. Essentially it starts to flip a bit, but stops halfway. Now replace all of the complex numbers by a single number such that if you multiply it by itself eight times, you get 1. This can also be seen as multiplying by 1, but stopping an eighth of the way there. This work shows that imposing a single, simple equation on this new gate and this new number makes them behave very well. In fact, the programming language we have now built is universal (you can approximate any quantum computation with arbitrary accuracy), and anything you can prove about these computations using matrices you can prove using just the equations of classical programs and our new equation! So you can program quantum computers, and prove things about quantum programs, without ever knowing anything about matrices.

Featured Image

Photo by Michael Dziedzic on Unsplash

Photo by Michael Dziedzic on Unsplash

Why is it important?

Because quantum programs are so hard to understand, it is very important to guarantee that they do what the programmer intends. An extra nice property of the programming language we present is that two programs are equal exactly when their matrices are equal. So not only does the language explain quantum computing without matrices, you do not even need to know matrices to make programs better without changing their meaning. This is the first work that accomplishes handling quantum programming this way with equations only. Computer algebra is much better at equations than numbers, so this makes reasoning about quantum programs much simpler for computers to do.