Abstract
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. Towards a general theory of the complexity of "inherently quantum" operations, we define models of interactive proofs for synthesizing quantum states and unitaries. In these protocols, the verifier interacts with an untrusted quantum prover and is able to verify at the end whether a target state has been constructed (for state synthesis) or whether a target unitary has been implemented (for unitary synthesis).
Our main result is a "state synthesis" analogue of the inclusion of PSPACE in IP: 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 protoco for polynomial space-computable unitaries that act nontrivially on only a polynomial-dimensional subspace.
Joint work with Greg Rosenthal.