We present a new technique for accelerating quantum program testing. Given a quantum circuit with an input/output specification, our goal is to check whether executing the program on the input state produces the expected output. In quantum computing, however, it is impossible to directly check the equivalence of the two quantum states. Instead, we rely on statistical testing, which involves repeated program executions, state measurements, and subsequent comparisons with the specified output. To guarantee a high level of assurance, however, this method requires an extensive number of measurements. In this paper, we propose a solution to alleviate this challenge by adapting Fixed-Point Amplitude Amplification (FPAA) for quantum program testing. We formally present our technique, demonstrate its ability to reduce the required number of measurements as well as runtime cost without sacrificing the original statistical guarantee, and showcase its runtime effectiveness through case studies.
We present a new technique for accelerating quantum program testing. Given a quantum circuit with an input/output specification, our goal is to check whether executing the program on the input state produces the expected output. In quantum computing, however, it is impossible to directly check the equivalence of the two quantum states. Instead, we rely on statistical testing, which involves repeated program executions, state measurements, and subsequent comparisons with the specified output. To guarantee a high level of assurance, however, this method requires an extensive number of measurements. In this paper, we propose a solution to alleviate this challenge by adapting Fixed-Point Amplitude Amplification (FPAA) for quantum program testing. We formally present our technique, demonstrate its ability to reduce the required number of measurements as well as runtime cost without sacrificing the original statistical guarantee, and showcase its runtime effectiveness through case studies.
Mutation testing assesses test suites by introducing program changes and checking whether tests detect them. In quantum programs, a surviving mutant may leave program behavior unchanged, produce a change hidden by the chosen input or measurement, or remain undetected because statistical evidence is insufficient. We develop a circuit-aware framework to distinguish these causes and guide execution planning and test changes. The framework covers ideal, noiseless programs and mutations that replace one gate or subcircuit. The method traces how a mutation can affect measured outputs and combines established mathematical checks with statistical estimates. For supported cases, we establish conditions under which a test cannot reveal a mutation and exact formulas for its effect when the required state information is available. Under stated assumptions, we bound the mutation score while retaining surviving and unresolved mutants, and identify a restricted circuit family whose mutation effects admit efficient classical classification. The deliverables include a decision procedure, mathematical guarantees, worked examples of test changes and their implementation requirements, and a small-circuit reference implementation for differential expectation tests. These results help testers decide what to execute, what to change, and what remains unknown. The evidence is limited to proofs and executable examples under the ideal model.
When a bug is detected by testing a quantum program on a quantum computer, we want to determine its location to fix it. To locate the bug, the quantum program is divided into several segments, and each segment is tested. However, to prepare a quantum state that is input to a segment, it is necessary to execute all the segments ahead of that segment in a quantum computer. This means that the cost of testing each segment depends on its location. We can also locate a buggy segment only if it is confirmed that there are no bugs in all segments ahead of that buggy segment. Since a quantum program is tested statistically on the basis of measurement results, there is a tradeoff between testing accuracy and cost. These characteristics are unique to quantum programs and complicate locating bugs. We propose an efficient bug-locating method consisting of four approaches, i.e., cost-based binary search, early determination, finalization, and looking back, which take these characteristics into account. We present experimental results indicating that the proposed method can reduce bug-locating cost, represented as the number of executed quantum gates, compared with naive methods that do not use the four approaches. The limitations and usefulness of the proposed method are also discussed on the basis of the experimental results.
In this paper, we propose Proq, a runtime assertion scheme for testing and debugging quantum programs on a quantum computer. The predicates in Proq are represented by projections (or equivalently, closed subspaces of the state space), following Birkhoff-von Neumann quantum logic. The satisfaction of a projection by a quantum state can be directly checked upon a small number of projective measurements rather than a large number of repeated executions. On the theory side, we rigorously prove that checking projection-based assertions can help locate bugs or statistically assure that the semantic function of the tested program is close to what we expect, for both exact and approximate quantum programs. On the practice side, we consider hardware constraints and introduce several techniques to transform the assertions, making them directly executable on the measurement-restricted quantum computers. We also propose to achieve simplified assertion implementation using local projection technique with soundness guaranteed. We compare Proq with existing quantum program assertions and demonstrate the effectiveness and efficiency of Proq by its applications to assert two ingenious quantum algorithms, the Harrow-Hassidim-Lloyd algorithm and Shor's algorithm.
We present a technique to reduce the error probability of quantum algorithms that determine whether its input has a specified property of interest. The standard process of reducing this error is statistical processing of the results of multiple independent executions of an algorithm. Denoting by $\ensuremath{\rho}$ an upper bound of this probability (wlog; assume $\ensuremath{\rho}\ensuremath{\le}\frac{1}{2}$), classical techniques require $O(\frac{\ensuremath{\rho}}{{[(1\ensuremath{-}\ensuremath{\rho})\ensuremath{-}\ensuremath{\rho}]}^{2}})$ executions to reduce the error to a negligible constant. We investigate when and how quantum algorithmic techniques like amplitude amplification and estimation may reduce the number of executions. On one hand, the former idea does not directly benefit algorithms that can err on both yes and no answers and the number of executions in the latter approach is $O(\frac{1}{(1\ensuremath{-}\ensuremath{\rho})\ensuremath{-}\ensuremath{\rho}})$. We propose a quantum approach called amplitude separation that combines both these approaches and achieves $O(\frac{1}{\sqrt{1\ensuremath{-}\ensuremath{\rho}}\ensuremath{-}\sqrt{\ensuremath{\rho}}})$ executions, which betters existing approaches when the errors are high. In the multiple-weight decision problem, the input is an n-bit Boolean function f() given as a black box and the objective is to determine the number of x for which f(x)=1, denoted wt(f), given some possible values w1,...,wk for wt(f). When our technique is applied to this problem, we obtain the correct answer, maybe with a negligible error, using O(log2k2n) calls to f(), which shows a quadratic speedup over classical approaches and currently known quantum algorithms.
Quantum software testing is important for reliable quantum software engineering. Despite recent advances, existing quantum software testing approaches rely on simple test inputs and statistical oracles, costly program specifications, and limited validation on real quantum computers. To address these challenges, we propose SB-QOPS, a search-based quantum program testing approach via commuting Pauli strings. SB-QOPS, as a direct extension to a previously proposed QOPS approach, redefines test cases in terms of Pauli strings and introduces a measurement-centric oracle that exploits their commutation properties, enabling effective testing of quantum programs while reducing the need for full program specifications. By systematically exploring the search space through an expectation-value-based fitness function, SB-QOPS improves test budget utilization and increases the likelihood of uncovering subtle faults. We conduct a large-scale empirical evaluation on quantum circuits of up to 29 qubits on real quantum computers and emulators. We assess three search strategies: Genetic Algorithm, Hill Climbing, and the (1+1) Evolutionary Algorithm, and evaluate SB-QOPS under both simulated and real noisy conditions. Experiments span three quantum computing platforms: IBM, IQM, and Quantinuum. Results show that SB-QOPS significantly outperforms QOPS, achieving a fault-detection score of 100% for circuits up to 29 qubits, and demonstrating portability across quantum platforms.
Quantum computing (QC) promises polynomial and exponential speedups in many domains, such as unstructured search and prime number factoring. However, quantum programs yield probabilistic outputs from exponentially growing distributions and are vulnerable to quantum-specific faults. Existing quantum software testing (QST) approaches treat quantum superpositions as classical distributions. This leads to two major limitations when applied to quantum programs: (1) an exponentially growing sample space distribution and (2) failing to detect quantum-specific faults such as phase flips. To overcome these limitations, we introduce a QST approach, which applies a reduction algorithm to a quantum program specification. The reduced specification alleviates the limitations (1) by enabling faster sampling through quantum parallelism and (2) by performing projective measurements in the mixed Hadamard basis. Our evaluation of 143 quantum programs across four categories demonstrates significant improvements in test runtimes and fault detection with our reduction approach. Average test runtimes improved from 169.9 s to 11.8 s, with notable enhancements in programs with large circuit depths (383.1 s to 33.4 s) and large program specifications (464.8 s to 7.7 s). Furthermore, our approach increases mutation scores from 54.5% to 74.7% , effectively detecting phase flip faults that non-reduced specifications miss. These results underline our approach's importance to improve QST efficiency and effectiveness.