We establish connections between state tomography, pseudorandomness, quantum state synthesis, and circuit lower bounds. In particular, let $\mathfrak C $ be a family of non-uniform quantum circuits of polynomial size and suppose that there exists an algorithm that, given copies of $\ket \psi$, distinguishes whether $\ket \psi$ is produced by $\mathfrak C$ or is Haar random, promised one of these is the case. For arbitrary fixed constant $c$, we show that if the algorithm uses at most $O\!\left(2^{n^c}\right)$ time and $2^{n^{0.99}}$ samples then $\mathsf{stateBQE} \not\subset \mathsf{state}\mathfrak{C}$. Here $\mathsf{stateBQE} \coloneqq \mathsf{stateBQTIME}\left[2^{O(n)}\right]$ and $\mathsf{state}\mathfrak{C}$ are state synthesis complexity classes as introduced by Rosenthal and Yuen (2022), which capture problems with classical inputs but quantum output. Note that efficient tomography implies a similarly efficient distinguishing algorithm against Haar random states, even for nearly exponential-time algorithms. Because every state produced by a polynomial-size circuit can be learned with $2^{O(n)}$ samples and time, or $\omega(\mathrm{poly}(n))$ samples and $2^{\omega(\mathrm{poly}(n))}$ time, we show that even slightly non-trivial quantum state tomography algorithms would lead to new statements about quantum state synthesis. Finally, a slight modification of our proof shows that distinguishing algorithms for quantum states can imply circuit lower bounds for decision problems as well. We then take these results and port them over to the setting of unitary learning and unitary synthesis. All combined, this helps shed light on why time-efficient tomography algorithms for non-uniform quantum circuit classes has only had limited and partial progress. Our work extends the results of Arunachalam et. al. (2022), which revealed a connection between quantum learning of \emph{Boolean functions} and circuit lower bounds for \emph{classical} circuit classes, to the setting of state (resp. unitary) tomography and state (resp. unitary) synthesis. As a result, we establish a conditional pseudorandom state (resp. unitary) generator, a circuit size hierarchy theorems for non-uniform state (resp. unitary) synthesis, and connections between state (resp. unitary) synthesis class separations and decision class separations, which may be of independent interest.

Bill Cai, Ng Clarence, Daniel Liang, Shelvia Hotama. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2024.

We study the complexity of learning quantum states in various models with respect to the stabilizer formalism and obtain the following results: We prove that Ω(n) T-gates are necessary for any Clifford+T circuit to prepare computationally pseudorandom quantum states, an exponential improvement over the previously known bound. This bound is asymptotically tight if linear-time quantum-secure pseudorandom functions exist. Given an n-qubit pure quantum state |ψ⟩ that has fidelity at least τ with some stabilizer state, we give an algorithm that outputs a succinct description of a stabilizer state that witnesses fidelity at least τ − ε. The algorithm uses O(n/(ε2τ4)) samples and exp(O(n/τ4)) / ε2 time. In the regime of τ constant, this algorithm estimates stabilizer fidelity substantially faster than the naive exp(O(n2))-time brute-force algorithm over all stabilizer states. In the special case of τ > cos2(π/8), we show that a modification of the above algorithm runs in polynomial time. We exhibit a tolerant property testing algorithm for stabilizer states. The underlying algorithmic primitive in all of our results is Bell difference sampling. To prove our results, we establish and/or strengthen connections between Bell difference sampling, symplectic Fourier analysis, and graph theory.

We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. Specifically, given an n-qubit pure state |ψ⟩, we give an efficient algorithm that distinguishes whether |ψ⟩ is (i) Haar-random or (ii) a state with stabilizer fidelity at least 1/k (i.e., has fidelity at least 1/k with some stabilizer state), promised that one of these is the case. With black-box access to |ψ⟩, our algorithm uses O(k^{12} log(1/δ)) copies of |ψ⟩ and O(n k^{12} log(1/δ)) time to succeed with probability at least 1-δ, and, with access to a state preparation unitary for |ψ⟩ (and its inverse), O(k³ log(1/δ)) queries and O(n k³ log(1/δ)) time suffice. As a corollary, we prove that ω(log(n)) T-gates are necessary for any Clifford+T circuit to prepare computationally pseudorandom quantum states, a first-of-its-kind lower bound.