Abstract
Quantum programming is hard: Quantum programs are necessarily probabilistic and impossible to examine without disrupting the execution of a program. In response to this challenge, we and a number of other researchers have written tools to verify quantum programs against their intended semantics. This is not enough. Verifying an idealized semantics against a real world quantum program doesn't allow you to confidently predict the program’s output. In order to have verification that works, you need both an error semantics related to the hardware at hand (this is necessarily low level) and certified compilation to the that same hardware. Once we have these two things, we can talk about an approach to quantum programming where we start by writing and verifying programs at a high level, attempt to verify properties of the compiled code, and repeat as necessary.
Keywords
FactoringQuantum Fourier transformIBMFourier transformDiscrete Fourier transform (general)Quantum computerQuantumFast Fourier transformComputer scienceAlgorithmMathematicsArithmeticFractional Fourier transformPhysicsFourier analysisQuantum mechanicsMathematical analysisQuantum error correctionOptics
Related Publications
Quantum measurements and the Abelian Stabilizer Problem
We present a polynomial quantum algorithm for the Abelian stabilizer problem which includes both factoring and the discrete logarithm. Thus we extend famous Shor's results. Our ...
The Design and Implementation of FFTW3
FFTW is an implementation of the discrete Fourier transform (DFT) that adapts to the hardware in order to maximize performance. This paper shows that such an approach can yield ...
Digital filters with equiripple or minimax responses
Techniques for determining the coefficients of digital filters which have equiripple or minimax errors are reviewed and occasionally extended. These techniques include: 1) mappi...
Structure and Interpretation of Computer Programs
"The Structure and Interpretation of Computer Programs" is the entry-level subject in Computer Science at the Massachusetts Institute of Technology. It is required of all studen...
Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
This paper proves best known guarantees for exact reconstruction of a sparse signal f from few non-adaptive universal linear measurements. We consider Fourier measurements (rand...
Publication Info
- Year
- 2019
- Type
- preprint
- Citations
- 341
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
341
OpenAlex
Cite This
Don Coppersmith
(2019).
Formal Verification vs. Quantum Uncertainty.
Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
.
https://doi.org/10.4230/lipics.snapl.2019.12
Identifiers
- DOI
- 10.4230/lipics.snapl.2019.12