Using programming frameworks, such as IBM’s Qiskit and Microsoft’s Q#, people can write quantum programs and execute them on classical simulators or real quantum computers. However, program testing and debugging, which have been studied for a long time in classical computing, are still at a very early stage for quantum computing. The reason is that these activities turn out to be surprisingly challenging on quantum computers. This blog post presents our initial effort to tackle these challenges. It is a summary of our paper, Projection-based Runtime Assertions for Testing and Debugging Quantum Programs, named a Distinguished Paper at SPLASH/OOPSLA 2020.

The Problem of Quantum Program Testing

Our work revisits assertions, one of the basic program testing and debugging approaches, and applies it to quantum programs. Designing quantum program assertions is challenging for two reasons.

1. Very large, complex quantum state. The state of a quantum system consisting of n qubits is represented by a state vector of size , or a density matrix of size , because a quantum state can be in a superposition of at most classical states for n qubits. How to express the predicate of a quantum state is a question. The classical language employed by previous quantum program assertions (Statistical Assertion, Dynamic Assertion) can only express very few types of quantum states and a large number of complex intermediate states cannot be asserted.
2. Destructive measurement. You need to measure the quantum system to extract information about the tested state, but the measurement operation affects the state. Measuring a quantum state which is a superposition of many classical states returns just one of these states, and collapses the superposition to that state. As such, single measurements do not characterize the full superposition, and destroy it in the process.

Considering the two obstacles above, we set two objectives for our assertion design.

1. Strong expressive power. The assertion language should have a strong expressive power and can express a wide range of predicates.
2. High checking efficiency. The satisfaction of the assertion predicates can be checked upon a small number of measurements/executions.

Traditionally, physicists employ a protocol called quantum state tomography to test an unknown quantum state. This protocol can theoretically check any state but its running time increases exponentially in the number of qubits.

(Note: For readers who would like to learn more about quantum computing, to expand on and solidify the concepts just mentioned, we recommend the interactive essays at quantum.country.)

Projection-based Runtime Assertions

In our OOPSLA’20 paper, we proposed a new kind of assertion, in which predicates are expressed using projections.

Projections are special linear operators in a Hilbert space — the “home” of quantum states. A projection operator will map a state into a linear subspace. Each projection operator corresponds to a unique subspace, which acts as a predicate: When a state is in the subspace of the projection, we can say that the state satisfies the projection.

Expressive. A projection-based assertion predicate language is highly expressive compared with previous classical languages. All projections formulate an orthomodular lattice. The assertion languages in previous works (Statistical Assertion, Dynamic Assertion) can only express a few elements in the lattice while projections can express all of its elements.

For example, suppose we are simulating the state of two electrons on three orbitals. When the number of electrons is conserved, we know that a valid state must be in the subspace spanned by . Here, each qubit represents one orbital and the values x=1 and x=0 represent if the orbital is occupied by an electron or not, respectively. Therefore a valid state must have two 1’s in the 3-bit string, which can be expressed by the assertion

.

Efficient and Non-destructive. Checking a projection-based predicate can be very efficient. For the projection in an assertion predicate, we can construct a two-output projective measurement. In this constructed measurement, if the tested state satisfies the projection (in the corresponding subspace), the measurement outcome is always true and the post-measurement state is the original state (before the measurement) with probability 1 because a projection operator has no effect on a state that is already in its subspace. If not, we will observe a false outcome and know that the tested state is not what we expect. A possible case remaining is that the tested state does not satisfy the projection but it has some components in the subspace of the predicate. In this case we can observe both true and false outcomes at different testing executions. Different from a direct -output measurement which requires many iterations to fully reconstruct the tested state, we can be highly confident that the assertion predicate is satisfied in a two-output measurement using just a few measurements.

Implementation Issues

To execute the projection-based assertions on a quantum computer, there are still two practical implementation issues that must be addressed. These two issues come from the constraints of physical quantum computers.

• Limited measurement basis. On a physical quantum computer, only measurement along a specific basis called the computational basis is directly supported. But the projection in an assertion may result in measurement not along the computational basis.

• Dimension mismatch. The subspaces of the projections can have different dimensions but only those with the dimension of 2 to the power of an integer can be directly implemented by measuring an integer number of qubits (and we cannot measure a fraction number of qubits.)

For the first issue, the compiler can  rotate the basis through an additional operation. Then after the measurement it can rotate things back to recover the correct program state. For the second issue, the compiler can construct the target projection by two larger projections without the dimension mismatch or augment the original Hilbert space by introducing auxiliary qubit. Then checking one assertion is transformed to checking an array of derived assertions without changing the semantics.

After these transformations, all projection-based assertions will become executable on physical quantum computers.

Conclusions and Next Steps

To facilitate practical quantum program runtime testing and debugging, we studied how to design and implement effective and efficient quantum program assertions. We selected projections as predicates because of their logical expressive power and the ability to check them efficiently at runtime.

Currently the proposed transformations can generate multiple, functionally equivalent assertion implementations with different overhead. This transformation procedure (compilation) can be further optimized to find low-overhead implementations for several possible objectives like gate count and circuit depth.

It is also possible to relax the assertion predicates to find their sound yet easy-to-implement approximations. The degree of predicate relaxation and its effect on the robustness of the assertions in realistic erroneous program debugging need to be studied.

Generally speaking, there is substantial opportunity to explore new language designs and compilation strategies for quantum programs. It’s a rich, exciting area!

Bio: Gushu Li is a fourth-year Ph.D. student at University of California, Santa Barbara. Li Zhou is a Postdoc Scholar at Max Planck Institute for Software Systems. Nengkun Yu is a Faculty member and Mingsheng Ying is a Distinguished Professor and Research Director of the Center for Quantum Software and Information at the University of Technology Sydney. Yufei Ding is an Assistant Professor at Computer Science Department and Yuan Xie is a Professor at Electrical and Computer Engineering Department at University of California, Santa Barbara.

Disclaimer: These posts are written by individual contributors to share their thoughts on the SIGPLAN blog for the benefit of the community. Any views or opinions represented in this blog are personal, belong solely to the blog author and do not represent those of ACM SIGPLAN or its parent organization, ACM.