Interactive Proofs for Synthesizing Quantum States and Unitaries
Gregory Rosenthal, University of Toronto
Whereas quantum complexity theory has traditionally been concerned with problems arising from classical complexity theory (such as computing boolean functions), it also makes sense to study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations. With this motivation, we define models of interactive proofs for synthesizing quantum states and unitaries, where a polynomial-time quantum verifier interacts with an untrusted quantum prover, and a verifier who accepts also outputs an approximation of the target state (for the state synthesis problem) or the result of the target unitary applied to the input state (for the unitary synthesis problem); furthermore there should exist an "honest" prover which the verifier accepts with probability 1.
Our main result is a "state synthesis" analogue of the inclusion PSPACECIP: any sequence of states computable by a polynomial-space quantum algorithm (which may run for exponential time) admits an interactive protocol of the form described above. Leveraging this state synthesis protocol, we also give a unitary synthesis protocol for polynomial space-computable unitaries that act nontrivially on only a polynomial-dimensional subspace. We obtain analogous results in the setting with multiple entangled provers as well.
Based on joint work with Henry Yuen.
Join the seminar on Zoom
Meeting link: IQC-QuICS Math and Computer Science Seminar
Add event to calendar
Apple Google Office 365 Outlook Outlook.com Yahoo
This virtual seminar is jointly sponsored by the Institute for Quantum Computing and the Joint Center for Quantum Information and Computer Science.
If you are interested in presenting at a future seminar, please email either Daniel Grier (daniel.grier@uwaterloo.ca) or Adam Bene Watts (adam.benewatts1@uwaterloo.ca).