Testing a Qubit and Classical Verification of Quantum Computation
Stub. Characterizing/testing an untrusted quantum device's qubit using observables and trapdoor claw-free functions, including a hardcore-bits assumption and the circuit-to-Hamiltonian reduction that converts a quantum computation into a local Hamiltonian whose ground energy encodes the correct output; and the resulting protocol (Fitzsimmons-Morimae) letting a purely classical verifier certify a quantum computation's correctness.
Corresponds to Chapters 23–25.3. A classical verifier interacting with an untrusted quantum device (a “prover”) needs a way to test that the device is actually doing what it claims — this note builds that out of the trapdoor claw-free functions from fully-homomorphic-encryption-classical-and-quantum: a protocol lets the classical verifier check properties of a qubit it never directly sees, via observables and a cryptographic hardcore-bits assumption, effectively “establishing” a qubit’s existence and basic properties through classical interaction alone. This generalizes, via the circuit-to-Hamiltonian reduction (the same reduction underlying the QMA-completeness of the local Hamiltonian problem — see quantum-complexity-theory), to classical verification of quantum computation: the Fitzsimmons-Morimae protocol lets a classical verifier certify that a quantum computation was performed correctly, without the verifier needing any quantum hardware of its own — a foundational result for quantum money (quantum-money-and-cryptography-with-deletion) and for trusting quantum computers from a purely classical vantage point.
Outline (TODO — flesh out each)
- Characterizing qubits with observables
- Trapdoor claw-free functions, reviewed
- The testing protocol
- The hardcore bits assumption
- Establishing a qubit
- The circuit-to-Hamiltonian reduction
- Local Hamiltonians
- The Fitzsimmons-Morimae protocol for classical verification