Oracle quantum programs are a fundamental class of quantum programs that serve as a critical bridge between quantum computing and classical computing. Many important quantum algorithms are built upon oracle quantum programs, making it essential to ensure their correctness during development. Although software testing is a well-established approach for improving program reliability, no systematic method has been developed to test oracle quantum programs. This paper proposes a black-box testing framework designed for general oracle quantum programs. We formally define these programs, establish the foundational theory for their testing, and propose a detailed testing framework. We develop a prototype tool and conduct extensive experimental evaluations to evaluate the effectiveness of the framework. Our results demonstrate that the proposed framework significantly aids developers in testing oracle quantum programs, providing insights to enhance the reliability of quantum software.
Oracle quantum programs are a fundamental class of quantum programs that serve as a critical bridge between quantum computing and classical computing. Many important quantum algorithms are built upon oracle quantum programs, making it essential to ensure their correctness during development. Although software testing is a well-established approach for improving program reliability, no systematic method has been developed to test oracle quantum programs. This paper proposes a black-box testing framework designed for general oracle quantum programs. We formally define these programs, establish the foundational theory for their testing, and propose a detailed testing framework. We develop a prototype tool and conduct extensive experimental evaluations to evaluate the effectiveness of the framework. Our results demonstrate that the proposed framework significantly aids developers in testing oracle quantum programs, providing insights to enhance the reliability of quantum software.
Quantum programs exhibit inherent non-deterministic behavior, which poses more significant challenges for error discovery compared to classical programs. While several testing methods have been proposed for quantum programs, they often overlook fundamental questions in black-box testing. In this paper, we bridge this gap by presenting three novel algorithms specifically designed to address the challenges of equivalence, identity, and unitarity checking in black-box testing of quantum programs. We also explore optimization techniques for these algorithms, including specialized versions for equivalence and unitarity checking, and provide valuable insights into parameter selection to maximize performance and effectiveness. To evaluate the effectiveness of our proposed methods, we conducted comprehensive experimental evaluations, which demonstrate that our methods can rigorously perform equivalence, identity, and unitarity checking, offering robust support for black-box testing of quantum programs.
Quantum computers have already shown high potential in solving complex computational problems much more efficiently compared to the typical conventional supercomputers. One major challenge in the field of quantum computing is to implement the major operations of the conventional computers using the available quantum hardware (quantum gates). Such operations are the arithmetic operations as well as decoding and multiplexing. An obvious burden is the absence of quantum gates that directly implement the fundamental Boolean operations like AND and OR. Moreover, care should be taken in order to reduce the costs involved when implementing a quantum circuit. In this paper, we present an oracle-based approach to implement quantum decoding and multiplexing in a joint circuit. The use of oracles necessarily implies that some type of quantum programming will be used. A quantum program is a process organized in a sequence of computations whose data elements are selected from the set of the known quantum gates. In our approach, the oracles are used as pre-programmed black boxes that determine if a datum should be directed from the input to the output. The important idea behind our scheme is that the oracles operate in parallel, therefore their selection decisions are taken simultaneously, while the approaches found in the literature implement sequential circuits with feedbacks from the outputs to inputs that burden the overall performance. We have used Qiskit open-source software development kit to verify the correctness of our design through extensive simulations.
Recent advancements in quantum computing software are gradually increasing the scope and size of quantum programs being developed. At the same time, however, these larger programs provide more possibilities for functional errors that are harder to detect and resolve. Meanwhile, debugging tools that could aid developers in resolving these errors are still barely existent and far from what we take for granted in classical design automation and software engineering. As a result, even if one manages to identify the incorrect behavior of a developed quantum program, detecting and resolving the underlying errors in the program remains a time-consuming and tedious task. Moreover, the exponential growth of the state space in quantum programs makes the efficient manual investigation of errors radically difficult even for respectively simple algorithms, and almost impossible as the number of qubits increases. To address this problem, this work proposes a debugging framework, available as an open-source implementation at https://github.com/cda-tum/mqt-debugger. It assists developers in debugging errors in quantum programs, allowing them to efficiently identify the existence of errors and diagnose their causes. Users are given the ability to place assertions in the code that test for the correctness of a given algorithm and are evaluated using classical simulations of the underlying quantum program. Once an assertion fails, the proposed framework employs different diagnostic methods to point towards possible error causes. This way, the debugging workload for quantum programs is drastically reduced.
With the increased developments in quantum computing, the availability of systematic and automatic testing approaches for quantum programs is becoming increasingly essential. To this end, we present the quantum software testing tool QuCAT for combinatorial testing of quantum programs. QuCAT provides two functionalities of use. With the first functionality, the tool generates a test suite of a given strength (e.g., pairwise). With the second functionality, it generates test suites with increasing strength until a failure is triggered or a maximum strength is reached. QuCAT uses two test oracles to check the correctness of test outputs. We assess the cost and effectiveness of QuCAT with 3 faulty versions of 5 quantum programs. Results show that combinatorial test suites with a low strength can find faults with limited cost, while a higher strength performs better to trigger some difficult faults with relatively higher cost.
Quantum software has entered production use, but its reliability remains sensitive. Bugs in compilers, simulators, and algorithm-layer source codes do not lead to program crashes; rather, they emerge as faulty probability distributions, successfully compiled but incorrect circuits, and differences between platforms, which classical testing oracles are incapable of noticing. This paper surveys quantum fuzzing as a response to that gap. This paper is organize in the field along the classical grey-box, white-box, and black-box axis and trace, for each category, the sequence of tools that have advanced the state of the art QuanTest, QSolver, and NovaQ representing the current frontiers respectively. Characterized the defect landscape these tools have collectively exposed, showing that bugs concentrate disproportionately in compilers and transpilation passes, that simulator and algorithm-layer faults form a distinct oracle-evading class, and that roughly 40% of confirmed quantum bugs are quantum-specific in symptom. Across all categories mentioned the same that crash-based detection is structurally inadequate for quantum software, and that the most productive fuzzers replace it with statistical, metamorphic, entanglement-guided, or formal-invariant oracles. We close by identifying the unification of these oracle strategies within a single campaign as the principal open challenge for the field.
Quantum computing is getting increasing interest from both academia and industry, and the quantum software landscape has been growing rapidly. The quantum software stack comprises quantum programs, implementing algorithms, and platforms like IBM Qiskit, Google Cirq, and Microsoft Q#, enabling their development. To ensure the reliability and performance of quantum software, various techniques for testing and analyzing it have been proposed, such as test generation, bug pattern detection, and circuit optimization. However, the large amount of work and the fact that work on quantum software is performed by several research communities, make it difficult to get a comprehensive overview of the existing techniques. In this work, we provide an extensive survey of the state of the art in testing and analysis of quantum software. We discuss literature from several research communities, including quantum computing, software engineering, programming languages, and formal methods. Our survey covers a wide range of topics, including expected and unexpected behavior of quantum programs, testing techniques, program analysis approaches, optimizations, and benchmarks for testing and analyzing quantum software. We create novel connections between the discussed topics and present them in an accessible way. Finally, we discuss key challenges and open problems to inspire future research.