Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Proceedings of the ACM on Programming Languages

Statistical Testing of Quantum Programs via Fixed-Point Amplitude Amplification

Chan Gu Kang, Joonghoon Lee, Hakjoo Oh

Published Oct 8, 2024• 6 citations
Publisher

Abstract

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.

DOI
10.1145/3689716

Related papers

Statistical Hypothesis Testing for Efficient Black-Box Quantum Program Testing

Tiancheng Jin, Bo Yang, Haibo Yu +1 more

Quantum computing offers exponential computational advantages across diverse application domains, yet the inherent probabilistic nature of quantum measurements poses challenges for program testing. Existing quantum black-box testing approaches rely on ad-hoc tolerance checks applied to empirical probability distributions estimated from large measurement samples, often requiring a large number of measurements, because of lacking formal Type I error control, power guarantees, or principled sample size determination. We present a statistical hypothesis-testing method for quantum program testing, encompassing two paradigms: marginal probability testing and joint distribution testing over the full$2^{d}$-dimensional state space. By combining exact and asymptotic tests, bootstrap procedures, sequential designs, and kernel-based two-sample testing, our method provides rigorous error control with substantially improved sample efficiency. Experiments on quantum programs with 2 to 12 qubits show measurement reductions from 97 to 99 percent over the conventional practice of ten thousand shots against strong synthetic faults. A structural mutation study separates the faults that every test detects at one hundred measurements from those that no measurement-based test can detect. The exact marginal test, the exact branch of the sequential design, and the permutation-calibrated joint tests control the Type I error rate at or below the nominal level of 0.05. The adaptive chi-square branch is mildly anticonservative on random states, with a median of 0.060, and conservative on the named benchmarks. On QFT, the sequential design rejects a faulty program with 32 to 85 percent fewer measurements than a properly powered fixed-sample test at two to twelve qubits on its adaptive branch, and with 19 to 60 percent fewer on its exact branch, which is valid under any dependence and reaches the target power from four qubits upward. Power exceeds 0.80 above a characterized fault strength, and faults that preserve the output distribution are shown to be undetectable by any measurement-based test. These results establish a principled and practical foundation for quantum program testing.

IEEE Access•Jan 1, 2026•0 citations

Toward Circuit-Aware Mutation Testing for Quantum Programs: Exact Visibility and Execution Planning

Andriy Miranskyy, Jose Campos

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.

cs.SECross-listedarXiv:2610.36976•Oct 28, 2026•0 citations

Bug-Locating Method Based on Statistical Testing for Quantum Programs

Naoto Sato, Ryota Katsube

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.

arXiv:2409.20011•IEEE Transactions on Software Engineering•Aug 8, 2025•4 citations

A Dynamic Test Oracle for Quantum Programs With Separable Output States

Yuechen Li, Kai-Yuan Cai, Beibei Yin

As quantum software engineering advances, testing techniques are required to assess the quality of quantum programs (QPs). In the test process, the test oracle is vital for determining whether the test result indicates a success or a failure. Most related works directly measure the output states and acquire the corresponding test results by comparing the output distribution with the expected one. While attention has been paid to the capability of fault detection, the guarantee for the correctness of the produced test results remains limited. Unlike classical programs (CPs), the output quantum states of QPs should be transformed into probabilistic classical outcomes through quantum measurement. This additional operation of measurement could cause a test oracle to yield the wrong test results. Especially for high-dimensional output spaces, numerous measurement outcomes are required to capture the distribution characteristics, threatening the effectiveness and cost-efficiency of test oracles. Hence, this paper proposes a novel specified test oracle DOSS employing a dynamic scheme to integrate a quantum algorithm (i.e., swap test) with the direct measurement mode. This innovative approach enables the validation of individual outputs rather than their distribution during the testing phase. Considering acceptable cost, DOSS decomposes the fully or partially separable output states to lower the dimensionality and simplify the quantum circuit for testing. Empirical studies demonstrate that DOSS generally gives more correct test results than baselines, and maintains reasonable cost on an ideal simulator. Besides, DOSS’s effectiveness with quantum noise involved is validated via three noisy simulators.

IEEE Transactions on Software Engineering•Mar 4, 2026•2 citations

Search-Based Quantum Program Testing via Commuting Pauli String

Asmar Muqeet, Shaukat Ali, Paolo Arcaini

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.

arXiv:2602.11487•Feb 12, 2026•0 citations

Error reduction of quantum algorithms

Debajyoti Bera, P. V. Tharrmashastha

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(\phantom{\rule{0.16em}{0ex}})$ 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 ${{w}_{1},...,{w}_{k}}$ for $wt(f)$. When our technique is applied to this problem, we obtain the correct answer, maybe with a negligible error, using $O({log}_{2}k\sqrt{{2}^{n}})$ calls to $f(\phantom{\rule{0.16em}{0ex}})$, which shows a quadratic speedup over classical approaches and currently known quantum algorithms.

arXiv:1902.06852•Physical Review A•Jul 19, 2019•2 citations
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.
Quantum computing offers exponential computational advantages across diverse application domains, yet the inherent probabilistic nature of quantum measurements poses challenges for program testing. Existing quantum black-box testing approaches rely on ad-hoc tolerance checks applied to empirical probability distributions estimated from large measurement samples, often requiring a large number of measurements, because of lacking formal Type I error control, power guarantees, or principled sample size determination. We present a statistical hypothesis-testing method for quantum program testing, encompassing two paradigms: marginal probability testing and joint distribution testing over the full2d2^{d}2d-dimensional state space. By combining exact and asymptotic tests, bootstrap procedures, sequential designs, and kernel-based two-sample testing, our method provides rigorous error control with substantially improved sample efficiency. Experiments on quantum programs with 2 to 12 qubits show measurement reductions from 97 to 99 percent over the conventional practice of ten thousand shots against strong synthetic faults. A structural mutation study separates the faults that every test detects at one hundred measurements from those that no measurement-based test can detect. The exact marginal test, the exact branch of the sequential design, and the permutation-calibrated joint tests control the Type I error rate at or below the nominal level of 0.05. The adaptive chi-square branch is mildly anticonservative on random states, with a median of 0.060, and conservative on the named benchmarks. On QFT, the sequential design rejects a faulty program with 32 to 85 percent fewer measurements than a properly powered fixed-sample test at two to twelve qubits on its adaptive branch, and with 19 to 60 percent fewer on its exact branch, which is valid under any dependence and reaches the target power from four qubits upward. Power exceeds 0.80 above a characterized fault strength, and faults that preserve the output distribution are shown to be undetectable by any measurement-based test. These results establish a principled and practical foundation for quantum program testing.
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.
As quantum software engineering advances, testing techniques are required to assess the quality of quantum programs (QPs). In the test process, the test oracle is vital for determining whether the test result indicates a success or a failure. Most related works directly measure the output states and acquire the corresponding test results by comparing the output distribution with the expected one. While attention has been paid to the capability of fault detection, the guarantee for the correctness of the produced test results remains limited. Unlike classical programs (CPs), the output quantum states of QPs should be transformed into probabilistic classical outcomes through quantum measurement. This additional operation of measurement could cause a test oracle to yield the wrong test results. Especially for high-dimensional output spaces, numerous measurement outcomes are required to capture the distribution characteristics, threatening the effectiveness and cost-efficiency of test oracles. Hence, this paper proposes a novel specified test oracle DOSS employing a dynamic scheme to integrate a quantum algorithm (i.e., swap test) with the direct measurement mode. This innovative approach enables the validation of individual outputs rather than their distribution during the testing phase. Considering acceptable cost, DOSS decomposes the fully or partially separable output states to lower the dimensionality and simplify the quantum circuit for testing. Empirical studies demonstrate that DOSS generally gives more correct test results than baselines, and maintains reasonable cost on an ideal simulator. Besides, DOSS’s effectiveness with quantum noise involved is validated via three noisy simulators.
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.
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 nnn-bit Boolean function f()f(\phantom{\rule{0.16em}{0ex}})f() given as a black box and the objective is to determine the number of xxx for which f(x)=1f(x)=1f(x)=1, denoted wt(f)wt(f)wt(f), given some possible values w1,...,wk{{w}_{1},...,{w}_{k}}w1​,...,wk​ for wt(f)wt(f)wt(f). When our technique is applied to this problem, we obtain the correct answer, maybe with a negligible error, using O(log2k2n)O({log}_{2}k\sqrt{{2}^{n}})O(log2​k2n​) calls to f()f(\phantom{\rule{0.16em}{0ex}})f(), which shows a quadratic speedup over classical approaches and currently known quantum algorithms.