Скачать или смотреть [PLanQC'26] Quantum Assertion Testing Without Mid-Circuit Measurement: Strategies and Lower Bounds

Quantum Assertion Testing Without Mid-Circuit Measurement: Strategies and Lower Bounds (Video, PLanQC 2026)
Shengyuan Yang, and Charles Yuan
(University of Wisconsin-Madison; University of Wisconsin–Madison)

Abstract: To make quantum computing more practical and ubiquitous, we must develop more general and robust ways to detect bugs in quantum programs. Prior work on runtime quantum assertions has focused on the expressiveness of individual assertions and their construction as quantum circuits, but a complementary question—how to effectively check multiple assertions in a quantum program—has been less explored.
In this work, we study the time–space trade-offs for testing quantum assertions in a practical hardware setting without mid-circuit measurement. We formalize this setting and analyze the FirstFail problem—outputting the first failing assertion among n program assertions. We give a single-run strategy that uses O(log n) ancilla qubits, and we prove a matching lower bound showing that any strategy must satisfy T × S = Ω(log n), where T is the number of runs and S is the number of ancilla qubits used per run.
This asymptotically improves over the O(n) product achieved by two naïve baselines (i.e., using a single run with n ancillae, or using a single ancilla with n runs). Moreover, it also shows that mid-circuit measurement does not yield a decisive advantage: it yields only O(log n) advantage, not O(n), over strategies not relying on mid-circuit measurements.


Presentation at the PLanQC 2026 workshop, Jan 12, 2026, https://popl26.sigplan.org/home/planq...
Sponsored by ACM SIGPLAN.