We present a polynomial-time quantum algorithm making a single query (in superposition) to a classical oracle, such that for every state |ψ〉 there exists a choice of oracle that makes the algorithm construct an exponentially close approximation of |ψ〉. Previous algorithms for this problem either used a linear number of queries and polynomial time, or a constant number of queries and polynomially many ancillae but no nontrivial bound on the runtime. As corollaries we do the following:

Whereas quantum complexity theory has traditionally been concerned with problems arising from classical complexity theory (such as computing boolean functions), it also makes sense to study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations. With this motivation, we define models of interactive proofs for synthesizing quantum states and unitaries, where a polynomial-time quantum verifier interacts with an untrusted quantum prover, and a verifier who accepts also outputs an approximation of the target state (for the state synthesis problem) or the result of the target unitary applied to the input state (for the unitary synthesis problem); furthermore there should exist an "honest" prover which the verifier accepts with probability 1. Our main result is a "state synthesis" analogue of the inclusion $\mathsf{PSPACE} \subseteq \mathsf{IP}$: any sequence of states computable by a polynomial-space quantum algorithm (which may run for exponential time) admits an interactive protocol of the form described above. Leveraging this state synthesis protocol, we also give a unitary synthesis protocol for polynomial space-computable unitaries that act nontrivially on only a polynomial-dimensional subspace. We obtain analogous results in the setting with multiple entangled provers as well.

QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. QAC$^0$ circuits are QAC circuits of constant depth, and are quantum analogues of AC$^0$ circuits. We prove the following: $\bullet$ For all $d \ge 7$ and $\varepsilon>0$ there is a depth-$d$ QAC circuit of size $\exp(\mathrm{poly}(n^{1/d}) \log(n/\varepsilon))$ that approximates the $n$-qubit parity function to within error $\varepsilon$ on worst-case quantum inputs. Previously it was unknown whether QAC circuits of sublogarithmic depth could approximate parity regardless of size. $\bullet$ We introduce a class of "mostly classical" QAC circuits, including a major component of our circuit from the above upper bound, and prove a tight lower bound on the size of low-depth, mostly classical QAC circuits that approximate this component. $\bullet$ Arbitrary depth-$d$ QAC circuits require at least $Ω(n/d)$ multi-qubit gates to achieve a $1/2 + \exp(-o(n/d))$ approximation of parity. When $d = Θ(\log n)$ this nearly matches an easy $O(n)$ size upper bound for computing parity exactly. $\bullet$ QAC circuits with at most two layers of multi-qubit gates cannot achieve a $1/2 + \exp(-o(n))$ approximation of parity, even non-cleanly. Previously it was known only that such circuits could not cleanly compute parity exactly for sufficiently large $n$. The proofs use a new normal form for quantum circuits which may be of independent interest, and are based on reductions to the problem of constructing certain generalizations of the cat state which we name "nekomata" after an analogous cat yōkai.

For any fixed graph $G$, the subgraph isomorphism problem asks whether an $n$-vertex input graph has a subgraph isomorphic to $G$. A well-known algorithm of Alon, Yuster and Zwick (1995) efficiently reduces this to the "colored" version of the problem, denoted $G$-$\mathsf{SUB}$, and then solves $G$-$\mathsf{SUB}$ in time $O(n^{tw(G)+1})$ where $tw(G)$ is the treewidth of $G$. Marx (2010) conjectured that $G$-$\mathsf{SUB}$ requires time $Ω(n^{\mathrm{const}\cdot tw(G)})$ and, assuming the Exponential Time Hypothesis, proved a lower bound of $Ω(n^{\mathrm{const}\cdot emb(G)})$ for a certain graph parameter $emb(G) \ge Ω(tw(G)/\log tw(G))$. With respect to the size of $\mathrm{AC}^0$ circuits solving $G$-$\mathsf{SUB}$ in the average case, Li, Razborov and Rossman (2017) proved (unconditional) upper and lower bounds of $O(n^{2κ(G)+\mathrm{const}})$ and $Ω(n^{κ(G)})$ for a different graph parameter $κ(G) \ge Ω(tw(G)/\log tw(G))$. Our contributions are as follows. First, we prove that $emb(G)$ is $O(κ(G))$ for all graphs $G$. Next, we show that $κ(G)$ can be asymptotically less than $tw(G)$; for example, if $G$ is a hypercube then $κ(G)$ is $Θ\big(tw(G)\big/\sqrt{\log tw(G)}\big)$. This implies that the average-case complexity of $G$-$\mathsf{SUB}$ is $n^{o(tw(G))}$ when $G$ is a hypercube. Finally, we construct $\mathrm{AC}^0$ circuits of size $O(n^{κ(G)+\mathrm{const}})$ that solve $G$-$\mathsf{SUB}$ in the average case, closing the gap between the upper and lower bounds of Li et al.