Many natural problems in quantum computing involve constructing a quantum state or implementing a unitary transformation. However, relatively little is known about the computational complexity of these problems compared to that of computing boolean functions. In this thesis we do the following:• We prove upper bounds on the complexity of constructing arbitrary states and implementing arbitrary unitaries with the help of a classical oracle. • We prove bounds on the complexity of computing parity in QAC0, a quantum analogue of AC0, by way of a reduction to the task of constructing a certain type of state. • We prove upper bounds on the circuit size and depth required to construct arbitrary states and implement arbitrary unitaries, in various quantum circuit models. Many of these bounds are tight. • We define models of interactive proofs for constructing states and implementing unitaries with the help of an untrusted prover. We prove a quantum state analogue of the inclusion PSPACE ⊆ QIP, and obtain somewhat analogous results for unitaries and with multiple entangled provers. • We present barriers to improving several of the above results.
Many natural problems in quantum computing involve constructing a quantum state or implementing a unitary transformation. However, relatively little is known about the computational complexity of these problems compared to that of computing boolean functions. In this thesis we do the following:• We prove upper bounds on the complexity of constructing arbitrary states and implementing arbitrary unitaries with the help of a classical oracle. • We prove bounds on the complexity of computing parity in QAC0, a quantum analogue of AC0, by way of a reduction to the task of constructing a certain type of state. • We prove upper bounds on the circuit size and depth required to construct arbitrary states and implement arbitrary unitaries, in various quantum circuit models. Many of these bounds are tight. • We define models of interactive proofs for constructing states and implementing unitaries with the help of an untrusted prover. We prove a quantum state analogue of the inclusion PSPACE ⊆ QIP, and obtain somewhat analogous results for unitaries and with multiple entangled provers. • We present barriers to improving several of the above results.
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 PSPACE⊆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 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.
We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or BPP=NEXP. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in unitaryPSPACE either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for NEXP search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving unitaryPSPACE would imply breakthrough classical lower bounds such as NC=NP.
Along the way, we propose new definitions for the unitary complexity classes unitaryP and unitaryPSPACE. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that unitaryPSPACE has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that unitaryPSPACE can generically erase garbage, a result that provably fails relative to unitary oracles.
Testing the symmetries of quantum states and channels provides a way to assess their usefulness for different physical, computational, and communication tasks. Here, we establish several complexity-theoretic results that classify the difficulty of symmetry-testing problems involving a unitary representation of a group and a state or a channel that is being tested. In particular, we prove that various such symmetry-testing problems are complete for bounded-error quantum polynomial time, quantum Merlin–Arthur (QMA), quantum statistical zero-knowledge, two-message quantum interactive proofs (QIPs), two-message QIPs restricted to entanglement-breaking provers, and QIPs, thus spanning the prominent classes of the QIP hierarchy and forging a nontrivial connection between symmetry and quantum computational complexity. Finally, we prove the inclusion of two Hamiltonian symmetry-testing problems in QMA and quantum Arthur–Merlin, while leaving it as an intriguing open question to determine whether these problems are complete for these classes.
State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot easily be characterized using traditional complexity theory, which focuses on tasks with classical inputs and outputs. To study the complexity of such state transformation tasks, we introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. We formalize this as the Uhlmann Transformation Problem, an algorithmic version of Uhlmann's theorem. Then, we prove structural results relating the complexity of the Uhlmann Transformation Problem, polynomial space quantum computation, and zero knowledge protocols. The Uhlmann Transformation Problem allows us to characterize the complexity of a variety of tasks in quantum information processing, including decoding noisy quantum channels, breaking falsifiable quantum cryptographic assumptions, implementing optimal prover strategies in quantum interactive proofs, and decoding the Hawking radiation of black holes. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
Complexity theory traditionally studies the hardness of solving classical computational problems. In the quantum setting, it is also natural to consider a different notion of complexity, namely the complexity of physically preparing a certain quantum state. We study the relation between two such state complexity classes: statePSPACE, which contains states that can be generated by space-uniform polynomial-space quantum circuits, and stateQIP, which contains states that a polynomialtime quantum verifier can generate by interacting with an all-powerful untrusted quantum prover. The latter class was recently introduced by Rosenthal and Yuen (ITCS 2022), who proved that statePSPACE ⊆ stateQIP.Our main result is the reverse inclusion, stateQIP ⊆ statePSPACE, thereby establishing equality of the two classes and providing a natural state-complexity analogue to the celebrated QIP = PSPACE theorem of Jain, et al. (J. ACM 2011). To prove this, we develop a polynomial-space quantum algorithm for solving a large class of exponentially large “PSPACE-computable” semidefinite programs (SDPs), which also prepares an optimiser encoded in a quantum state. Our SDP solver relies on recent blockencoding techniques from quantum algorithms, demonstrating that these techniques are also useful for complexity theory.Using similar techniques, we also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum polynomial space. We prove this by studying an algorithmic version of Uhlmann’s theorem and establishing an upper bound on the complexity of implementing Uhlmann transformations.
Bounds on the QAC0 Complexity of Approximating Parity
QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. QAC0 circuits are QAC circuits of constant depth, and are quantum analogues of AC0 circuits. We prove the following:
∙ For all d≥7 and ε>0 there is a depth-dQAC circuit of size exp(poly(n1/d)log(n/ε)) that approximates the n-qubit parity function to within error ε on worst-case quantum inputs. Previously it was unknown whether QAC circuits of sublogarithmic depth could approximate parity regardless of size.
∙ We introduce a class of QAC circuits, including a major component of our circuit from the above upper bound, and prove a tight lower bound on the size of low-depth, mostly classical QAC circuits that approximate this component.
∙ Arbitrary depth-dQAC circuits require at least Ω(n/d) multi-qubit gates to achieve a 1/2+exp(−o(n/d)) approximation of parity. When d=Θ(logn) this nearly matches an easy O(n) size upper bound for computing parity exactly.
∙QAC circuits with at most two layers of multi-qubit gates cannot achieve a 1/2+exp(−o(n)) approximation of parity, even non-cleanly. Previously it was known only that such circuits could not cleanly compute parity exactly for sufficiently large n.
The proofs use a new normal form for quantum circuits which may be of independent interest, and are based on reductions to the problem of constructing certain generalizations of the cat state which we name nekomata after an analogous cat y\=okai.