Statistical Testing of Quantum Programs via Fixed-Point Amplitude Amplification
summary
Proposes using fixed-point amplitude amplification to reduce the number of runs needed to statistically detect wrong output states, claiming reductions like 1,000→2 runs for a toy bug and 9,000→5 for verification, while preserving the program state when no bug exists. Introduces a sequential FPAA strategy found by random search to cut expected circuit-moment cost (measured instead of running on hardware), reporting ~58% average verification cost reduction versus naive sampling and ~40% gain for B=0.001, and limits worst-case loss from −120% to about −29%.
AI-written summary · about
chapters (10)
- 0:00Quantum program testing intro
- 2:12Problem definition and bug detection
- 3:56Measurement limits in quantum programs
- 5:46Naive sampling challenges
- 7:54Fixed-point amplitude amplification
- 9:40Sequential fixed-point strategy
- 11:27Experimental evaluation and cost
- 13:38Core principles of amplification
- 14:43Summary and future research
- 15:04Q&A
related talks
42mQuantum program analysis: Verification and Testing
22mEfficient Formal Verification of Quantum Error Correcting Programs
16mProjection-Based Runtime Assertions for Testing and Debugging Quantum Programs
19mAvenues for Quantum Error Correction and Mitigation
18mAn Automata-Based Framework for Verification and Bug Hunting in Quantum Circuits
19mShaking Up Quantum Simulators with Fuzzing and Rigour
15mAssertion-Based Optimization of Quantum Programs
48mThe Quantum Games PCP: Results and Confessions