Statistical Testing of Quantum Programs via Fixed-Point Amplitude Amplification
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.
Fri 25 OctDisplayed time zone: Pacific Time (US & Canada) change
16:00 - 17:40 | Testing Everything, Everywhere, All At OnceOOPSLA 2024 at IBR East Chair(s): Alex Potanin Australian National University | ||
16:00 20mTalk | Crabtree: Rust API Test Synthesis Guided by Coverage and Type OOPSLA 2024 Yoshiki Takashima Carnegie Mellon University, Chanhee Cho Carnegie Mellon University, Ruben Martins Carnegie Mellon University, Limin Jia , Corina S. Păsăreanu Carnegie Mellon University; NASA Ames DOI | ||
16:20 20mTalk | Drowzee: Metamorphic Testing for Fact-conflicting Hallucination Detection in Large Language Models OOPSLA 2024 Ningke Li Huazhong University of Science and Technology, Yuekang Li UNSW, Yi Liu Nanyang Technological University, Ling Shi Nanyang Technological University, Kailong Wang Huazhong University of Science and Technology, Haoyu Wang Huazhong University of Science and Technology DOI | ||
16:40 20mTalk | Reward Augmentation in Reinforcement Learning for Testing Distributed Systems OOPSLA 2024 Andrea Borgarelli Max Planck Institute for Software Systems, Constantin Enea LIX, CNRS, Ecole Polytechnique, Rupak Majumdar MPI-SWS, Srinidhi Nagendra CNRS, Université Paris Cité, IRIF, Chennai Mathematical Institute DOI | ||
17:00 20mTalk | Rustlantis: Randomized Differential Testing of the Rust Compiler OOPSLA 2024 DOI | ||
17:20 20mTalk | Statistical Testing of Quantum Programs via Fixed-Point Amplitude Amplification OOPSLA 2024 DOI |