Interaction Protocol for State Preparation and Unitary Synthesis

The state preparation problem is a fundamental question in quantum computing: how do you determine which sequence of operations are necessitated by the task of transforming some standard the initial state (e.g. the |0>^(⊗n) state) into a specified target state for all such possible target states? A related problem, called the unitary synthesis problem, concerns determining a sequence of elementary operations to arbitrarily accurately approximate a target unitary operation.

A recent result by Gregory Rosenthal and Henry Yuen presented at ITCS 2022 shows that any sequence of states for which there exists a polynomial-space (with no restrictions on time complexity) construction also admits an interactive protocol for the synthesis. Their model for interactive proof involves a polynomial-time quantum verifier interacting with a dubious quantum prover, a verifier accepting accurate approximations of the target state, and an honest prover which the verifier always accepts.

They also provide a similar interactive protocol for the unitary synthesis problem using the same framework as they used for the state synthesis problem. These results allow for the chance to construct more reductions and other claims about the computational complexity of these problems. Another result by Sandy Irani, et. al, co-authored by Henry Yuen, explores such reductions for the quantum search problem, which is a special class of the state preparation problem. They also provide the construction of a classical oracle for which the query complexity of approximating a quantum state to inverse exponential precision is sublinear with the number of qubits in the state. This result hence solves a long-standing open problem in the field of quantum information theory.

You can read more about their works from the arXiv preprints:

https://arxiv.org/abs/2108.07192,

https://arxiv.org/abs/2111.02999