1 Introduction↩︎

Many natural tasks in quantum computing can be phrased as constructing a quantum state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\), by which we mean implementing a quantum circuit that outputs \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) given the all-zeros input. Examples include ground states of physical systems cerezo2021variational?, Hamiltonian simulation applied to the all-zeros state swingle2018unscrambling?, QSampling states AT03?, quantum money aaronson2009quantum?, quantum pseudorandom states ji2018pseudorandom?, and the first step in Linear Combinations of Unitaries (LCU) BCK15?, CW12?. A survey by Aaronson Aar16? discusses other examples.

Despite this, much less is known about the complexity of constructing quantum states than is known about the (quantum) complexity of computing Boolean functions. This motivates the goal of finding, for a state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) that we would like to construct, a Boolean function \(f\) such that the task of constructing \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) efficiently reduces to that of computing \(f\). We can phrase this problem as follows:

We call \(A\) a state synthesis algorithm. By \(A^f\) we mean \(A\) with query access to the Boolean function \(f\). We may assume without loss of generality that \(f\) has a single output bit, for reasons that will be explained in 2 when we define the query model. The requirement that all queries be to the same function \(f\) is also without loss of generality, because if the \(j\)’th query is to a function \(f_j\) then the function \((j,x) \mapsto f_j(x)\) can simulate all queries.

Our main result is the following state synthesis algorithm, where by a “clean construction" we mean that the ancillae end in approximately the all-zeros state (as opposed to some other state unentangled with \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\)):

We state 2 formally in 4. The rest of the Introduction is organized as follows: in 1.1 we compare 2 to previously known state synthesis algorithms, in [sec:bar] [sec:iss] [sec:cub] we discuss three different applications of 2, and in 1.5 we discuss the organization of the rest of the paper.

First we briefly sketch the proof of 2.² For simplicity, in this sketch we allow the circuit (as opposed to just the oracle) to depend on the state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) being constructed. Call a state of the form \(C \cdot 2^{-n/2} \sum_{x \in \{0,1\}^{n}} \pm \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle\) where \(C\) is a Clifford unitary a “Clifford times phase state". Irani, Natarajan, Nirkhe, Rao and Yuen INN+22? proved that every state has fidelity \(\Omega(1)\) with some Clifford times phase state (more generally, this holds for \(C\) from any 2-design) and observed that Clifford times phase states can be efficiently constructed with one query. Thus all that remains is to decrease the approximation error.

We recursively define \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_k \mspace{.5mu}}\right\rangle\) for \(k \ge 0\) as a Clifford times phase state that has fidelity \(\Omega(1)\) with \(\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle- \sum_{j=0}^{k-1} c_j \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_j \mspace{.5mu}}\right\rangle}\right) / \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle- \sum_{j=0}^{k-1} c_j \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_j \mspace{.5mu}}\right\rangle}\right\|\), for appropriately chosen coefficients \(c_0, c_1, \dotsc\) tending to zero. We show that \(\sum_{j=0}^{k-1} c_j \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_j \mspace{.5mu}}\right\rangle\) is a good approximation of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) for sufficiently large \(k\). Furthermore, using Linear Combinations of Unitaries (LCU) BCK15?, CW12? we can construct this approximation of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) with constant success probability. Finally we increase the success probability either by parallel repetition (in the one-query version of the theorem), with parallel queries merged into a single query, or by a hybrid of parallel repetition and amplitude amplification (in the four-query version).

1.1 Comparison to previous state synthesis algorithms↩︎

There is a trivial state synthesis algorithm using one query, where that query returns the description of a circuit over a universal gate set that constructs an exponentially close approximation of the target state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\). This construction can be made clean by using a second query to uncompute the first query after constructing \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\). However this algorithm requires an exponential number of qubits, because there exist states that require exponentially large circuits to construct NC10?.

The following algorithm improves on the trivial algorithm by running in polynomial time, but at the expense of requiring a super-constant number of queries:

The following algorithm also improves on the trivial algorithm, by running in polynomial rather than exponential space, without an increase in the number of queries:

However 4 does not give an upper bound on the circuit size required to implement the non-query operations, besides the trivial exponential upper bound, and these circuits are nonuniform. Furthermore in the one-query version of 4, the approximation error is inverse polynomial rather than inverse exponential.

1 compares these algorithms, of which only ours runs in polynomial time using a constant number of queries. Our result answers questions posed by Aaronson Aar16? and Irani et al. INN+22?, who collectively asked whether there exists a polynomial-time one-query state synthesis algorithm with exponentially small error.

1.2 \(\mathsf{statePSPACE} = \mathsf{stateQIP}(6)\)↩︎

Rosenthal and Yuen RY21? introduced a notion of interactive proofs for constructing a state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\), where a polynomial-time quantum verifier interacts with an unbounded-complexity but untrusted prover. At the end of the interaction the verifier accepts or rejects, and when accepting the verifier also outputs a state. The completeness condition is that there should exist a prover such that the verifier accepts with probability 1. The soundness condition is that for every prover such that the verifier accepts with non-negligible probability, the verifier’s output state conditioned on accepting should be an approximation of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}\psi \mspace{.5mu}}\right\rvert\).

Rosenthal and Yuen RY21? defined \(\mathsf{stateQIP}\) as the class of state sequences that can be constructed in this way, in analogy with the class \(\mathsf{QIP}\) of decision problems with similar quantum interactive protocols. They also defined \(\mathsf{statePSPACE}\) as a quantum state analogue of \(\mathsf{PSPACE}\). (Formal definitions are given in 5.) Then Rosenthal and Yuen proved the inclusion \(\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}\), and Metger and Yuen MY23? proved the converse inclusion \(\mathsf{stateQIP} \subseteq \mathsf{statePSPACE}\). This establishes the equality \(\mathsf{stateQIP} = \mathsf{statePSPACE}\), a quantum state analogue of \(\mathsf{QIP} = \mathsf{PSPACE}\) jain2011qip?, which is itself a quantum analogue of \(\mathsf{IP} = \mathsf{PSPACE}\) lund1992algebraic?, shamir1992ip?.

Rosenthal and Yuen’s proof that \(\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}\) goes roughly as follows. Let \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) denote the \(n\)-qubit state that the verifier would like to construct, and let \(f\) be the oracle associated with constructing \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) in 3. Tomography of states in \(\mathsf{statePSPACE}\) can be done in \(\mathsf{PSPACE}\) since \(\mathsf{PSPACE} = \mathsf{BQPSPACE}\) watrous03complexity?, and inspection of the proof of 3 reveals that \(f\) can be computed in \(\mathsf{PSPACE}\) given query access to the description of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\). Therefore \(f\) can be computed in \(\mathsf{PSPACE}\), which suggests the following candidate protocol for constructing \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\): simulate the algorithm from 3, with queries to \(f\) answered by running the \(\mathsf{IP}= \mathsf{PSPACE}\) protocol in superposition.

However, controlled on an input string \(x\) to the \(\mathsf{IP}= \mathsf{PSPACE}\) protocol for \(f\), there is a garbage state associated with \(x\) at the end of the \(\mathsf{IP}= \mathsf{PSPACE}\) protocol. The prover is required to help the verifier uncompute this garbage state, so that the verifier’s output register is not entangled with the rest of the system. The main challenge is to ensure that the prover uncomputes this garbage state honestly, which the verifier achieves using an intricate sequence of swap tests. Finally the soundness of the protocol is improved by repeating the above procedure polynomially many times, accepting if and only if every instance accepts, and then outputting the output state of a random instance.

Rosenthal and Yuen RY21? posed the question of whether there exists a \(\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}\) protocol with a constant number of rounds of interaction. Since the \(\mathsf{PSPACE}\subseteq \mathsf{QIP}\) protocol can be parallelized to three total messages watrous03pspace?, the main obstacle is that the algorithm from 3 makes a super-constant number of queries. A second, more subtle obstacle is that Rosenthal and Yuen’s proof of correctness of the above soundness amplification procedure breaks down if the instances are run in parallel.

Using the one-query version of 2 we prove the following, where \(\mathsf{stateQIP}(6)\) is defined similarly to \(\mathsf{stateQIP}\) but for protocols with six total messages:

5 mostly follows by substituting 2 for 3 in Rosenthal and Yuen’s RY21? proof that \(\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}\). However, we present a self-contained proof of 5 for three reasons. First, it is necessary to prove that a soundness amplification procedure similar to the one used by Rosenthal and Yuen can be parallelized. Second, we can substitute a single, easily defined projective measurement for the sequence of swap tests in Rosenthal and Yuen’s proof, using the fact that the queries in our one-query state synthesis algorithm are (trivially) non-adaptive. This significantly simplifies the description of the verifier and the proof of soundness. Third, in their proof of the converse inclusion \(\mathsf{stateQIP} \subseteq \mathsf{statePSPACE}\), Metger and Yuen MY23? used definitions of \(\mathsf{statePSPACE}\) and \(\mathsf{stateQIP}\) slightly different than those of Rosenthal and Yuen. We adopt Metger and Yuen’s definitions in our proof of 5, implying the equality \(\mathsf{statePSPACE} = \mathsf{stateQIP} = \mathsf{stateQIP}(6)\).

1.3 Barrier to \(\mathsf{QAC_f^0}\) lower bounds for constructing explicit states↩︎

In classical circuit complexity it is notoriously difficult to prove that an explicit Boolean function is hard for a given circuit class. The same holds for quantum circuit complexity, since quantum circuits can simulate Boolean circuits. However this does not immediately imply that it should be difficult to prove quantum circuit lower bounds for quantum tasks with no classical analogue, such as constructing a quantum state. And in fact, Jia and Wolf JW23? found explicit states that require exponential circuit size to exactly construct.

Nevertheless, Aaronson Aar16? observed a barrier to finding explicit states that cannot be approximately constructed by \(\mathsf{BQP/poly}\) circuits (i.e.nonuniform polynomial-size quantum circuits) to within exponentially small error. Specifically, let \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_n \mspace{.5mu}}\right\rangle\) be an \(n\)-qubit state for all \(n\) and let \(f_n\) be the oracle associated with approximately constructing \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_n \mspace{.5mu}}\right\rangle\) in 3. If \((f_n)_n\) can be computed in \(\mathsf{BQP/poly}\), then plugging these circuits for \((f_n)_n\) into the algorithm from 3 yields a sequence of \(\mathsf{BQP/poly}\) circuits for approximately constructing \((\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_n \mspace{.5mu}}\right\rangle)_n\). Conversely, if there are no \(\mathsf{BQP/poly}\) circuits for approximately constructing \((\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_n \mspace{.5mu}}\right\rangle)_n\) then there are no \(\mathsf{BQP/poly}\) circuits for computing \((f_n)_n\). This would be a breakthrough result, since finding an explicit function that is not in \(\mathsf{BQP/poly}\) (or even \(\mathsf{P/poly}\)) is a longstanding open problem.

However this still leaves open the possibility of finding explicit states that cannot be approximately constructed by \(\mathcal{C}\) circuits, for some nonuniform quantum circuit class \(\mathcal{C}\) that (as far as we know) is weaker than \(\mathsf{BQP/poly}\). One such class is \(\mathsf{QAC_f^0}\), a quantum analogue of \(\mathsf{AC^0}\) introduced by Green, Homer, Moore and Pollett Gre+02? which we define in 2. Analogously to \(\mathsf{AC^0}\), one motivation for proving lower bounds against \(\mathsf{QAC_f^0}\) is that it is contained in \(\mathsf{QNC^1}\)(i.e.log-depth circuits with one- and two-qubit gates), and another motivation is that \(\mathsf{QAC_f^0}\) is one of the weakest quantum circuit classes that is natural to define. The “next weakest" class \(\mathsf{QAC^0}\) Gre+02? is like \(\mathsf{QAC_f^0}\) except without”fanout gates" that make copies of a classical bit, and the even weaker class \(\mathsf{QNC^0}\) is easy to prove lower bounds against by light cone arguments.

The non-query operations from 2 can be efficiently implemented in \(\mathsf{QAC_f^0}\), so we can rule out this possibility by reasoning similar to that in Aaronson’s barrier:

We state 6 more formally in 7. It is known that \(\mathsf{TC^0} \subseteq \mathsf{QAC_f^0}\) HS05?, TT16?, where \(\mathsf{TC^0}\) denotes the class of functions computable by non-uniform polynomial-size Boolean circuits with NOT gates and unbounded-fanin AND, OR, and MAJORITY gates. It is an open problem to prove superpolynomial-size \(\mathsf{TC^0}\) lower bounds for an explicit Boolean function, so 6 implies a barrier to proving superpolynomial-size \(\mathsf{QAC_f^0}\) lower bounds for approximately constructing explicit states.

1.4 Approximately constructing arbitrary states↩︎

Every \(n\)-qubit pure state can be cleanly, exactly constructed with \(O(2^n)\) one- and two-qubit gates Gui+23?, Sun+21?, YZ23?, ZLY22?. This upper bound is tight, because by a dimension-counting argument a Haar random state almost surely requires \(\Omega(2^n)\) one- and two-qubit gates to construct exactly. However we show that circuits of size \(o(2^n)\) can approximately construct any \(n\)-qubit state, moreover with gates from an appropriate finite gate set:

We prove [thm:ubs] using Lupanov’s Lup58? \(O(2^m/m)\)-size Boolean circuit for an arbitrary function \(f: \{0,1\}^{m} \to \{0,1\}\), applied to the oracle from the clean version of 2. The portion of the circuit corresponding to the non-query operations is converted to a circuit over \(\mathcal{G}\) using the Solovay–Kitaev theorem BG21?, DN06?. We require \(\varepsilon\ge \exp(-\mathrm{poly}(n))\) for convenience, but our proof technique implies a similar statement for smaller \(\varepsilon\) as well.

The circuit from [thm:ubs] uses exponentially many ancillae. Some ancillae are necessary, because Nielsen and Chuang NC10? proved by a counting argument that without ancillae, for every finite gate set \(\mathcal{G}\) there exist states that require \(\Omega\mathopen{}\mathclose{\left(2^n \log(1/\varepsilon) / \log n}\right)\) gates from \(\mathcal{G}\) to construct to within error \(\varepsilon\). We also prove an analogue of Nielsen and Chuang’s lower bound for non-clean constructions with ancillae, by a similar counting argument:

To properly compare [thm:ubs] [thm:lbs] it is necessary to convert the error bound in [thm:ubs] from 2-norm error to trace distance error. Identifying a pure state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi \mspace{.5mu}}\right\rangle\) with the density matrix \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}\phi \mspace{.5mu}}\right\rvert\), the trace distance between two pure states is at most the 2-norm distance between those states (see 3 ), so the conclusion of [thm:ubs] implies that the trace distance between \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\mathopen{}\mathclose{\left\lvert\mspace{.5mu}0\dotsc 0 \mspace{.5mu}}\right\rangle\) and \(C \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0\dotsc 0 \mspace{.5mu}}\right\rangle\) is at most \(\varepsilon\). Therefore the trace distance between \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) and the reduced state on the first \(n\) qubits of \(C \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0\dotsc 0 \mspace{.5mu}}\right\rangle\) is at most \(\varepsilon\), so the lower bound from [thm:lbs] matches the upper bound from [thm:ubs].

It is an open problem whether the \(\varepsilon\ge 2^{-O(n)}\) case of [thm:lbs] generalizes to circuits consisting of arbitrary one- and two-qubit gates. (The \(\varepsilon\le 2^{-\omega(n)}\) case cannot admit such a generalization, by the previously mentioned \(O(2^n)\) upper bounds for exact constructions with arbitrary one- and two-qubit gates.) A slightly weaker lower bound of \(2^n / \mathrm{poly}(n)\) holds for such circuits, because by the Solovay–Kitaev theorem BG21?, DN06? circuits consisting of \(2^n n^{-\omega(1)}\) one- and two-qubit gates can be simulated to within exponentially small error by circuits consisting of \(2^n n^{-\omega(1)}\) gates from a universal gate set, and therefore by [thm:lbs] cannot construct arbitrary \(n\)-qubit states to within error \(\varepsilon\).³

1.5 Organization↩︎

2 is the preliminaries. In 3 we prove a weaker variant of the one-query version of 2, where the circuit postselects on a certain measurement outcome that occurs with constant probability. By reducing to this result in different ways, in 4 we prove the one- and four-query versions of 2. In 5 we define \(\mathsf{statePSPACE}\) and \(\mathsf{stateQIP}(6)\) and introduce other related background, in preparation for the proof in 6 that \(\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}(6)\) (i.e.5). In 7 we state and prove 6 more formally, and in 8 we prove [thm:ubs] [thm:lbs].

2 Preliminaries↩︎

Logarithms in this paper are base 2. We write \((x_n)_n\) to denote the infinite sequence \((x_1, x_2, \dotsc)\) for some class of objects \(x_n\).

Space-bounded computation

All Turing machines in this paper have a read-only input tape, read-write work tapes, and a write-only output tape. Let \(\{0,1\}^{*}\) denote the set of finite strings over \(\{0,1\}\), and for \(x \in \{0,1\}^{*}\) let \(|x|\) denote the length of \(x\). For \(s: \mathbb{N}\to \mathbb{N}\) a Turing machine \(M\) uses space \(s\) if for all \(x \in \{0,1\}^{*}\), at most \(s(|x|)\) cells are used on the work tapes in the computation of \(M(x)\). If \(M\) uses space \(s\) and halts then \(M\) uses time \(O(2^s)\), so \(|M(x)| \le O\mathopen{}\mathclose{\left(2^{s(|x|)}}\right)\) for all \(x\).

Description of a pure state

For \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle= \sum_{x \in \{0,1\}^{n}} \alpha_x \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle\) and \(\varepsilon>0\), we define an \(\varepsilon\)-precision description of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) to be a tuple \(\mathopen{}\mathclose{\left(\tilde{\alpha}_x}\right)_{x \in \{0,1\}^{n}}\) of complex numbers specified exactly in binary such that \(\mathopen{}\mathclose{\left| \tilde{\alpha}_x - \alpha_x }\right| \le \varepsilon\) for all \(x\). We will often leave \(\varepsilon\) implicit and simply refer to “the description of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\)", by which we mean an \(\exp(-p(n))\)-precision description of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) where \(p\) is a polynomial that may be chosen to be as large as desired; in this case \(\mathrm{poly}(n)\) bits of precision are needed to specify \(\tilde{\alpha}_x\).

Quantum information theory

A register \(\mathsf R\) is a named finite-dimensional complex Hilbert space. If \(\mathsf A, \mathsf B, \mathsf C\) are registers, for example, then the concatenation \(\mathsf{ABC}\) denotes the tensor product of the associated Hilbert spaces. For a linear transformation \(L\) and register \(\mathsf R\), we write \(L_{\mathsf R}\) to indicate that \(L\) acts on \(\mathsf R\), and similarly we write \(\rho_{\mathsf R}\) to indicate that a state \(\rho\) is in the register \(\mathsf R\). We write \(\operatorname{tr} \mathopen{}\mathclose{\left( \cdot }\right)\) to denote trace, \(\mathrm{tr}_{\mathsf R}(\cdot)\) to denote the partial trace over a register \(\mathsf R\), and \(\operatorname{tr}_{> n} \mathopen{}\mathclose{\left( \cdot }\right)\) to denote the partial trace over all but the first \(n\) qubits. We write \(I_n\) to denote the \(n\)-qubit identity transformation, or \(I\) when the number of qubits is implicit. We write \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}+ \mspace{.5mu}}\right\rangle = \frac{\mathopen{}\mathclose{\left\lvert\mspace{.5mu}0 \mspace{.5mu}}\right\rangle + \mathopen{}\mathclose{\left\lvert\mspace{.5mu}1 \mspace{.5mu}}\right\rangle}{\sqrt 2}, \mathopen{}\mathclose{\left\lvert\mspace{.5mu}- \mspace{.5mu}}\right\rangle = \frac{\mathopen{}\mathclose{\left\lvert\mspace{.5mu}0 \mspace{.5mu}}\right\rangle - \mathopen{}\mathclose{\left\lvert\mspace{.5mu}1 \mspace{.5mu}}\right\rangle}{\sqrt2}\) to denote the Hadamard basis states, and \(\text{\textrm{ctrl-}}U = \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0 \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}0 \mspace{.5mu}}\right\rvert \otimes I + \mathopen{}\mathclose{\left\lvert\mspace{.5mu}1 \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}1 \mspace{.5mu}}\right\rvert \otimes U\) to denote controlled-\(U\). For a (not necessarily normalized) vector \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) we write \(\psi = \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}\psi \mspace{.5mu}}\right\rvert\). We write \(\|\cdot\|\) to denote the vector 2-norm.

Let \(\|M\|_1 = \operatorname{tr} \mathopen{}\mathclose{\left( |M| }\right)\) denote the trace norm of a matrix \(M\), and let \(\mathop{\mathrm{td}}(\rho, \sigma) = \frac{1}{2} \|\rho - \sigma\|_1\) denote the trace distance between mixed states \(\rho\) and \(\sigma\). We use the fact that \[\label{eq:tdc} \mathop{\mathrm{td}}\mathopen{}\mathclose{\left(\Phi(\rho), \Phi(\sigma)}\right) \le \mathop{\mathrm{td}}(\rho, \sigma)\tag{1}\] for all channels \(\Phi\) and states \(\rho, \sigma\). We also use the following special case of the Fuchs-van de Graaf inequality: if \(\rho\) is a mixed state and \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) is a pure state then \[\label{eq:fvdg} \mathop{\mathrm{td}}(\rho, \psi) \le \sqrt{1 - \operatorname{tr} \mathopen{}\mathclose{\left( \rho \psi }\right)} = \sqrt{\operatorname{tr} \mathopen{}\mathclose{\left( \rho(I - \psi) }\right)}.\tag{2}\] (See e.g.Nielsen and Chuang NC10? for proofs of 1 2 .) In particular, if \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) and \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi \mspace{.5mu}}\right\rangle\) are pure states then \[\label{eq:tdps} \mathop{\mathrm{td}}\mathopen{}\mathclose{\left(\psi, \phi}\right) \le \sqrt{1 - \mathopen{}\mathclose{\left| \mathopen{}\mathclose{\left\langle \psi \middle| \phi }\right\rangle }\right|^2} = \sqrt{\mathopen{}\mathclose{\left(1 + \mathopen{}\mathclose{\left| \mathopen{}\mathclose{\left\langle \psi \middle| \phi }\right\rangle }\right|}\right) \mathopen{}\mathclose{\left(1 - \mathopen{}\mathclose{\left| \mathopen{}\mathclose{\left\langle \psi \middle| \phi }\right\rangle }\right|}\right)} \le \sqrt{2\mathopen{}\mathclose{\left(1 - \mathrm{Re}\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\langle \psi \middle| \phi }\right\rangle}\right)}\right)} \\ = \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle- \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi \mspace{.5mu}}\right\rangle}\right\|.\tag{3}\]

Quantum query models

By a quantum circuit making \(k\) queries to an \(n\)-qubit quantum oracle and its inverse, we mean a circuit of the form \(C = C_k Q_k C_{k-1} Q_{k-1} \dotsb C_0\) where each \(C_j\) is a unitary and each \(Q_j\) is a placeholder for either a “forward" or”backward" query. For an \(n\)-qubit unitary \(A\), by \(C^A\) we mean the unitary defined by substituting \(A\) and \(A^\dagger\) respectively for the forward and backward queries in \(C\). Claims about the quantum circuit complexity of \(C\) are in reference to the circuit \(C_k C_{k-1} \dotsb C_0\) defined by removing the queries from \(C\).

The following result of the author R21b? says that if the task of constructing a state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) reduces to that of constructing a state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi \mspace{.5mu}}\right\rangle\), then the task of approximately constructing \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) reduces to that of approximately constructing \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi \mspace{.5mu}}\right\rangle\):

Queries to a classical oracle (i.e.a Boolean function) can be modeled in either of two standard ways. In the first, a function \(f: \{0,1\}^{n} \mapsto \{0,1\}^{m}\) is encoded as the oracle \(U_f\) defined by \(U_f \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x, y \mspace{.5mu}}\right\rangle = \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x, y \oplus f(x) \mspace{.5mu}}\right\rangle\). In the second, which is only applicable when \(m=1\), the function \(f\) is instead encoded as the oracle \(V_f\) defined by \(V_f \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle = (-1)^{f(x)} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle\). These models are equivalent, because \(V_f = (I_n \otimes \mathopen{}\mathclose{\left\langle\mspace{.5mu}- \mspace{.5mu}}\right\vert) U_f (I_n \otimes \mathopen{}\mathclose{\left\lvert\mspace{.5mu}- \mspace{.5mu}}\right\rangle)\), and if \(g(x,y) = \bigoplus_{j=1}^m f(x)_j y_j\) (where the subscript \(j\) indicates the \(j\)’th bit of an \(m\)-bit string) then \(U_f = (I_n \otimes H^{\otimes m}) V_g (I_n \otimes H^{\otimes m})\) where \(H\) denotes the Hadamard gate BV97?, NC10?. We write \(C^f\) to abbreviate \(C^{U_f}\) or \(C^{V_f}\); since \(U_f\) and \(V_f\) are Hermitian we do not need to distinguish between forward and backward queries to a classical oracle.

We use the fact that parallel queries to classical oracles can be merged into a single query to a classical oracle, i.e. \[\begin{align} \label{eq:par-quer} &V_{f_1} \otimes \dotsb \otimes V_{f_k} = V_F &\text{for}& & F\mathopen{}\mathclose{\left(x^{(1)}, \dotsc, x^{(k)}}\right) = \bigoplus_{j=1}^k f_j\mathopen{}\mathclose{\left(x^{(j)}}\right) \end{align}\tag{4}\] for all functions \(f_1, \dotsc, f_k\). More generally, a collection of parallel queries of the form \(\bigotimes_j U_{f_j} \otimes \bigotimes_k V_{g_k}\) can be merged into a single query to a classical oracle, using the above equivalence between the query models.

\(\mathsf{QAC_f^0}\) circuits

A \(\mathsf{QAC_f^0}\) circuit Gre+02? is a constant-depth quantum circuit consisting of arbitrary one-qubit gates, as well as generalized Toffoli gates of arbitrary arity defined by \[\mathopen{}\mathclose{\left\lvert\mspace{.5mu}b,x \mspace{.5mu}}\right\rangle \mapsto \mathopen{}\mathclose{\left\lvert\mspace{.5mu}b \oplus \prod_{j=1}^n x_j, x \mspace{.5mu}}\right\rangle \quad \text{for} \quad b \in \{0,1\}, x = (x_1, \dotsc, x_n) \in \{0,1\}^{n},\] and fanout gates of arbitrary arity defined by \[\mathopen{}\mathclose{\left\lvert\mspace{.5mu}b,x \mspace{.5mu}}\right\rangle \mapsto \mathopen{}\mathclose{\left\lvert\mspace{.5mu}b, x \oplus b^n \mspace{.5mu}}\right\rangle \quad \text{for} \quad b \in \{0,1\}, x \in \{0,1\}^{n}.\]

The following results of the author R21b? are easy to prove:

The following lemma says that \(\mathsf{QAC_f^0} \subseteq \mathsf{QNC^1}\):

3 One-query state synthesis with postselection↩︎

In this section we prove the following lemma, which will be used in our proof of 2. This lemma implies an efficient one-query state synthesis algorithm given the ability to postselect on a measurement outcome that occurs with approximately constant probability:

The proof is organized as follows. In 3.1 we describe \(A_n\) and \(f\), and in 3.2 we prove that ?? holds. In 3.3 we prove that \(f\) can be computed in \(\mathrm{poly}(n)\) space; actually we prove this for a slightly different oracle \(f^\prime\) due to a subtlety involving floating-point arithmetic, but we show that ?? also holds with \(f^\prime\) in place of \(f\) (and with slightly different values of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tau \mspace{.5mu}}\right\rangle\) and \(z\)).

3.1 The algorithm↩︎

Our algorithm uses Clifford unitaries, which are products of Hadamard, phase, and CNOT gates, i.e.products of the gates \[\begin{align} &H = \frac{1}{\sqrt 2} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix},& &S = \begin{pmatrix} 1 & \\ & i \end{pmatrix},& &\mathit{CNOT} = \begin{pmatrix} 1 & & & \\ & 1 & & \\ & & & 1 \\ & & 1 & \end{pmatrix}. \end{align}\] Let \[\alpha = 0.35, \qquad \beta = \sqrt{1-\alpha^2} \approx 0.94, \qquad \gamma = (1-\beta)/\alpha \approx 0.18.\] For a complex number \(c\), let \(\mathop{\mathrm{sgnRe}}(c) = 1\) if the real part of \(c\) is nonnegative, and let \(\mathop{\mathrm{sgnRe}}(c) = -1\) otherwise. For a vector \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta \mspace{.5mu}}\right\rangle\in \mathopen{}\mathclose{\left(\mathbb{C}^2}\right)^{\otimes n}\) and a Clifford unitary \(C\), let \[\mathopen{}\mathclose{\left\lvert\mspace{.5mu}p_{\eta, C} \mspace{.5mu}}\right\rangle = C \cdot 2^{-n/2} \sum_{\mathclap{x \in \{0,1\}^{n}}} \mathop{\mathrm{sgnRe}}(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle) \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle.\] The following is implicit in Irani et al. INN+22?, as explained in 9:

Fix \(n, \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle, t = t(n)\) as in 11. For \(k \ge 0\), given states \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_0 \mspace{.5mu}}\right\rangle, \dotsc, \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_{k-1} \mspace{.5mu}}\right\rangle\), let \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k \mspace{.5mu}}\right\rangle = \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle- \alpha \sum_{j=0}^{k-1} \beta^j \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_j \mspace{.5mu}}\right\rangle\), and (using [lem:a5]) let \(C_k\) be a Clifford unitary such that the state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_k \mspace{.5mu}}\right\rangle = \mathopen{}\mathclose{\left\lvert\mspace{.5mu}p_{\eta_k, C_k} \mspace{.5mu}}\right\rangle\) satisfies \(\mathrm{Re} (\mathopen{}\mathclose{\left\langle \eta_k \middle| \phi_k }\right\rangle) \ge \alpha \|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k \mspace{.5mu}}\right\rangle\|\).

Let \(T = 2^t\) and \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\sigma \mspace{.5mu}}\right\rangle= \sqrt{\frac{1 - \beta}{1 - \beta^T}} \cdot \sum_{j=0}^{T-1} \sqrt{\beta^j} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}j \mspace{.5mu}}\right\rangle\). Observe that \[\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\sigma \mspace{.5mu}}\right\rangle= \sqrt{\frac{1-\beta}{1-\beta^T}} \mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}0 \mspace{.5mu}}\right\rangle + \beta^{2^{t-2}} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}1 \mspace{.5mu}}\right\rangle}\right) \otimes \mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}0 \mspace{.5mu}}\right\rangle + \beta^{2^{t-1}} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}1 \mspace{.5mu}}\right\rangle}\right) \otimes \dotsb \mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}0 \mspace{.5mu}}\right\rangle + \beta \mathopen{}\mathclose{\left\lvert\mspace{.5mu}1 \mspace{.5mu}}\right\rangle}\right) \otimes \mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}0 \mspace{.5mu}}\right\rangle + \beta^{1/2} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}1 \mspace{.5mu}}\right\rangle}\right),\] so there is a tensor product \(L\) of \(t\) one-qubit gates such that \(L\mathopen{}\mathclose{\left\lvert\mspace{.5mu}0^t \mspace{.5mu}}\right\rangle = \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\sigma \mspace{.5mu}}\right\rangle\).

The circuit \(A_n\) is described in 2, where \(\mathsf A\) is a \(t\)-qubit register and \(\mathsf B\) is an \(n\)-qubit register. Although the algorithm is phrased in terms of multiple queries, these can be merged into a single query using 4 and the surrounding discussion. Aaronson and Gottesman AG04? proved that every Clifford unitary can be written as a round of Hadamard gates, then a round of CNOT gates, then a round of phase gates, and so on in the sequence H-C-P-C-P-C-H-P-C-P-C with no ancillae (a “round" may consist of any number of layers of the given gate type). On [line:o7] [line:o8], by the description of a Clifford unitary we mean the concatenation of the descriptions of the rounds comprising that unitary, defined as follows:

• Since \(H^2 = I\) a round of Hadamard gates equals \(\bigotimes_{j=1}^n H^{x_j}\) for some string \(x = (x_1, \dotsc, x_n) \in \{0,1\}^{n}\). Call \(x\) the description of this round.

• Similarly since \(S^4 = I\), a round of phase gates can be described by a string in \(\{0,1,2,3\}^n\).

• A round of CNOT gates acts on the standard basis as \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle \mapsto \mathopen{}\mathclose{\left\lvert\mspace{.5mu}Mx \mspace{.5mu}}\right\rangle\) for some \(M \in \mathrm{GL}_n(\mathbb{F}_2)\), because this holds for a single CNOT gate and \(\mathrm{GL}_n(\mathbb{F}_2)\) is closed under multiplication. Call the pair \((M, M^{-1})\) the description of this round.

We now describe the \(\mathsf{QAC_f^0}\) implementation of [line:o8] in greater detail. Given an index \(j\) and descriptions of Clifford unitaries \(C_0, \dotsc, C_{T-1}\), the description of \(C_j\) can be computed using 8. A polynomial-size \(\mathsf{QAC_f^0}\) circuit can then implement \(C_j\) by successively implementing the rounds comprising \(C_j\). Rounds of Hadamard and phase gates can be implemented trivially. To implement a round of CNOT gates acting as \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle \mapsto \mathopen{}\mathclose{\left\lvert\mspace{.5mu}Mx \mspace{.5mu}}\right\rangle\), first compute \(y = Mx\), and then uncompute \(x = M^{-1} y\) controlled on \(y\), using that parity is in \(\mathsf{QAC_f^0}\) Gre+02?. Since \(\varepsilon(n) \ge \exp(-\mathrm{poly}(n))\) it holds that \(t \le O(\log n)\) and \(T \le \mathrm{poly}(n)\), so \(A_n\) requires \(\mathrm{poly}(n)\) qubits.

3.2 Proof of correctness↩︎

The string \(z\) referred to in the lemma is the concatenation of the descriptions of \(C_0, \dotsc, C_{T-1}\) along with some number of zeros. Let \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi \mspace{.5mu}}\right\rangle\) denote the final state in \(\mathsf{AB}\), let \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle= \mathopen{}\mathclose{\left\langle\mspace{.5mu}0^t \mspace{.5mu}}\right\vert_{\mathsf A} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi \mspace{.5mu}}\right\rangle\), and let \[\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tau \mspace{.5mu}}\right\rangle = \frac{\mathopen{}\mathclose{\left(I - \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0^t \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}0^t \mspace{.5mu}}\right\rvert}\right)_{\mathsf A} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi \mspace{.5mu}}\right\rangle}{\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left(I - \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0^t \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}0^t \mspace{.5mu}}\right\rvert}\right)_{\mathsf A} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi \mspace{.5mu}}\right\rangle}\right\|} = \frac{\mathopen{}\mathclose{\left(I - \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0^t \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}0^t \mspace{.5mu}}\right\rvert}\right)_{\mathsf A} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi \mspace{.5mu}}\right\rangle}{\sqrt{1 - \|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle\|^2}}.\] Then \[\begin{align} &\mathopen{}\mathclose{\left\|A_n^f \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0\dotsc 0 \mspace{.5mu}}\right\rangle- \mathopen{}\mathclose{\left(\gamma \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0^t \mspace{.5mu}}\right\rangle \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle+ \sqrt{1 - \gamma^2} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tau \mspace{.5mu}}\right\rangle}\right) \mathopen{}\mathclose{\left\lvert\mspace{.5mu}z \mspace{.5mu}}\right\rangle}\right\|^2 \\ &= \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi \mspace{.5mu}}\right\rangle- \mathopen{}\mathclose{\left(\gamma \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0^t \mspace{.5mu}}\right\rangle \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle+ \sqrt{1 - \gamma^2} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tau \mspace{.5mu}}\right\rangle}\right)}\right\|^2 \\ &= \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}0^t \mspace{.5mu}}\right\rangle \mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle- \gamma \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle}\right) + \mathopen{}\mathclose{\left(\sqrt{1 - \|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle\|^2} - \sqrt{1 - \gamma^2}}\right) \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tau \mspace{.5mu}}\right\rangle}\right\|^2 \\ &= \|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle- \gamma \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\|^2 + \mathopen{}\mathclose{\left(\sqrt{1 - \|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle\|^2} - \sqrt{1 - \gamma^2}}\right)^2 \\ &= \|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle- \gamma \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\|^2 + \mathopen{}\mathclose{\left(\frac{\mathopen{}\mathclose{\left(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle\| + \gamma}\right) \mathopen{}\mathclose{\left(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle\| - \gamma}\right)}{\sqrt{1 - \|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle\|^2} + \sqrt{1 - \gamma^2}}}\right)^2 \\ &\le \|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle- \gamma \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\|^2 + \frac{(1 + \gamma)^2}{1 - \gamma^2} \mathopen{}\mathclose{\left(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle\| - \gamma}\right)^2 &\text{because \|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle\| \le 1} \\ &\le \mathopen{}\mathclose{\left(1 + \frac{(1 + \gamma)^2}{1-\gamma^2}}\right) \|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle- \gamma \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\|^2 &\text{by the triangle inequality} \\ &\le 2.45 \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle- \gamma \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle}\right\|^2, \end{align}\] so \[\mathopen{}\mathclose{\left\|A_n^f \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0\dotsc 0 \mspace{.5mu}}\right\rangle- \mathopen{}\mathclose{\left(\gamma \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0^t \mspace{.5mu}}\right\rangle \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle+ \sqrt{1 - \gamma^2} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tau \mspace{.5mu}}\right\rangle}\right) \mathopen{}\mathclose{\left\lvert\mspace{.5mu}z \mspace{.5mu}}\right\rangle}\right\| \le 1.57 \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle- \gamma \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle}\right\|.\]

Inspection of 2 reveals that \[\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi \mspace{.5mu}}\right\rangle = L^\dagger_{\mathsf A} \mathopen{}\mathclose{\left(\sum_{j<T} \mathopen{}\mathclose{\left(j_{\mathsf A} \otimes C_j \sum_{\mathclap{x \in \{0,1\}^{n}}} \mathop{\mathrm{sgnRe}}\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta_j \mspace{.5mu}}\right\vert C_j \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle}\right) x_{\mathsf B}}\right)}\right) \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\sigma \mspace{.5mu}}\right\rangle_{\mathsf A} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}+^n \mspace{.5mu}}\right\rangle_{\mathsf B},\] so \[\begin{align} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle &= \mathopen{}\mathclose{\left\langle\mspace{.5mu}\sigma \mspace{.5mu}}\right\vert_{\mathsf A} \mathopen{}\mathclose{\left(\sum_{j<T} \mathopen{}\mathclose{\left(j_{\mathsf A} \otimes C_j \cdot 2^{-n/2} \sum_{\mathclap{x \in \{0,1\}^{n}}} \mathop{\mathrm{sgnRe}}\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta_j \mspace{.5mu}}\right\vert C_j \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle}\right) \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle_{\mathsf B}}\right)}\right) \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\sigma \mspace{.5mu}}\right\rangle_{\mathsf A} \\ &= \sum_{j<T} |\mathopen{}\mathclose{\left\langle j \middle| \sigma }\right\rangle|^2 \mathopen{}\mathclose{\left\lvert\mspace{.5mu}p_{\eta_j, C_j} \mspace{.5mu}}\right\rangle_{\mathsf B} = \frac{1-\beta}{1-\beta^T} \sum_{j<T} \beta^j \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_j \mspace{.5mu}}\right\rangle = \frac{1-\beta}{1-\beta^T} \cdot \frac{\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle- \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_T \mspace{.5mu}}\right\rangle}{\alpha} = \frac{\gamma \mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle- \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_T \mspace{.5mu}}\right\rangle}\right)}{1-\beta^T}, \end{align}\] and therefore by the triangle inequality \[\begin{align} \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta \mspace{.5mu}}\right\rangle- \gamma \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle}\right\| &= \frac{\gamma}{1-\beta^T} \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle- \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_T \mspace{.5mu}}\right\rangle}\right) - \mathopen{}\mathclose{\left(1 - \beta^T}\right) \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle}\right\| = \frac{\gamma}{1-\beta^T} \mathopen{}\mathclose{\left\|\beta^T \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle- \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_T \mspace{.5mu}}\right\rangle}\right\| \\ &\le \frac{\gamma}{1-\beta} \mathopen{}\mathclose{\left(\beta^T + \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_T \mspace{.5mu}}\right\rangle}\right\|}\right) \le 2.86 \mathopen{}\mathclose{\left(\beta^T + \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_T \mspace{.5mu}}\right\rangle}\right\|}\right). \end{align}\]

We prove by induction on \(k\) that \(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k \mspace{.5mu}}\right\rangle\| \le \beta^k\) for all \(k\). The base case \(k=0\) holds because \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_0 \mspace{.5mu}}\right\rangle = \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\). If the claim holds for \(k\), then \[\begin{align} \|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_{k+1} \mspace{.5mu}}\right\rangle\|^2 &= \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k \mspace{.5mu}}\right\rangle - \alpha \beta^k \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_k \mspace{.5mu}}\right\rangle}\right\|^2 = \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k \mspace{.5mu}}\right\rangle}\right\|^2 - 2 \alpha \beta^k \mathrm{Re}(\mathopen{}\mathclose{\left\langle \eta_k \middle| \phi_k }\right\rangle) + \alpha^2 \beta^{2k} \\ &\le \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k \mspace{.5mu}}\right\rangle}\right\|^2 - 2 \alpha^2 \beta^k \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k \mspace{.5mu}}\right\rangle}\right\| + \alpha^2 \beta^{2k}, \end{align}\] where the inequality is by the definition of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_k \mspace{.5mu}}\right\rangle\). This bound is convex as a function of \(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k \mspace{.5mu}}\right\rangle\|\), so it achieves its maximum over \(0 \le \|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k \mspace{.5mu}}\right\rangle\| \le \beta^k\) at either \(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k \mspace{.5mu}}\right\rangle\| = 0\) or \(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k \mspace{.5mu}}\right\rangle\| = \beta^k\). In both cases it follows straightforwardly that \(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_{k+1} \mspace{.5mu}}\right\rangle\| \le \beta^{k+1}\), using in the \(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k \mspace{.5mu}}\right\rangle\| = 0\) case the fact that \(\alpha < \beta\), and using in the \(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k \mspace{.5mu}}\right\rangle\| = \beta^k\) case the fact that \(1-\alpha^2 = \beta^2\).

Finally, writing \(\varepsilon= \varepsilon(n)\) it holds that \[\beta^T = \beta^{2^t} = \beta^{2^{\ceil{\log \log(1/\varepsilon)} + 7}} \le \beta^{128 \log(1/\varepsilon)} = \varepsilon^{128 \log(1/\beta)} \le \varepsilon^{8.36} \le \varepsilon\cdot (1/2)^{7.36} \le 0.01 \varepsilon,\] so \[\mathopen{}\mathclose{\left\|A_n^f \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0\dotsc 0 \mspace{.5mu}}\right\rangle- \mathopen{}\mathclose{\left(\gamma \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0^t \mspace{.5mu}}\right\rangle \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle+ \sqrt{1 - \gamma^2} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tau \mspace{.5mu}}\right\rangle}\right) \mathopen{}\mathclose{\left\lvert\mspace{.5mu}z \mspace{.5mu}}\right\rangle}\right\| \le 1.57 \cdot 2.86 \cdot 2 \beta^T \le \varepsilon.\]

3.3 Computing \(f\) in \(\mathrm{poly}(n)\) space↩︎

Recall from 2 that the oracle \(f\) encodes, for each \(0 \le j < T\), a description of the Clifford unitary \(C_j\) and the values \(\mathop{\mathrm{sgnRe}}(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta_j \mspace{.5mu}}\right\vert C_j \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle)\) for \(x \in \{0,1\}^{n}\). The problem is that \(\mathop{\mathrm{sgnRe}}(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta_j \mspace{.5mu}}\right\vert C_j \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle)\) depends discontinuously on \(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta_j \mspace{.5mu}}\right\vert C_j \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle\), and \(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta_j \mspace{.5mu}}\right\vert C_j \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle\) can only be computed approximately due to (exponentially small) error in the description of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_j \mspace{.5mu}}\right\rangle\) and in floating-point arithmetic. Therefore we will use a slightly different oracle \(f^\prime\). Let \(\delta = 0.01 \cdot \beta^{2T} \ge \exp(-\mathrm{poly}(n))\); we will use \(\delta\) to define bounds on the floating-point error in certain calculations.

The new oracle \(f^\prime\)

For a vector \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta \mspace{.5mu}}\right\rangle\in \mathopen{}\mathclose{\left(\mathbb{C}^2}\right)^{\otimes n}\) and a Clifford unitary \(C\), let \[\mathopen{}\mathclose{\left\lvert\mspace{.5mu}p_{\eta, C}^\prime \mspace{.5mu}}\right\rangle = C \cdot 2^{-n/2} \sum_{\mathclap{x \in \{0,1\}^{n}}} \mathop{\mathrm{sgnRe}}\mathopen{}\mathclose{\left(\widetilde{\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle}}\right) \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle,\] where \(\widetilde{\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle}\) is a value computable in \(\mathrm{poly}(n)\) space (given descriptions of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta \mspace{.5mu}}\right\rangle\) and \(C\)) such that \(\mathopen{}\mathclose{\left| \widetilde{\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle} - \mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle }\right| \le 2^{-n/2} \delta\). For example we may compute \(\widetilde{\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle}\) by a “sum over histories" argument, i.e.write \(C = R_1 \dotsb R_{11}\) as the product of the rounds \(R_i\) comprising the description of \(C\), and use that \[\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vert C \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle = \sum_{\mathclap{y_0, \dotsc, y_{10} \in \{0,1\}^{n}}} \mathopen{}\mathclose{\left\langle \eta \middle| y_0 }\right\rangle \cdot \prod_{i=1}^{10} \mathopen{}\mathclose{\left\langle\mspace{.5mu}y_{i-1} \mspace{.5mu}}\right\vert R_i \mathopen{}\mathclose{\left\lvert\mspace{.5mu}y_i \mspace{.5mu}}\right\rangle \cdot \mathopen{}\mathclose{\left\langle\mspace{.5mu}y_{10} \mspace{.5mu}}\right\vert R_{11} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle.\]

For a state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta \mspace{.5mu}}\right\rangle\) and Clifford unitary \(C\), if \(|\mathrm{Re}(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle)| > 2^{-n/2} \delta\) then \(\mathop{\mathrm{sgnRe}}\mathopen{}\mathclose{\left(\widetilde{\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle}}\right) = \mathop{\mathrm{sgnRe}}\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle}\right)\), so by the triangle inequality \[\begin{align} \mathopen{}\mathclose{\left| \mathrm{Re} \mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\langle \eta \middle| p_{\eta, C}^\prime }\right\rangle}\right) - \mathrm{Re} \mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\langle \eta \middle| p_{\eta, C} }\right\rangle}\right) }\right| &= \mathopen{}\mathclose{\left| 2^{-n/2} \sum_{\mathclap{x \in \{0,1\}^{n}}} \mathopen{}\mathclose{\left(\mathop{\mathrm{sgnRe}}\mathopen{}\mathclose{\left(\widetilde{\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle}}\right) - \mathop{\mathrm{sgnRe}}\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle}\right)}\right) \mathrm{Re}(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle) }\right| \\ &\le 2^{-n/2} \sum_{\mathclap{x \in \{0,1\}^{n}}} 2 \cdot 2^{-n/2} \delta = 2\delta. \end{align}\] Therefore by [lem:a5], for all states \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta \mspace{.5mu}}\right\rangle\) there exists a Clifford unitary \(C\) such that \(\mathrm{Re}\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\langle \eta \middle| p^\prime_{\eta, C} }\right\rangle}\right) \ge \alpha - 2 \delta\).

For \(k \ge 0\), given states \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_0^\prime \mspace{.5mu}}\right\rangle, \dotsc, \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_{k-1}^\prime \mspace{.5mu}}\right\rangle\), let \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle = \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle- \alpha \sum_{j=0}^{k-1} \beta^j \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_j^\prime \mspace{.5mu}}\right\rangle\), and let \(C_k^\prime\) be a Clifford unitary such that the state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_k^\prime \mspace{.5mu}}\right\rangle = \mathopen{}\mathclose{\left\lvert\mspace{.5mu}p_{\eta_k^\prime, C_k^\prime}^\prime \mspace{.5mu}}\right\rangle\) satisfies \(\mathrm{Re} \mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\langle \eta_k^\prime \middle| \phi_k^\prime }\right\rangle}\right) \ge \mathopen{}\mathclose{\left(\alpha - 2 \delta}\right) \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle}\right\| - \delta\). Let \(f^\prime\) be the oracle that encodes, for each \(0 \le j < T\), the description of \(C_j^\prime\) and \(\mathop{\mathrm{sgnRe}}\mathopen{}\mathclose{\left(\widetilde{\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta_j^\prime \mspace{.5mu}}\right\vert C_j^\prime \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle}}\right)\) for \(x \in \{0,1\}^{n}\).

Computing \(f^\prime\) in \(\mathrm{poly}(n)\) space

Given the description of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta^\prime_k \mspace{.5mu}}\right\rangle\), a valid Clifford unitary \(C_k^\prime\) can be found in \(\mathrm{poly}(n)\) space by performing a brute-force search for a Clifford unitary \(C\) such that \(\mathrm{Re}\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\langle \eta^\prime_k \middle| p^\prime_{\eta^\prime_k, C} }\right\rangle}\right) \ge \mathopen{}\mathclose{\left(\alpha - 2 \delta}\right) \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle}\right\|\). (The “extra" \(\delta\) term in the definition of \(C_k^\prime\) allows for floating-point error in the calculation of \(\mathrm{Re}\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\langle \eta^\prime_k \middle| p^\prime_{\eta^\prime_k, C} }\right\rangle}\right) - \mathopen{}\mathclose{\left(\alpha - 2 \delta}\right) \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle}\right\|\) during this search.) The description of the vector \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_{k+1}^\prime \mspace{.5mu}}\right\rangle = \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle - \alpha \beta^k \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_k^\prime \mspace{.5mu}}\right\rangle\) can be subsequently computed in \(\mathrm{poly}(n)\) space. Since \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_0^\prime \mspace{.5mu}}\right\rangle = \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\), it follows by induction that descriptions of \(C_k^\prime\) and \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_{k+1}^\prime \mspace{.5mu}}\right\rangle\) for \(k \ge 0\) can be computed in \((k+1) \mathrm{poly}(n)\) space, by answering queries to individual bits of the description of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle\) recursively. Since \(T \le \mathrm{poly}(n)\), descriptions of \(C_k^\prime\) and \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle\) for \(0 \le k < T\) can be computed in \(\mathrm{poly}(n)\) space. Finally, the value \(\mathop{\mathrm{sgnRe}}\mathopen{}\mathclose{\left(\widetilde{\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\vert C_k^\prime \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle}}\right)\) can by definition be computed in \(\mathrm{poly}(n)\) space given descriptions of \(C_k^\prime\) and \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle\).

Constructing \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) using \(f^\prime\)

We now show that ?? still holds with \(f^\prime\) substituted for \(f\). By reasoning similar to that in 3.2, there exist a state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tau^\prime \mspace{.5mu}}\right\rangle\) and a string \(z^\prime\) such that \(\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\langle\mspace{.5mu}0^t \mspace{.5mu}}\right\vert \otimes I}\right) \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tau^\prime \mspace{.5mu}}\right\rangle = 0\) and \[\mathopen{}\mathclose{\left\|A_n^{f^\prime} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0\dotsc 0 \mspace{.5mu}}\right\rangle- \mathopen{}\mathclose{\left(\gamma \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0^t \mspace{.5mu}}\right\rangle \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle+ \sqrt{1 - \gamma^2} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tau^\prime \mspace{.5mu}}\right\rangle}\right) \mathopen{}\mathclose{\left\lvert\mspace{.5mu}z^\prime \mspace{.5mu}}\right\rangle}\right\| \le 1.57 \cdot 2.86 \mathopen{}\mathclose{\left(\beta^T + \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_T^\prime \mspace{.5mu}}\right\rangle}\right\|}\right).\]

We prove by induction on \(k\) that \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle}\right\|^2 \le \beta^{2k} + 0.1 \beta^{2T} \sum_{j = 0}^{k-1} \beta^j\) for all \(k\). The case \(k=0\) holds trivially. If the claim holds for \(k\), then (similarly to in 3.2) \[\begin{align} \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_{k+1}^\prime \mspace{.5mu}}\right\rangle}\right\|^2 &\le \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle}\right\|^2 - 2 \alpha \beta^k \mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left(\alpha - 2 \delta}\right) \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle}\right\| - \delta}\right) + \alpha^2 \beta^{2k} \\ &= \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle}\right\|^2 - 2 \alpha^2 \beta^k \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle}\right\| + \alpha^2 \beta^{2k} + \beta^k \cdot 2 \alpha \mathopen{}\mathclose{\left(2 \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle}\right\| + 1}\right) \delta. \end{align}\] By the triangle inequality \[\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle}\right\| = \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle- \alpha \sum_{j=0}^{k-1} \beta^j \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_j^\prime \mspace{.5mu}}\right\rangle}\right\| \le 1 + \alpha \sum_{j=0}^{k-1} \beta^j \le 1 + \frac{\alpha{1-\beta}}{=} 1 + \frac{1}{\gamma},\] so recalling that \(\delta = 0.01 \beta^{2T}\) it holds that \[2\alpha \mathopen{}\mathclose{\left(2 \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle}\right\| + 1}\right) \delta \le 2\alpha \mathopen{}\mathclose{\left(2 \mathopen{}\mathclose{\left(1 + \frac{1}{\gamma}}\right) + 1}\right) \cdot 0.01 \beta^{2T} < 0.1 \beta^{2T},\] and therefore \[\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_{k+1}^\prime \mspace{.5mu}}\right\rangle}\right\|^2 \le \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle}\right\|^2 - 2 \alpha^2 \beta^k \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_k^\prime \mspace{.5mu}}\right\rangle}\right\| + \alpha^2 \beta^{2k} + \beta^k \cdot 0.1 \beta^{2T}.\] The rest of the inductive argument follows by reasoning similar to that in 3.2.

Therefore \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta_T^\prime \mspace{.5mu}}\right\rangle}\right\| \le \sqrt{\beta^{2T} + 0.1 \beta^{2T} / (1-\beta)} < 1.7 \beta^T\), and the rest of the proof is similar to that in 3.2.

4 State synthesis algorithms: removing the postselection↩︎

In this section we formally state and prove both the non-clean, one-query version and the clean, four-query version of 2. We also give a clean, ten-query state synthesis algorithm that has two advantages compared to the four-query algorithm. First, the ten-query algorithm is simpler. Second, the oracle in the ten-query algorithm requires fewer input bits, which will be relevant when we prove circuit upper bounds for approximately constructing arbitrary states (i.e.[thm:ubs]).

All of these algorithms invoke the algorithm from 11. Let \(\gamma\) be the constant from 11. Given an \(n\)-qubit state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) and parameter \(\varepsilon\), when we say “define \(A, f, \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tau \mspace{.5mu}}\right\rangle, z, t\) as in 11 with respect to \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) and error tolerance \(\varepsilon\)", we mean that \(A\) is the circuit \(A_n\) from 11 and all other variables have the same meaning as in 11. We will write \(\varepsilon= \varepsilon(n)\) and \(t = t(n)\) when \(n\) is implicit. In the four- and ten-query algorithms not all of the queries will be to precisely the same function, but this can easily be addressed as discussed in the paragraph after 1. Although our results will be stated in terms of \(\mathsf{QAC_f^0}\) circuits, similar results hold for circuits consisting of one- and two-qubit gates by 10.

4.1 The one-query algorithm↩︎

We prove the following by using parallel repetition to boost the success probability from 11:

4.2 The ten-query algorithm↩︎

We prove the following by using amplitude amplification to boost the success probability from 11:

4.3 The four-query algorithm↩︎

The following statement is identical to 13 except with “four" instead of”ten", and is proved by a combination of the ideas from [sec:oqa] [sec:eqa]:

5 State complexity classes↩︎

In this section we define various state complexity classes and establish some basic facts about them as preparation for the proof that \(\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}(6)\). Although for simplicity these classes are defined in terms of state sequences where the \(n\)’th state is on \(n\) qubits, the definitions (and related results) generalize easily to sequences where the \(n\)’th state is on \(\mathrm{poly}(n)\) qubits. Much of the language in this section is closely modeled on passages from Rosenthal and Yuen RY21? and Metger and Yuen MY23?.

5.1 \(\mathsf{polyL}\)-explicit state sequences↩︎

Recall from 2 that we define an \(\varepsilon\)-precision description of a pure state \(\sum_{x \in \{0,1\}^{n}} \alpha_x \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle\) to be a tuple \(\mathopen{}\mathclose{\left(\tilde{\alpha}_x}\right)_{x \in \{0,1\}^{n}}\) of complex numbers specified exactly in binary such that \(\mathopen{}\mathclose{\left| \tilde{\alpha}_x - \alpha_x }\right| \le \varepsilon\) for all \(x\). We define a similar notion for mixed states: an \(\varepsilon\)-precision description of a mixed state \(\sum_{x,y \in \{0,1\}^{n}} \rho_{x,y} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}y \mspace{.5mu}}\right\rvert\) is a tuple \(\mathopen{}\mathclose{\left(\tilde{\rho}_{x,y}}\right)_{x,y \in \{0,1\}^{n}}\) of complex numbers specified exactly in binary such that \(\mathopen{}\mathclose{\left| \tilde{\rho}_{x,y} - \rho_{x,y} }\right| \le \varepsilon\) for all \(x,y\).

5.2 The class \(\mathsf{statePSPACE}\)↩︎

For convenience we use the universal gate set \(\{ H, \mathit{CNOT}, T \}\) NC10? in the following definition, although our results hold for any universal gate set consisting of gates with algebraic entries.

We abuse notation and write \((\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_n \mspace{.5mu}}\right\rangle)_n \in \mathsf{statePSPACE}_\delta\) if \((\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_n \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}\psi_n \mspace{.5mu}}\right\rvert)_n\) is in \(\mathsf{statePSPACE}_\delta\). Also recall that the definitions of state complexity classes such as \(\mathsf{statePSPACE}_\delta\) generalize easily to sequences where the \(n\)’th state is on \(\mathrm{poly}(n)\) qubits. With this in mind we can state the following result, which in particular implies that \(\mathsf{statePSPACE_{exp}}\) is closed under purification:

We also use the following:

5.3 Quantum interactive protocols↩︎

Since in quantum computing the standard model of computation is the quantum circuit model (rather than quantum Turing machines), we model the verifier in a quantum interactive protocol as a sequence of verifier circuits, one for each input length. A verifier circuit is itself a tuple of quantum circuits that correspond to the operations performed by the verifier in each round of the protocol. Below we describe this more formally.

The case where the verifier sends the first message is illustrated in 6. For a register \(\mathsf A\) let \(\mathrm{D}(\mathsf A)\) denote the set of density matrices on \(\mathsf A\). A \(2r\)-message quantum verifier circuit \(C = (C_j)_{j \in [r+1]}\) is a tuple of general quantum circuits, where \(C_1: \mathrm{D}(\mathsf W_0) \to \mathrm{D}(\mathsf W_1 \mathsf M_1)\), and \(C_j: \mathrm{D}(\mathsf W_{j-1} \mathsf M_{2j-2}) \to \mathrm{D}(\mathsf W_j \mathsf M_{2j-1})\) for \(2 \le j \le r\), and \(C_{r+1}: \mathrm{D}(\mathsf W_r \mathsf M_{2r}) \to \mathrm{D}(\mathsf Z \mathsf W_{r+1} \mathsf S)\). A quantum prover \(P\) for such a verifier circuit \(C\) is a tuple of quantum channels \((P_j)_{j \in [r]}\) where \(P_j: \mathrm{D}(\mathsf Q_{j-1} \mathsf M_{2j-1}) \to \mathrm{D}(\mathsf Q_j \mathsf M_{2j})\). We think of \(\mathsf W_j\) (resp.\(\mathsf Q_j\)) as the verifier’s (resp.prover’s) private memory at a given time, and we think of \(\mathsf M_j\) as the \(j\)’th message. At the end of the protocol, the verifier produces a one-qubit register \(\mathsf Z\) indicating whether to accept or reject, and a register \(\mathsf S\) containing an output state.

Let \(x\) denote a string whose length is at most the number of qubits in \(\mathsf W_0\). We write \(C(x) \mathord{\rightleftarrows}P\) to denote the interaction between the verifier circuit \(C\) and the prover \(P\) on input \(x\), which means applying the channels \(C_j\) and \(P_j\) as pictured in 6 to the initial state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}x, 0\dotsc 0 \mspace{.5mu}}\right\rangle_{\mathsf W_0} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0\dotsc 0 \mspace{.5mu}}\right\rangle_{\mathsf Q_0}\). We say that \(C(x) \mathord{\rightleftarrows}P\) accepts (resp.rejects) if measuring \(\mathsf Z\) in the standard basis yields the outcome \(1\) (resp.\(0\)). If \(C(x) \mathord{\rightleftarrows}P\) accepts with nonzero probability, then by the output of \(C(x) \mathord{\rightleftarrows}P\) conditioned on accepting we mean the reduced state in \(\mathsf S\) conditioned on \(C(x) \mathord{\rightleftarrows}P\) accepting. In other words if \(\rho\) denotes the output of \(C_{r+1}\), then the output state conditioned on accepting is \[\mathrm{tr}_{\mathsf W_{r+1}} \mathopen{}\mathclose{\left(\frac{\mathopen{}\mathclose{\left\langle\mspace{.5mu}1 \mspace{.5mu}}\right\vert_{\mathsf Z} \rho \mathopen{}\mathclose{\left\lvert\mspace{.5mu}1 \mspace{.5mu}}\right\rangle_{\mathsf Z}}{\operatorname{tr} \mathopen{}\mathclose{\left( \mathopen{}\mathclose{\left\langle\mspace{.5mu}1 \mspace{.5mu}}\right\vert_{\mathsf Z} \rho \mathopen{}\mathclose{\left\lvert\mspace{.5mu}1 \mspace{.5mu}}\right\rangle_{\mathsf Z} }\right)}}\right).\]

By dilating we can assume without loss of generality that the prover’s channels are all unitary, i.e.\(P_j(A) = U_j A U^\dagger_j\) for some unitary \(U_j\), and similarly for the verifier. (This is the purpose of the registers \(\mathsf Q_0, \mathsf Q_r, \mathsf W_{r+1}\).) We always assume that the prover is unitary, but only sometimes assume that the verifier is unitary.

We can model interactions in which the prover sends the first (nontrivial) message by requiring \(\mathsf M_1\) to only convey the input string \(x\) that was in \(\mathsf W_0\). In this case there are only \(2r-1\) (nontrivial) messages.

We say that a sequence of quantum verifier circuits \((V_n)_n\) is uniform if the total number gates in all circuits in \(V_n\) is \(\mathrm{poly}(n)\), and the descriptions of the circuits in \(V_n\) can be computed in \(\mathrm{poly}(n)\) time as a function of \(n\). For \(m: \mathbb{N}\to \mathbb{N}\), an \(m\)-message quantum verifier is a uniform sequence \((V_n)_n\) of quantum verifier circuits where \(V_n\) defines a protocol with \(m(n)\) messages. These \(m(n)\) messages include messages sent by both the verifier and prover, and do not include the trivial first message sent by the verifier if \(m(n)\) is odd.

5.4 The class \(\mathsf{QIP}(3)\)↩︎

The class \(\mathsf{QIP}\) is the standard quantum analogue of the complexity class \(\mathsf{IP}\). For our purposes we will only need to define the three-message version of \(\mathsf{QIP}\), known as \(\mathsf{QIP}(3)\). Below we abbreviate \(V_{|x|}(x) \mathord{\rightleftarrows}P\) by \(V(x) \mathord{\rightleftarrows}P\).

We remark that the converse inclusion \(\mathsf{QIP}(3) \subseteq \mathsf{PSPACE}\) holds as well jain2011qip?. It is straightforward to generalize 22 from decision problems to functions:

5.5 The classes \(\mathsf{stateQIP}(m)\) and \(\mathsf{stateQIP}\)↩︎

6 Proof that \(\mathsf{statePSPACE}\subseteq \mathsf{stateQIP}(6)\)↩︎

In this section we use the background from 5 to prove 5, i.e.that \(\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}(6)\). Let \((\rho_n)_n \in \mathsf{statePSPACE}\) and let \(\varepsilon(n), \delta(n) = 1/\mathrm{poly}(n)\); below we prove that \((\rho_n)_n\) is in \(\mathsf{stateQIP}_{\varepsilon, \delta}(6)\) which establishes the theorem.

6.1 The protocol↩︎

Since \((\rho_n)_n\) is in \(\mathsf{statePSPACE}\) there exists a sequence \((\sigma_n)_n \in \mathsf{statePSPACE}_0\) such that \(\mathop{\mathrm{td}}\mathopen{}\mathclose{\left(\rho_n, \sigma_n}\right) \le \delta(n)/2\). By 19 there exists a sequence of pure states \((\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_n \mspace{.5mu}}\right\rangle)_n \in \mathsf{statePSPACE_{exp}}\) such that the reduced state on the first \(n\) qubits of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_n \mspace{.5mu}}\right\rangle\) equals \(\sigma_n\). By 20 the sequence \((\psi_n)_n\) is \(\mathsf{polyL}\)-explicit, so by 16 the sequence \(\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_n \mspace{.5mu}}\right\rangle}\right)_n\) is \(\mathsf{polyL}\)-explicit up to global phases. Therefore by 12 there exists a uniform sequence of polynomial-size quantum circuits \((A_n)_n\), making one query to a \(\mathsf{PSPACE}\)-computable function \(f\), such that the reduced state on the initial qubits of \(A_n^f \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0\dotsc 0 \mspace{.5mu}}\right\rangle\) is within \(2^{-n}\) trace distance of \(\psi_n\), and furthermore \((A_n)_n\) does not depend on \((\rho_n)_n\). Henceforth we will fix \(n\) and write \(\rho = \rho_n, \varepsilon= \varepsilon(n)\) and so on for brevity.

Let \(m = \mathrm{poly}(n)\) be the number of qubits on which \(A\) acts. By the discussion in 2, we can assume without loss of generality that \(f\) has a single output bit and that the query in \(A^f\) is of the form \(D = \sum_{x \in \{0,1\}^{m}} (-1)^{f(x)} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}x \mspace{.5mu}}\right\rvert\). Write \(A^f \mathopen{}\mathclose{\left\lvert\mspace{.5mu}0^m \mspace{.5mu}}\right\rangle = C D \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi \mspace{.5mu}}\right\rangle\) where \(C\) is the portion of \(A\) applied after the query, and \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi \mspace{.5mu}}\right\rangle\) is the state constructed by the portion of \(A\) applied before the query.

Let \(t = \mathrm{poly}(n)\) be a parameter to be chosen later, and for \(x_1, \dotsc, x_t \in \{0,1\}^{m}\) let \(F \mathopen{}\mathclose{\left(x_1, \dotsc, x_t}\right) = \mathopen{}\mathclose{\left(f \mathopen{}\mathclose{\left(x_1}\right), \dotsc, f \mathopen{}\mathclose{\left(x_t}\right)}\right)\). Since \(f\) is \(\mathsf{PSPACE}\)-computable, so is \(F\). Let \(V_F\) be the three-message quantum verifier circuit for \(F\) guaranteed to exist by 23, with soundness parameter \(2^{-2n}\). As mentioned in 5.3 we can assume without loss of generality that \(V_F\) is unitary. We can also assume without loss of generality that \(V_F\) preserves the classical state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle\) of its input register, e.g.by defining a verifier circuit that makes a copy of \(x\) and simulates \(V_F\) on the copy.

We name certain registers associated with \(V_F\) as follows. Let \(\mathsf A\) be the input register, and write \(\mathsf A = \mathsf A_1 \dotsb \mathsf A_t\) where each \(\mathsf A_j\) is an \(m\)-qubit register. Let \(\mathsf S\) be the output register (which on input \(x\), ideally holds \(F(x)\)), and write \(\mathsf S = \mathsf S_1 \dotsb \mathsf S_t\) where each \(\mathsf S_j\) is a one-qubit register. Let \(\mathsf Z\) be the one-qubit register indicating whether to accept or reject, and let \(\mathsf W\) be the register disjoint from \(\mathsf{AZS}\) that holds the rest of the output of \(V_F\)’s final circuit.

7 describes a verifier circuit for constructing \(\rho\). There are six messages in total, because [line:4] requires four messages (including sending \(x\) to the prover) and [line:10] [line:11] each require one message.

6.2 Proof of completeness↩︎

We describe an honest prover \(P\). On [line:4] \(P\) simulates an honest prover \(P_F\) for \(V_F\). We can assume without loss of generality that if \(x\) denotes \(V_F\)’s input string, then the final state of \(P_F\)’s workspace includes a copy of \(x\) (e.g.by having \(P_F\) make an extra copy of \(x\) at the beginning of its computation). Write \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi \mspace{.5mu}}\right\rangle^{\otimes t} = \sum_{x \in \{0,1\}^{t m}} \alpha_x \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle\); then we can write the state of the system immediately after [line:4] as \[\sum_{\mathclap{x \in \{0,1\}^{t m}}} \alpha_x \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle_{\mathsf A} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}F(x) \mspace{.5mu}}\right\rangle_{\mathsf S} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}1 \mspace{.5mu}}\right\rangle_{\mathsf Z} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle_{\mathsf M} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta_x \mspace{.5mu}}\right\rangle_{\mathsf{WQ}}.\] Here \(\mathsf M\) is a register held by \(P\) (which will later be sent to the verifier in [line:11]), the register \(\mathsf Q\) denotes the remainder of \(P\)’s private workspace, and \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta_x \mspace{.5mu}}\right\rangle\) is some state.

Let \(k\) be the value chosen by the verifier in [line:8]. Given the above state, clearly applying \(Z_{\mathsf S_k}\) has the same effect that applying \(D_{\mathsf A_k}\) would have, so the state of the system after [line:10] is \[D_{\mathsf A_k} \cdot \sum_{\mathclap{x \in \{0,1\}^{t m}}} \alpha_x \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle_{\mathsf A} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}F(x) \mspace{.5mu}}\right\rangle_{\mathsf S} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle_{\mathsf M} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta_x \mspace{.5mu}}\right\rangle_{\mathsf{WQ}}\] where \(\mathsf A\) is held by the verifier and \(\mathsf{SMWQ}\) is held by \(P\).

Next \(P\) uncomputes the state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}F(x) \mspace{.5mu}}\right\rangle_{\mathsf S} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta_x \mspace{.5mu}}\right\rangle_{\mathsf{WQ}}\) controlled on \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle_{\mathsf M}\), and then sends \(\mathsf M\) to the verifier in [line:11]. After [line:14] the verifier holds the state \[D_{\mathsf A_k} \cdot \sum_{\mathclap{x \in \{0,1\}^{t m}}} \alpha_x \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle_{\mathsf A} = D_{\mathsf A_k} \cdot \bigotimes_{j \in [t]} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi \mspace{.5mu}}\right\rangle_{\mathsf A_j},\] which clearly passes the subsequent measurements with probability 1.

6.3 Proof of soundness↩︎

It will be convenient to refer to the output register in a manner independent of the random variable \(k\) from [line:8]. To this end, let \(\mathsf O\) be an \(m\)-qubit register, and imagine that the verifier’s final action is to apply the channel \(\Phi_k\) that acts as the identity on the system except that \(\Phi_k\) renames \(\mathsf A_k\) as \(\mathsf O\). Fix a prover such that the verifier accepts with probability \(\varepsilon^\prime \ge \varepsilon\). Let \(\tau\) denote the state of the system at the end of the protocol, conditioned on accepting, and let \(\tau^O\) denote the reduced state of \(\tau\) on \(\mathsf O\). Then \(\mathrm{tr}_{>n} \mathopen{}\mathclose{\left(\tau^O}\right)\) is the output state conditioned on accepting.

Let \(n^\prime\) be the number of qubits comprising \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\). By the triangle inequality, 1 2 , and various definitions from 6.1, it holds that \[\label{eq:sound1} \mathop{\mathrm{td}}\mathopen{}\mathclose{\left(\operatorname{tr}_{> n} \mathopen{}\mathclose{\left( \tau^O }\right), \rho}\right) \le \mathop{\mathrm{td}}\mathopen{}\mathclose{\left(\operatorname{tr}_{> n} \mathopen{}\mathclose{\left( \tau^O }\right), \sigma}\right) + \mathop{\mathrm{td}}(\sigma, \rho) \le \mathop{\mathrm{td}}\mathopen{}\mathclose{\left(\operatorname{tr}_{> n} \mathopen{}\mathclose{\left( \tau^O }\right), \operatorname{tr}_{> n} \mathopen{}\mathclose{\left( \psi }\right)}\right) + \delta/2\tag{5}\] and that \[\begin{align} \mathop{\mathrm{td}}\mathopen{}\mathclose{\left(\operatorname{tr}_{> n} \mathopen{}\mathclose{\left( \tau^O }\right), \operatorname{tr}_{> n} \mathopen{}\mathclose{\left( \psi }\right)}\right) &\le \mathop{\mathrm{td}}\mathopen{}\mathclose{\left(\operatorname{tr}_{> n^\prime} \mathopen{}\mathclose{\left( \tau^O }\right), \psi}\right) \nonumber \\ &\le \mathop{\mathrm{td}}\mathopen{}\mathclose{\left(\mathrm{tr}_{>n^\prime} \mathopen{}\mathclose{\left(\tau^O}\right), \mathrm{tr}_{>n^\prime} \mathopen{}\mathclose{\left(C D \phi D C^\dagger}\right)}\right) + \mathop{\mathrm{td}}\mathopen{}\mathclose{\left(\mathrm{tr}_{>n^\prime} \mathopen{}\mathclose{\left(C D \phi D C^\dagger}\right), \psi}\right)\nonumber \\ &\le \mathop{\mathrm{td}}\mathopen{}\mathclose{\left(\tau^O, C D \phi D C^\dagger}\right) + 2^{-n} \le \sqrt{\operatorname{tr} \mathopen{}\mathclose{\left( \tau \cdot (I - C D \phi D C^\dagger)_{\mathsf O} }\right)} + 2^{-n}. \label{eq:sound2} \end{align}\tag{6}\]

Let \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi \mspace{.5mu}}\right\rangle\) denote the state of the system after [line:5], and let \(U\) be the unitary jointly applied by the verifier and prover from [line:10] to [line:14]. Then \[\varepsilon^\prime \tau = \frac{1}{t} \sum_{k=1}^t \Phi_k \mathopen{}\mathclose{\left(\theta_k}\right) \qquad \text{for} \qquad \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta_k \mspace{.5mu}}\right\rangle = \bigotimes_{j \neq k} \mathopen{}\mathclose{\left\langle\mspace{.5mu}\phi \mspace{.5mu}}\right\vert_{\mathsf A_j} \cdot C_{\mathsf A_k} U Z_{\mathsf S_k} \mathopen{}\mathclose{\left\langle\mspace{.5mu}1 \mspace{.5mu}}\right\vert_{\mathsf Z} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi \mspace{.5mu}}\right\rangle,\] where \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta_k \mspace{.5mu}}\right\rangle\) is (in general) subnormalized and \(\theta_k = \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta_k \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}\theta_k \mspace{.5mu}}\right\rvert\). Let \[Q = \sum_{\mathclap{x \in \{0,1\}^{t m}}} x_{\mathsf A} \otimes F(x)_{\mathsf S},\] and similarly define a matrix \(\tilde{\tau}\) as follows: \[\varepsilon^\prime \tilde{\tau} = \frac{1}{t} \sum_{k=1}^t \Phi_k \mathopen{}\mathclose{\left(\tilde{\theta}_k}\right) \qquad \text{for} \qquad \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tilde{\theta}_k \mspace{.5mu}}\right\rangle = \bigotimes_{j \neq k} \mathopen{}\mathclose{\left\langle\mspace{.5mu}\phi \mspace{.5mu}}\right\vert_{\mathsf A_j} \cdot C_{\mathsf A_k} U Z_{\mathsf S_k} Q \mathopen{}\mathclose{\left\langle\mspace{.5mu}1 \mspace{.5mu}}\right\vert_{\mathsf Z} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi \mspace{.5mu}}\right\rangle.\]

We now argue that \(\tilde{\tau}\) is a close approximation of \(\tau\), using the soundness property of \(V_F\). For \(k \in [t]\) it holds that \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tilde{\theta}_k \mspace{.5mu}}\right\rangle - \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta_k \mspace{.5mu}}\right\rangle}\right\|^2 \le \mathopen{}\mathclose{\left\|(I-Q) \mathopen{}\mathclose{\left\langle\mspace{.5mu}1 \mspace{.5mu}}\right\vert_{\mathsf Z} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi \mspace{.5mu}}\right\rangle}\right\|^2\). This bound equals the probability that if the register \(\mathsf{ASZ}\) of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi \mspace{.5mu}}\right\rangle\) is measured in the standard basis, then the measurement outcome is of the form \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle_{\mathsf A} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}y \mspace{.5mu}}\right\rangle_{\mathsf S} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}1 \mspace{.5mu}}\right\rangle_{\mathsf Z}\) where \(y \neq F(x)\). Conditioning on \(x\) and applying the soundness of \(V_F\) shows that this event has probability at most \(2^{-2n}\), so \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tilde{\theta}_k \mspace{.5mu}}\right\rangle - \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta_k \mspace{.5mu}}\right\rangle}\right\| \le 2^{-n}\). Therefore by the triangle inequality, \[\begin{align} \varepsilon^\prime \mathopen{}\mathclose{\left\|\tilde{\tau} - \tau}\right\|_1 &\le \frac{1}{t} \sum_{k=1}^t \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tilde{\theta}_k \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}\tilde{\theta}_k \mspace{.5mu}}\right\rvert - \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta_k \mspace{.5mu}}\right\rangle\! \mathopen{}\mathclose{\left\langle \mspace{.5mu}\theta_k \mspace{.5mu}}\right\rvert}\right\|_1 \\ &\le \frac{1}{t} \sum_{k=1}^t \mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tilde{\theta}_k \mspace{.5mu}}\right\rangle - \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta_k \mspace{.5mu}}\right\rangle}\right) \mathopen{}\mathclose{\left\langle\mspace{.5mu}\tilde{\theta}_k \mspace{.5mu}}\right\vert}\right\|_1 + \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta_k \mspace{.5mu}}\right\rangle \mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\tilde{\theta}_k \mspace{.5mu}}\right\vert - \mathopen{}\mathclose{\left\langle\mspace{.5mu}\theta_k \mspace{.5mu}}\right\vert}\right)}\right\|_1}\right) \\ &\le \frac{1}{t} \sum_{k=1}^t 2^{-n} \mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tilde{\theta}_k \mspace{.5mu}}\right\rangle}\right\| + \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\theta_k \mspace{.5mu}}\right\rangle}\right\|}\right) \le 2 \cdot 2^{-n}. \end{align}\] Since \(\varepsilon^\prime \ge \varepsilon\ge 1/\mathrm{poly}(n)\) it follows that \(\mathopen{}\mathclose{\left\|\tilde{\tau} - \tau}\right\|_1 \le \exp(-\Omega(n))\).

Let \(P = (I - CD\phi D C^\dagger)_{\mathsf O}\). Since \(P\) is an orthogonal projection, \[\operatorname{tr} \mathopen{}\mathclose{\left( \tau P }\right) \le \operatorname{tr} \mathopen{}\mathclose{\left( \tilde{\tau} P }\right) + \frac{\mathopen{}\mathclose{\left\|\tilde{\tau} - \tau}\right\|_1}{2} \le \operatorname{tr} \mathopen{}\mathclose{\left( \tilde{\tau} P }\right) + \exp(-\Omega(n)). \label{eq:sound3}\tag{7}\] By reasoning similar to that in 6.2, it holds that \(U Z_{\mathsf S_k} Q = U D_{\mathsf A_k} Q = D_{\mathsf A_k} U Q\), so defining the subnormalized vector \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi^\prime \mspace{.5mu}}\right\rangle = U Q \mathopen{}\mathclose{\left\langle\mspace{.5mu}1 \mspace{.5mu}}\right\vert_{\mathsf Z} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi \mspace{.5mu}}\right\rangle\) it holds that \[\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tilde{\theta}_k \mspace{.5mu}}\right\rangle = \bigotimes_{j \neq k} \mathopen{}\mathclose{\left\langle\mspace{.5mu}\phi \mspace{.5mu}}\right\vert_{\mathsf A_j} \cdot (CD)_{\mathsf A_k} \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\varphi^\prime \mspace{.5mu}}\right\rangle.\] Therefore since trace is linear, \[\begin{align} \varepsilon^\prime \operatorname{tr} \mathopen{}\mathclose{\left( \tilde{\tau} P }\right) &= \frac{1}{t} \sum_{k=1}^t \operatorname{tr} \mathopen{}\mathclose{\left( \Phi_k \mathopen{}\mathclose{\left(\tilde{\theta}_k}\right) P }\right) = \frac{1}{t} \sum_{k=1}^t \operatorname{tr} \mathopen{}\mathclose{\left( \tilde{\theta}_k \cdot (I - CD\phi D C^\dagger)_{\mathsf A_k} }\right) \\ &= \frac{1}{t} \operatorname{tr} \mathopen{}\mathclose{\left( \varphi^\prime \cdot \sum_{k=1}^t \bigotimes_{j \neq k} \phi_{\mathsf A_j} \otimes \mathopen{}\mathclose{\left(I - \phi}\right)_{\mathsf A_k} }\right) \le \frac{1}{t} \operatorname{tr} \mathopen{}\mathclose{\left( \varphi^\prime }\right) \le \frac{1}{t}, \end{align}\] where we used that \(\sum_{k=1}^t \bigotimes_{j \neq k} \phi_{\mathsf A_j} \otimes \mathopen{}\mathclose{\left(I - \phi}\right)_{\mathsf A_k}\) is an orthogonal projection. Since \(\varepsilon^\prime \ge \varepsilon\) it follows that \[\operatorname{tr} \mathopen{}\mathclose{\left( \tilde{\tau} P }\right) \le 1/(\varepsilon t). \label{eq:sound4}\tag{8}\]

Choose \(t = \ceil*{16/\mathopen{}\mathclose{\left(\varepsilon\delta^2}\right)} \le \mathrm{poly}(n)\). Then for all sufficiently large \(n\), it follows from 5 6 7 8 that \[\mathop{\mathrm{td}}\mathopen{}\mathclose{\left(\mathrm{tr}_{>n} \mathopen{}\mathclose{\left(\tau^O}\right), \rho}\right) \le \sqrt{\frac{1}{\varepsilon t} + \exp(-\Omega(n))} + 2^{-n} + \delta/2 \le \frac{2}{\sqrt{\varepsilon t}} + \frac{\delta}{2} \le \delta.\]

7 Barrier to \(\mathsf{QAC_f^0}\) lower bounds for constructing explicit states↩︎

Call a state sequence \((\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_n \mspace{.5mu}}\right\rangle)_n\) explicit if \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_n \mspace{.5mu}}\right\rangle\) is an \(n\)-qubit state whose description can be computed in time \(\exp(\mathrm{poly}(n))\) as a function of \(n\). For example, every pure state sequence in \(\mathsf{statePSPACE_{exp}}\) is explicit up to global phases, by 16 20 and the fact that \(\mathsf{PSPACE} \subseteq \mathsf{EXP}\). We say that a language is in \(\mathsf{QAC_f^0}\) if it can be decided with bounded error by a nonuniform sequence of polynomial-size \(\mathsf{QAC_f^0}\) circuits. The following is one way to more formally state 6:

8 Approximately constructing arbitrary states↩︎

8.1 Upper bound↩︎

8.2 Lower bound↩︎

9 Proof of [lem:a5]↩︎

Recall that in 3.1 we defined \(\alpha = 0.35\) and \[\mathopen{}\mathclose{\left\lvert\mspace{.5mu}p_{\eta, C} \mspace{.5mu}}\right\rangle = C \cdot 2^{-n/2} \sum_{\mathclap{x \in \{0,1\}^{n}}} \mathop{\mathrm{sgnRe}}(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle) \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle\] for a Clifford unitary \(C\) and vector \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta \mspace{.5mu}}\right\rangle\in \mathopen{}\mathclose{\left(\mathbb{C}^2}\right)^{\otimes n}\). We establish the following fact:

Eq. (A.22) of Irani et al. INN+22?—where their \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\tau \mspace{.5mu}}\right\rangle\) equals our \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta \mspace{.5mu}}\right\rangle\), their \(\gamma\) can be set to \(0.24999\), and their \(d\) equals \(2^n\)—implies that \[\mathrm{Pr}\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\|\mathrm{Re} \mathopen{}\mathclose{\left(C \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta \mspace{.5mu}}\right\rangle}\right)}\right\|_1 \ge \sqrt{0.24999 \cdot 2^n}}\right) > 0\] for a random Clifford unitary \(C\). Therefore there exists a fixed Clifford unitary \(C\) such that \(2^{-n/2} \mathopen{}\mathclose{\left\|\mathrm{Re} \mathopen{}\mathclose{\left(C^\dagger \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta \mspace{.5mu}}\right\rangle}\right)}\right\|_1 \ge 0.4999\). Finally it follows from the definition of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}p_{\eta, C} \mspace{.5mu}}\right\rangle\) that \[\mathrm{Re}(\mathopen{}\mathclose{\left\langle \eta \middle| p_{\eta, C} }\right\rangle) = 2^{-n/2} \sum_x \mathopen{}\mathclose{\left| \mathrm{Re}(\mathopen{}\mathclose{\left\langle\mspace{.5mu}\eta \mspace{.5mu}}\right\vertC \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle) }\right| = 2^{-n/2} \mathopen{}\mathclose{\left\|\mathrm{Re}(C^\dagger \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\eta \mspace{.5mu}}\right\rangle)}\right\|_1,\] implying that [lem:a5] holds with \(\alpha = 0.4999\).

We instead define \(\alpha = 0.35\) because we believe that there is a typo in Irani et al. INN+22?, and that the right side of their Eq. (A.22) should be \(1/2 - 4\gamma\) instead of \(1/2 - 2\gamma\). So in the above analysis we should actually set \(\gamma\) to be slightly less than \(1/8\), and so the value of \(\alpha\) should be slightly less than \(\sqrt{1/8} \approx 0.354\). The exact value of \(\alpha\) is not important for our main results however.

Our disagreement with the argument in Irani et al. INN+22? is as follows. We will use their notation; in particular they assign a different meaning to the variable \(\alpha\) than we have done. First—and this part is actually an understatement by Irani et al., not an error—in Eq. (A.13) the expression \(\sqrt{\mathopen{}\mathclose{\left(2^n+1}\right) / \mathopen{}\mathclose{\left(2\alpha}\right)}\) can trivially be replaced by \(\sqrt{\mathopen{}\mathclose{\left(2^n+1}\right) / (4 \alpha)}\), and so Eq. (A.15) can be replaced by “\(\ge 1 - 1/(2\alpha)\)". Applying this strengthening of Eq. (A.15) with \(\alpha = 1/(16\gamma)\) implies that \(\mathrm{Pr}\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle}\right\|_1 \ge 2\sqrt{\gamma 2^n}}\right) \ge 1 - 8\gamma\), where \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) is as defined in Lemma A.5 of Irani et al.

Write \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle= \mathopen{}\mathclose{\left\lvert\mspace{.5mu}a \mspace{.5mu}}\right\rangle + i \mathopen{}\mathclose{\left\lvert\mspace{.5mu}b \mspace{.5mu}}\right\rangle\) where \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}a \mspace{.5mu}}\right\rangle, \mathopen{}\mathclose{\left\lvert\mspace{.5mu}b \mspace{.5mu}}\right\rangle \in \mathbb{R}^{2^n}\). Then \[\mathrm{Pr}\mathopen{}\mathclose{\left(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}a \mspace{.5mu}}\right\rangle\|_1 \ge \sqrt{\gamma 2^n}}\right) \ge \mathrm{Pr}\mathopen{}\mathclose{\left(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}a \mspace{.5mu}}\right\rangle\|_1 \ge \sqrt{\gamma 2^n} \, \middle| \, \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle}\right\|_1 \ge 2\sqrt{\gamma 2^n}}\right) \mathrm{Pr}\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle}\right\|_1 \ge 2\sqrt{\gamma 2^n}}\right).\] By the triangle inequality \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle}\right\|_1 \le \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}a \mspace{.5mu}}\right\rangle}\right\|_1 + \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}b \mspace{.5mu}}\right\rangle}\right\|_1\), so conditioned on \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle}\right\|_1 \ge 2\sqrt{\gamma 2^n}\) either \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}a \mspace{.5mu}}\right\rangle}\right\|_1 \ge \sqrt{\gamma 2^n}\) or \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}b \mspace{.5mu}}\right\rangle}\right\|_1 \ge \sqrt{\gamma 2^n}\) (or both). Furthermore \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}a \mspace{.5mu}}\right\rangle}\right\|_1\) and \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}b \mspace{.5mu}}\right\rangle}\right\|_1\) are identically distributed conditioned on any value of \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle}\right\|_1\), because applying a global phase of \(i\) to \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) has the effect of swapping \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}a \mspace{.5mu}}\right\rangle}\right\|_1\) and \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}b \mspace{.5mu}}\right\rangle}\right\|_1\) without changing \(\mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle}\right\|_1\). Therefore \[\mathrm{Pr}\mathopen{}\mathclose{\left(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}a \mspace{.5mu}}\right\rangle\|_1 \ge \sqrt{\gamma 2^n} \, \middle| \, \mathopen{}\mathclose{\left\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle}\right\|_1 \ge 2\sqrt{\gamma 2^n}}\right) \ge 1/2\] and so \(\mathrm{Pr}\mathopen{}\mathclose{\left(\|\mathopen{}\mathclose{\left\lvert\mspace{.5mu}a \mspace{.5mu}}\right\rangle\|_1 \ge \sqrt{\gamma 2^n}}\right) \ge \frac{1}{2}\mathopen{}\mathclose{\left(1 - 8\gamma}\right) = 1/2 - 4\gamma\).

10 State synthesis using perfect linear hash functions↩︎

Below we argue that in the proof of (a statement similar to) 11, instead of using states of the form \(C \cdot 2^{-n/2} \sum_{x \in \{0,1\}^{n}} \pm \mathopen{}\mathclose{\left\lvert\mspace{.5mu}x \mspace{.5mu}}\right\rangle\) where \(C\) is a Clifford unitary, we could alternatively use what we call “hash states":

A hash state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi \mspace{.5mu}}\right\rangle\) can be constructed with one query as follows. First prepare \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}+^k \mspace{.5mu}}\right\rangle\) in a register \(\mathsf R\). Then controlled on the state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}y \mspace{.5mu}}\right\rangle_{\mathsf R}\) where \(y \in \{0,1\}^{k}\), query the unique string \(x \in S\) such that \(Ax = y\), while simultaneously making a query to apply a phase of \(\sigma_x\). Finally use \(A\) to uncompute \(y\) controlled on \(x\), using that parity is in \(\mathsf{QAC_f^0}\) Gre+02?.

More generally, for \(0 \le j < T\) let \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_j \mspace{.5mu}}\right\rangle\) be a hash state and let \(A_j \in \mathbb{F}_2^{k_j \times n}\) be the linear transformation associated with \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_j \mspace{.5mu}}\right\rangle\). To construct \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi_j \mspace{.5mu}}\right\rangle\) controlled on \(j\), first construct \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}+^n \mspace{.5mu}}\right\rangle_{\mathsf R}\), and then proceed as above controlled on \(j\). Here the oracle ignores the last \(n - k_j\) qubits of \(\mathsf R\), and also outputs descriptions of \(A_0, \dotsc,A_{T-1}\). Finally uncompute \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}+^{n-k_j} \mspace{.5mu}}\right\rangle\) in the last \(n-k_j\) qubits of \(\mathsf R\), controlled on \(k_j\) (which is implicit in the description of \(A_j\)).

All that remains is to write an arbitrary \(n\)-qubit state \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\) as a linear combination of hash states, in a manner suitable to an LCU application like that in 4.1. (It will be apparent from our proof that the queries can be computed in \(\mathrm{poly}(n)\) space given the description of \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle\), by reasoning similar to that in 3.3.) By writing \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}\right\rangle= \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_R \mspace{.5mu}}\right\rangle + i \mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_I \mspace{.5mu}}\right\rangle\) where \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_R \mspace{.5mu}}\right\rangle\) and \(\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi_I \mspace{.5mu}}\right\rangle\) are real-valued vectors, it suffices to write a real-valued vector with norm at most 1 as such a linear combination of hash states. To do this we will need the following lemma, which is proved using the probabilistic method:

We remark that Alon, Dietzfelbinger, Miltersen, Petrank and Tardos ADM+99? also investigated the properties of random linear hash functions from \(S \subseteq \mathbb{F}_2^n\) to \(\mathbb{F}_2^k\). However, they did not bound the number of nonempty buckets when \(|S| = 2^k\).

Using 27 we prove the following:

---

1. Email: grosenth@uwaterloo.ca. Part of this work was done while the author was visiting the Simons Institute for the Theory of Computing.↩︎

2. We credit Fermi Ma Ma23? for suggesting a simplification of the proof which he has allowed us to incorporate, as discussed in 3.↩︎

3. A tighter analysis can be obtained using Harrow, Recht and Chuang’s HRC02? version of the Solovay–Kitaev theorem, which says that for certain finite gate sets, any unitary on a fixed number of qubits can be approximated to within error \(\varepsilon\) in the operator 2-norm by \(O(\log(1/\varepsilon))\) (rather than \(\mathrm{poly}\log(1/\varepsilon)\)) gates.↩︎

4. Specifically, the case where their \(J\) equals our \(\mathopen{}\mathclose{\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\psi \mspace{.5mu}}}\right\rangle\), their \(A\) equals our \(\mathopen{}\mathclose{\mathopen{}\mathclose{\left\lvert\mspace{.5mu}0 \mspace{.5mu}}}\right\rangle\! \mathopen{}\mathclose{\mathopen{}\mathclose{\left\langle \mspace{.5mu}0 \mspace{.5mu}}}\right\rvert \otimes I_n + \mathopen{}\mathclose{\mathopen{}\mathclose{\left\lvert\mspace{.5mu}1 \mspace{.5mu}}}\right\rangle\! \mathopen{}\mathclose{\mathopen{}\mathclose{\left\langle \mspace{.5mu}1 \mspace{.5mu}}}\right\rvert \otimes \mathopen{}\mathclose{\mathopen{}\mathclose{\left\lvert\mspace{.5mu}\phi \mspace{.5mu}}}\right\rangle\! \mathopen{}\mathclose{\mathopen{}\mathclose{\left\langle \mspace{.5mu}0^n \mspace{.5mu}}}\right\rvert\), their \(U\) equals our \(\text{\textrm{ctrl-}}U\), their \(B\) equals our \(\mathopen{}\mathclose{\mathopen{}\mathclose{\left\lvert\mspace{.5mu}0 \mspace{.5mu}}}\right\rangle\! \mathopen{}\mathclose{\mathopen{}\mathclose{\left\langle \mspace{.5mu}0 \mspace{.5mu}}}\right\rvert \otimes I_n + \mathopen{}\mathclose{\mathopen{}\mathclose{\left\lvert\mspace{.5mu}1 \mspace{.5mu}}}\right\rangle\! \mathopen{}\mathclose{\mathopen{}\mathclose{\left\langle \mspace{.5mu}1 \mspace{.5mu}}}\right\rvert \otimes V \mathopen{}\mathclose{\mathopen{}\mathclose{\left\lvert\mspace{.5mu}0^n \mspace{.5mu}}}\right\rangle\! \mathopen{}\mathclose{\mathopen{}\mathclose{\left\langle \mspace{.5mu}0^n \mspace{.5mu}}}\right\rvert\), and their \(V\) equals our \(\text{\textrm{ctrl-}}V\).↩︎

5. Inspection of the proof of 11 reveals that the last query (i.e.uncomputing \(z\)) can be computed in \(\mathrm{poly}(n)\) space, as required by the theorem. The idea to use \(G\) to artificially decrease the initial “success" amplitude was suggested to us by Wiebe Wie21a?.↩︎

6. Although not directly implied by 9, inspection of the proof of 9 reveals that if \((B_n)_n\) is a uniform sequence of polynomial-size \(\mathsf{QAC_f^0}\) circuits then \((\text{\textrm{ctrl-}}B_n)_n\) can be implemented by a uniform sequence of polynomial-size \(\mathsf{QAC_f^0}\) circuits.↩︎

7. As of this writing the \(\varepsilon\) term is omitted from MY23?, but inspection of their proof reveals that this omission is an error.↩︎

8. The reader may wonder whether the definition of \(\mathsf{QIP}(3)\) here is sensitive to the assumption of perfect completeness; it is known that if the verifier uses the universal gate set \(\{H, \mathit{CNOT}, T\}\), then we can assume perfect completeness without loss of generality vidick2016quantum?.↩︎

9. One way to see this is as follows. Let \(x,y \in \mathbb{F}_2^n\) be nonzero vectors, and let \(B \in \mathbb{F}_2^{n \times n}\) be an invertible matrix such that \(Bx = y\). Then \(AB\) is distributed identically to \(A\), so \(\mathrm{Pr}(Ax = 0) = \mathrm{Pr}(ABx = 0) = \mathrm{Pr}(Ay = 0)\).↩︎

10. Define \(\binom r 2 = r(r-1)/2\) even for non-integer values of \(r\).↩︎