💻 computer science

Metamorphic Testing of Quantum Query Algorithms

This paper proposes and validates six metamorphic relations for three quantum query algorithms, demonstrating through systematic experiments that these relations effectively detect faults with high mutation scores and maintain this effectiveness even when using significantly reduced input sets.

Original authors: Sinhué García-Gil, Luis Llana, José Ignacio Requeno Jarabo

Published 2026-11-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sinhué García-Gil, Luis Llana, José Ignacio Requeno Jarabo

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the emerging field of quantum computing, machines promise to solve problems that would take today's supercomputers thousands of years to crack. These machines do not use the standard on-off switches of classical computers; instead, they rely on particles that can exist in multiple states at once, a property that allows them to explore many possibilities simultaneously. However, this power comes with a significant hurdle: the act of measuring the result of a quantum calculation is inherently probabilistic. Unlike a classical computer that gives a single, definite answer, a quantum machine produces a cloud of possibilities, requiring researchers to run the same calculation thousands of times and use statistics to guess the correct outcome. This uncertainty makes it incredibly difficult to test whether the software running these machines is working correctly, as there is often no simple way to know if the result is right or wrong without running the entire process again.

To address this challenge, a team of researchers at the Universidad Complutense de Madrid has developed a new way to test quantum software that sidesteps the need for a perfect answer key. They focused on three specific types of quantum programs designed to solve particular mathematical puzzles. Instead of trying to predict the exact output of every single run, the team created a set of rules that describe how the results of different inputs should relate to one another. If the software is working correctly, changing the input in a specific way will always produce a predictable change in the output, even if the exact numbers remain uncertain. By checking these relationships, the researchers could verify the software's logic without needing to know the final answer in advance.

The researchers applied this method to three well-known quantum algorithms: one that determines if a function is balanced or constant, another that uncovers a hidden secret string, and a third that finds a repeating pattern. They defined six specific rules, or relationships, that these algorithms must follow. For instance, if you flip the bits of an input in a certain way, the output should change in a corresponding, predictable manner. To test if these rules held up, they used a technique called mutation testing. This involved taking the original, correct quantum circuits and intentionally introducing small, random errors into them, creating thousands of slightly broken versions. They then ran their new testing rules against these broken versions to see if the rules could spot the mistakes.

The results showed that these relationship-based rules were highly effective at catching errors. When the researchers tested the software with all possible inputs, the rules successfully identified between 41 percent and 83 percent of the introduced faults, depending on the specific algorithm. This was a significant finding because it proved that these rules could reliably detect errors in quantum software without needing to know the correct answer beforehand. More importantly, the team discovered that they did not need to test every single possible input to get this level of accuracy. In many cases, testing just a handful of inputs was enough to find the same number of errors as testing the entire set. For some algorithms, testing as few as three inputs was sufficient to reproduce the results of an exhaustive test that would have required millions of calculations.

This discovery is crucial for the future of quantum software engineering. Because quantum simulations are computationally expensive, running every possible test is often impossible, especially as the problems get larger. The researchers found that for the algorithms they studied, the ability to detect errors stabilized quickly. After a certain point, adding more inputs did not reveal new errors, suggesting that a small, carefully chosen set of tests could be enough to ensure the software is working. While the study was conducted using computer simulations rather than physical quantum hardware, the findings offer a practical path forward. They suggest that by focusing on how inputs and outputs relate to each other, rather than trying to predict exact outcomes, developers can build more reliable quantum software with far fewer resources. The work highlights that even in a world of probabilistic results, there are still solid, predictable patterns that can be used to ensure quality and trust in these complex new machines.

Technical Summary: Metamorphic Testing of Quantum Query Algorithms

Problem Statement
Testing quantum software faces two primary challenges: the probabilistic nature of quantum measurement, which necessitates repeated executions and statistical analysis to verify behavior, and the "oracle problem," where determining the correct expected output for a given input is often intractable. While Metamorphic Testing (MT) offers a solution to the oracle problem by verifying relationships between inputs and outputs rather than specific values, its fault-detection effectiveness and input requirements for quantum algorithms remain insufficiently investigated. Furthermore, existing approaches often rely heavily on statistical analysis of measurement outcomes, which increases testing costs.

Methodology
The authors propose a systematic approach to apply MT to three fundamental quantum query algorithms: Deutsch-Jozsa (DJ), Bernstein-Vazirani (BV), and Simon. The methodology involves three core components:

Definition of Metamorphic Relations (MRs): Six specific MRs were derived based on the mathematical properties and preconditions of the target algorithms:
- Deutsch-Jozsa: Two MRs ( $MR1_{DJ}$ , $MR2_{DJ}$ ) based on bijections and input complementation, verifying that the output remains $|0\rangle$ if and only if the function is constant.
- Bernstein-Vazirani: Three MRs ( $MR1_{BV}$ , $MR2_{BV}$ , $MR3_{BV}$ ) derived from the algebraic properties of the oracle. Notably, these relations allow the verification of properties (e.g., $o_2 = o_0 \oplus o_1$ ) before measurement by combining outputs within the quantum circuit using CNOT gates. This minimizes dependence on statistical analysis.
- Simon: One MR ( $MR_S$ ) based on the periodicity of the function, verifying that inverting the input string results in the same set of measurement outcomes.
Integration with Mutation Testing: The authors extended the QCRMut tool (which supports Qiskit 2.x) to automate the testing process.
- Mutant Generation: QCRMut generates mutants by introducing faults into the quantum circuits while preserving specific "immutable" sections (the input oracles) to ensure the MRs remain applicable.
- Testing Structure: A framework was developed to translate the mathematical MRs into executable test structures. This includes computational input generators, test-circuit constructors (which insert oracles and, for BV, combine outputs), and result analyzers that determine if a mutant is "killed" (i.e., the MR is violated).
Experimental Evaluation: Three experiments were conducted using Qiskit's AerSimulator:
- Experiment I (Exhaustive Evaluation): Evaluated the validity and fault-detection effectiveness of the MRs across the complete input space for various qubit configurations (up to 6-7 qubits depending on the algorithm).
- Experiment II (Input Reduction): Investigated whether a reduced set of randomly selected inputs could reproduce the mutation scores obtained via exhaustive evaluation. This involved 20 random seeds per configuration.
- Experiment III (Stabilization): Examined larger configurations (up to 7 qubits) where exhaustive evaluation was computationally impractical, analyzing whether mutation scores stabilized with a limited number of inputs.

Key Results

Fault-Detection Effectiveness (RQ1): All six MRs successfully detected faults in the generated mutants. Mutation scores ranged from 41.80% to 83.59%.
- Bernstein-Vazirani MRs achieved the highest scores (75.35% – 83.59%).
- Deutsch-Jozsa MRs showed consistent effectiveness (69.92% – 77.34%).
- Simon's MR showed lower but significant effectiveness (41.80% – 60.16%).
Input Reduction (RQ2): Reduced input sets were highly effective in reproducing exhaustive results.
- For Deutsch-Jozsa, 3 inputs were sufficient across all configurations.
- For Bernstein-Vazirani, a median of 2 to 4 inputs was required.
- For Simon, the median ranged from 4 to 11.5 inputs depending on qubit count.
- Crucially, all 20 random seeds for every configuration reached the exhaustive mutation score within 15 inputs.
Stabilization (RQ3): For larger configurations without exhaustive references, mutation scores tended to stabilize. While Simon showed some gains up to 15 inputs, no further detections were observed beyond 15 inputs in any configuration.

Significance and Claims
The paper claims to provide the first systematic evaluation of the fault-detection capability of MT for quantum algorithms using automatically generated mutants. Its primary contributions are:

Demonstrating MT Viability: Confirming that MT is a promising approach for quantum software testing, capable of detecting a substantial proportion of faults without a traditional test oracle.
Pre-Measurement Verification: Highlighting that for algorithms like Bernstein-Vazirani, MRs can be verified deterministically within the circuit before measurement, reducing reliance on statistical analysis.
Input Efficiency: Showing that exhaustive input space evaluation is often unnecessary; small, randomly selected input sets can preserve fault-detection effectiveness, thereby mitigating the computational costs associated with quantum simulation.

The authors maintain a modest stance, acknowledging that MR definition is algorithm-specific and that the presence of equivalent mutants may lead to an underestimation of mutation scores. They also note that current results are based on simulation and that future work is needed to validate these findings on real quantum hardware and to extend the approach to more complex, practical quantum algorithms.

Technical Summary: Metamorphic Testing of Quantum Query Algorithms

More like this