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. With this motivation, we define models of interactive proofs for synthesizing quantum states and unitaries, where a polynomialtime 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 PSPACE ⊆ IP: any sequence of states computable by a polynomialspace 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 spacecomputable unitaries that act nontrivially on only a polynomialdimensional subspace. We obtain analogous results in the setting with multiple entangled provers as well.
BibTeX  Entry
@InProceedings{rosenthal_et_al:LIPIcs.ITCS.2022.112,
author = {Rosenthal, Gregory and Yuen, Henry},
title = {{Interactive Proofs for Synthesizing Quantum States and Unitaries}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {112:1112:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15708},
URN = {urn:nbn:de:0030drops157086},
doi = {10.4230/LIPIcs.ITCS.2022.112},
annote = {Keywords: interactive proofs, quantum state complexity, quantum unitary complexity}
}
Keywords: 

interactive proofs, quantum state complexity, quantum unitary complexity 
Collection: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) 
Issue Date: 

2022 
Date of publication: 

25.01.2022 