2^{\lfloor\log_{2}r\rfloor^{2}}<2^{n^{2\lambda}}=s=s\circ\ell^{-1}(\ell)$
$\displaystyle\varepsilon(\ell)=\varepsilon\left(\lfloor\log_{2}r\rfloor^{2/c}\right)$
$\displaystyle\geq\frac{63\cdot
4^{\lfloor\log_{2}r\rfloor^{1.98/c}}}{2^{\lfloor\log_{2}r\rfloor^{2/c}}}+\frac{1}{2^{n^{\lambda}}}+\sqrt{m}\cdot\delta>\frac{63\cdot
4^{\lfloor\log_{2}r\rfloor^{1.98/c}}}{2^{\lfloor\log_{2}r\rfloor^{2/c}}}+\frac{1}{2^{n^{\lambda}}}+\sqrt{m}\cdot\delta$
$\displaystyle>\frac{4\cdot
4^{n^{1.98\cdot\lambda/c}}}{2^{\lfloor\log_{2}r\rfloor^{2/c}}}+\frac{1}{2^{n^{\lambda}}}+\sqrt{m}\cdot\delta\geq\frac{4q^{2}}{2^{\lfloor\log_{2}r\rfloor^{2/c}}}+\frac{1}{r}+\sqrt{m}\cdot\delta$

Consequently, because $\mathcal{C}$ is
$\left(m,t,\varepsilon\right)$-distinguishable, then by Lemma 6.2 we find that

$\mathsf{pureStateBQTIME}\left[t\circ\kappa^{-1}\right]_{\exp}\not\subset\mathsf{pureState}\mathfrak{C}\left[\mathrm{poly}(\ell\circ\kappa^{-1})\right]_{\delta}=\mathsf{pureState}\mathfrak{C}[\mathrm{poly}(n)]_{\delta}.\qed$

While the choice of parameters may seem somewhat opaque, the most important
thing is to consider the relationship between $m$ and $\delta$ and how it
affects $\varepsilon$. For example, when $m=\mathrm{poly}(n)$ then there
exists some inverse-poly distinguishing that gives a separation with
$\mathsf{pureState}\mathfrak{C}$. Similarly, when $m$ is just less than
$2^{\ell^{0.99}}$ then inverse-sub-exponential distinguishing gives a
separation from $\mathsf{pureState}\mathfrak{C}_{\exp}$. We formally prove the
latter statement.

######  Corollary 6.4 (Formal statement of Theorem 1.2).

Let $\mathfrak{C}$ be a circuit class that is closed under restrictions.
Define $\mathcal{C}_{\ell}$ to be the set of pure states on $\ell$ qubits that
can be exactly constructed by $\mathfrak{C}[\mathrm{poly}(\ell)]$. If there
exists some constant $c\geq 2$ such that
$\mathcal{C}\coloneqq\bigcup_{\ell\geq 1}\mathcal{C}_{\ell}$ is
$\left(m,t,\varepsilon\right)$-distinguishable for $m\leq 2^{\ell^{0.99}}$,
$t\leq O\\!\left(2^{\ell^{c}}\right)$, and
$\varepsilon\geq\frac{1}{2^{\ell^{0.99}}}$, then at least one of the following
must be true:

  * •

for all $k\geq 1$,
$\mathsf{pureStateBQSUBEXP}_{\exp}\not\subset\mathsf{pureStateBQSIZE}\left[n^{k}\right]_{0.49}$,

  * •

$\mathsf{pureStateBQE}_{\exp}\not\subset\mathsf{pureState}\mathfrak{C}_{\exp}$.

###### Proof.

For arbitrary polynomial $p$,

$\varepsilon\geq\frac{1}{2^{\ell^{0.99}}}\geq\frac{63\cdot
4^{\ell^{0.99}}}{2^{\ell}}+\frac{1}{2^{\ell^{c/2}}}+\sqrt{2^{\ell^{0.99}}}\cdot\exp(-p)\geq\frac{63\cdot
4^{\ell^{0.99}}}{2^{\ell}}+\frac{1}{2^{n^{\lambda}}}+\sqrt{m}\cdot\exp(-p)$

with sufficiently large $\ell$. By Theorem 6.3, either (1) for all $k\geq 1$,
$\mathsf{pureStateBQSUBEXP}_{\exp}\not\subset\mathsf{pureStateBQSIZE}\left[n^{k}\right]_{0.49}$
or (2)
$\mathsf{pureStateBQE}\not\subset\mathsf{pureState}\mathfrak{C}_{\exp(-p)}$.
In case (2), since $p$ is an arbitrary polynomial, the state is not in
$\mathsf{pureState}\mathfrak{C}_{\exp}$ as well. ∎

Using our connection between learning and distinguishing (see Lemma 4.5) we
can now state our main result. Note that instead of listing two possible
outcomes like in Corollary 6.4, we take the intersection of the outcomes such
that it is true regardless of which outcome. However, while the implied result
would still be interesting for many circuit classes, it is decidedly weaker
than either of the two original possibilities.

######  Corollary 6.5 (Formal statement of Theorem 1.1).

Let $\mathfrak{C}$ be a circuit class that
$\mathsf{pureState}\mathfrak{C}_{\exp}\subset\mathsf{pureStateBQP/poly}_{0.49}$.
Define $\mathcal{C}_{\ell}$ to be the set of pure states on $\ell$ qubits that
can be exactly constructed by $\mathfrak{C}[\mathrm{poly}(\ell)]$. If there
exists some constant $c\geq 2$ such that
$\mathcal{C}\coloneqq\bigcup_{\ell\geq 1}\mathcal{C}_{\ell}$ is
$\left(m,t,1-\eta,1-\gamma\right)$-learnable for $m-1\leq 2^{\ell^{0.99}}$,
$t\leq O\\!\left(\frac{2^{\ell^{c}}}{\ell^{c}}\right)$ and
$\eta\cdot\gamma=\frac{4}{2^{\ell^{0.99}}}$, then for every $k\geq 1$,
$\mathsf{pureStateBQE}_{\exp}\not\subset\mathsf{pureState}\mathfrak{C}[n^{k}]_{\exp}$.

###### Proof.

Lemma 4.5 tells us that each $\mathcal{C}^{k}$ is
$\left(m,t^{\prime},\varepsilon\right)$-distinguishable for $t^{\prime}=t\log
t\leq O\\!\left(2^{\ell^{2}}\right)$ and
$\varepsilon=\frac{1-o(1)}{2}\eta\cdot\gamma\geq\frac{1}{2^{\ell^{0.99}}}$ for
sufficiently large $\ell$. We then appeal to Corollary 6.4. By invoking the
condition that
$\mathsf{pureState}\mathfrak{C}_{\exp}\subset\mathsf{pureStateBQP/poly}_{0.49}$,
in both cases the following statement is true: for every $k\geq 1$,
$\mathsf{pureStateBQE}_{\exp}\not\subset\mathsf{pureState}\mathfrak{C}[n^{k}]_{\exp}$.
∎

######  Remark 6.6.

It is actually possible to have a more fine-grained approach to the
learning/distinguishing algorithm than in Theorems 6.3 and 6.4. For instance,
if the learning algorithm only holds up to $\mathfrak{C}[n^{k}]$ for some
fixed $k$, then by a more careful application of Lemma 6.2, the separation in
the second case would be

$\mathsf{pureStateBQE}_{\exp}\not\subset\mathsf{pureState}\mathfrak{C}\left[n^{\alpha\cdot
k/\lambda}\right]_{\delta}$

instead. As a result, Corollary 6.5 remains true if there is a learning
algorithm for each $\mathcal{C}^{k}\coloneqq\bigcup_{\ell\geq
1}\mathcal{C}^{k}_{\ell}$ where $\mathcal{C}^{k}_{\ell}$ refers to
$\ell$-qubit states produced by $\mathfrak{C}[n^{k}]$. That is, the learning
algorithm can work up to any polynomial size, but needs to know an upper bound
on the polynomial in advance.

## Acknowledgements

We would like to thank William Kretschmer, Sabee Grewal, Vishnu Iyer, Shih-Han
Hung, Srinivasan Arunachalam, Henry Yuen, Scott Aaronson, Kai-Min Chung, and
Ruizhe Zhang for a variety of extremely useful discussions and feedback. DL
would also like to thank Igor Oliviera for helping fix bugs in the statement
of the PRG in Lemma 3.10, Nick Hunter-Jones for helping with all of Section
5.1, and Gregory Rosenthal for helping with the name of
$\mathsf{statePSPACESIZE}$ and aiding in the understanding of the results in
[Ros24]. Part of this research was performed while DL was visiting the
Institute for Pure and Applied Mathematics (IPAM), which is supported by the
National Science Foundation (Grant No. DMS-1925919). DL is supported by the US
NSF award FET-2243659. FS is supported in part by the US NSF grants
CCF-2054758 (CAREER) and CCF-2224131. NHC is supported by NSF Awards
FET-2243659 and FET-2339116 (CAREER), Google Scholar Award, and DOE Quantum
Testbed Finder Award DE-SC0024301.

## References

  * [AAK+07] Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie.  Testing k-wise and almost k-wise independence.  In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 496–505, New York, NY, USA, 2007. Association for Computing Machinery.  doi:10.1145/1250790.1250863.
  * [Aar22] Scott Aaronson.  Introduction to Quantum Information Science Lecture Notes, May 2022.  URL: https://www.scottaaronson.com/qclec.pdf.
  * [ABDY22] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder.  Optimal algorithms for learning quantum phase states, 2022.  arXiv:2208.07851.
  * [ABF+22] Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou.  Quantum Pseudoentanglement, 2022.  arXiv:2211.00747.
  * [AG04] Scott Aaronson and Daniel Gottesman.  Improved Simulation of Stabilizer Circuits.  Physical Review A, 70(5), 2004.  doi:10.1103/physreva.70.052328.
  * [AG08] Scott Aaronson and Daniel Gottesman.  Identifying Stabilizer States, 2008.  https://pirsa.org/08080052.
  * [AG23] Scott Aaronson and Sabee Grewal.  Efficient Tomography of Non-Interacting Fermion States, 2023.  arXiv:2102.10458.
  * [AGG+22] Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, and Aarthi Sundaram.  Quantum learning algorithms imply circuit lower bounds.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 562–573, 2022.  doi:10.1109/FOCS52979.2021.00062.
  * [AGS21] Srinivasan Arunachalam, Alex Bredariol Grilo, and Aarthi Sundaram.  Quantum Hardness of Learning Shallow Classical Circuits.  SIAM Journal on Computing, 50(3):972–1013, 2021.  doi:10.1137/20M1344202.
  * [BBD+97] Adriano Barenco, André Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, and Chiara Macchiavello.  Stabilization of Quantum Computations by Symmetrization.  SIAM Journal on Computing, 26(5):1541–1557, 1997.  doi:10.1137/S0097539796302452.
  * [BCG13] K. Banaszek, M. Cramer, and D. Gross.  Focus on quantum tomography.  New Journal of Physics, 15(12):125020, 2013.  doi:10.1088/1367-2630/15/12/125020.
  * [BCWdW01] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf.  Quantum Fingerprinting.  Phys. Rev. Lett., 87:167902, Sep 2001.  doi:10.1103/PhysRevLett.87.167902.
  * [BEM+23] John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen.  Unitary Complexity and the Uhlmann Transformation Problem, 2023.  arXiv:2306.13073.
  * [BLM+23] Harry Buhrman, Noah Linden, Laura Mančinska, Ashley Montanaro, and Maris Ozols.  Quantum Majority Vote.  In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:1, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.29, doi:10.4230/LIPIcs.ITCS.2023.29.
  * [BM99] Dagmar Bruß and Chiara Macchiavello.  Optimal state estimation for d-dimensional quantum systems.  Physics Letters A, 253(5):249–251, 1999.  doi:10.1016/S0375-9601(99)00099-7.
  * [BO21] Costin Bădescu and Ryan O’Donnell.  Improved Quantum Data Analysis.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1398–1411. Association for Computing Machinery, 2021.  doi:10.1145/3406325.3451109.
  * [BOFKT88] Michael Ben-Or, Ephraim Feig, Dexter Kozen, and Prasoon Tiwari.  A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots.  SIAM Journal on Computing, 17(6):1081–1092, 1988.  doi:10.1137/0217069.
  * [Bor77] Allan Borodin.  On Relating Time and Space to Size and Depth.  SIAM Journal on Computing, 6(4):733–744, 1977.  doi:10.1137/0206054.
  * [BPR12] Abhishek Banerjee, Chris Peikert, and Alon Rosen.  Pseudorandom functions and lattices.  In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, pages 719–737, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
  * [BS19] Zvika Brakerski and Omri Shmueli.  (Pseudo) Random Quantum States with Binary Phase.  In Theory of Cryptography, 2019.  doi:10.1007/978-3-030-36030-6_10.
  * [BV97] Ethan Bernstein and Umesh Vazirani.  Quantum Complexity Theory.  SIAM Journal on Computing, 26(5):1411–1473, 1997.  doi:10.1137/S0097539796300921.
  * [CBB+24] Chi-Fang Chen, Adam Bouland, Fernando G. S. L. Brandão, Jordan Docter, Patrick Hayden, and Michelle Xu.  Efficient unitary designs and pseudorandom unitaries from permutations, 2024.  arXiv:2404.16751.
  * [CCZZ22] Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, and Ruizhe Zhang.  Quantum Meets the Minimum Circuit Size Problem.  In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1–47:16, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.ITCS.2022.47.
  * [CHL+23] S. Chen, B. Huang, J. Li, A. Liu, and M. Sellke.  When does adaptivity help for quantum state learning?  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 391–404, Los Alamitos, CA, USA, nov 2023. IEEE Computer Society.  doi:10.1109/FOCS57990.2023.00029.
  * [CLL23] Nai-Hui Chia, Ching-Yi Lai, and Han-Hsuan Lin.  Efficient learning of $t$-doped stabilizer states with single-copy measurements, 2023.  arXiv:2308.07014.
  * [Csa75] L. Csanky.  Fast parallel matrix inversion algorithms.  In 16th Annual Symposium on Foundations of Computer Science (sfcs 1975), pages 11–12, 1975.  doi:10.1109/SFCS.1975.14.
  * [DCEL09] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine.  Exact and approximate unitary 2-designs and their application to fidelity estimation.  Phys. Rev. A, 80:012304, Jul 2009.  doi:10.1103/PhysRevA.80.012304.
  * [DN05] Christopher M. Dawson and Michael A. Nielsen.  The solovay-kitaev algorithm, 2005.  arXiv:quant-ph/0505030.
  * [Fan57] Ugo Fano.  Description of States in Quantum Mechanics by Density Matrix and Operator Techniques.  Reviews of Modern Physics, 29(1):74, 1957.  doi:10.1103/RevModPhys.29.74.
  * [FBaK21] Daniel Stilck França, Fernando G.S L. Brandão, and Richard Kueng.  Fast and Robust Quantum State Tomography from Few Basis Measurements.  In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1–7:13, 2021.  doi:10.4230/LIPIcs.TQC.2021.7.
  * [FK09] Lance Fortnow and Adam R. Klivans.  Efficient learning algorithms yield circuit lower bounds.  Journal of Computer and System Sciences, 75(1):27–36, 2009.  Learning Theory 2006.  doi:10.1016/j.jcss.2008.07.006.
  * [FvdG99] C.A. Fuchs and J. van de Graaf.  Cryptographic distinguishability measures for quantum-mechanical states.  IEEE Transactions on Information Theory, 45(4):1216–1227, 1999.  doi:10.1109/18.761271.
  * [GBFH09] Frederic Green, Debajyoti Bera, Stephen Fenner, and Steve Homer.  Efficient Universal Quantum Circuits.  Quantum Information and Computation, 10, 07 2009.  doi:10.1007/978-3-642-02882-3_42.
  * [GC01] Daniel Gottesman and Isaac Chuang.  Quantum Digital Signatures, 2001.  arXiv:quant-ph/0105032.
  * [GGM84] O. Goldreich, S. Goldwasser, and S. Micali.  How To Construct Randolli Functions.  In 25th Annual Symposium on Foundations of Computer Science, 1984., pages 464–479, 1984.  doi:10.1109/SFCS.1984.715949.
  * [GIKL23a] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang.  Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates, 2023.  arXiv:2305.13409.
  * [GIKL23b] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang.  Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates II: Single-Copy Measurements, 2023.  arXiv:2308.07175.
  * [GIKL23c] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang.  Improved stabilizer estimation via bell difference sampling, 2023.  arXiv:2304.13915.
  * [GTB23] Tudor Giurgica-Tiron and Adam Bouland.  Pseudorandomness from subset states, 2023.  arXiv:2312.09206.
  * [Han16] Steve Hanneke.  The optimal sample complexity of pac learning.  J. Mach. Learn. Res., 17(1):1319–1333, jan 2016.
  * [HG23] Dominik Hangleiter and Michael J. Gullans.  Bell sampling from quantum circuits, 2023.  arXiv:2306.00083v1.
  * [HH13] Ryan C. Harkins and John M. Hitchcock.  Exact learning algorithms, betting games, and circuit lower bounds.  ACM Trans. Comput. Theory, 5(4), nov 2013.  doi:10.1145/2539126.2539130.
  * [HHJ+17] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu.  Sample-Optimal Tomography of Quantum States.  IEEE Transactions on Information Theory, 63(9):5628–5641, 2017.  doi:10.1109/TIT.2017.2719044.
  * [HI19] Akinori Hosoyamada and Tetsu Iwata.  4-round luby-rackoff construction is a qprp.  In International Conference on the Theory and Application of Cryptology and Information Security, 2019.  URL: https://api.semanticscholar.org/CorpusID:147692931.
  * [HKP20] Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Predicting many properties of a quantum system from very few measurements.  Nature Physics, 16(10):1050–1057, 2020.  doi:10.1038/s41567-020-0932-7.
  * [HLB+24] Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean.  Learning shallow quantum circuits, 2024.  arXiv:2401.10095.
  * [HS05] Peter Hoyer and Robert Spalek.  Quantum fan-out is powerful.  Theory Computing, 1:81–103, 2005.  doi:10.4086/toc.2005.v001a005.
  * [IHM+19] Gembu Ito, Akinori Hosoyamada, Ryutaroh Matsumoto, Yu Sasaki, and Tetsu Iwata.  Quantum chosen-ciphertext attacks against feistel ciphers.  In Mitsuru Matsui, editor, Topics in Cryptology – CT-RSA 2019, pages 391–411, Cham, 2019. Springer International Publishing.
  * [JLS18] Zhengfeng Ji, Yi-Kai Liu, and Fang Song.  Pseudorandom Quantum States.  In Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, pages 126–152. Springer, 2018.  doi:10.1007/978-3-319-96878-0_5.
  * [JMW24] Fernando Granha Jeronimo, Nir Magrafta, and Pei Wu.  Pseudorandom and pseudoentangled states from subset states, 2024.  arXiv:2312.15285.
  * [KG15] Richard Kueng and David Gross.  Qubit stabilizer states are complex projective 3-designs, 2015.  arXiv:1510.02767.
  * [KKO13] Adam Klivans, Pravesh Kothari, and Igor C. Oliveira.  Constructing Hard Functions Using Learning Algorithms.  In 2013 IEEE Conference on Computational Complexity, pages 86–97, 2013.  doi:10.1109/CCC.2013.18.
  * [KQST23] William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal.  Quantum Cryptography in Algorithmica.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1589–1602, New York, NY, USA, 2023. Association for Computing Machinery.  doi:10.1145/3564246.3585225.
  * [Kre21] William Kretschmer.  Quantum Pseudorandomness and Classical Complexity.  In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:20, 2021.  doi:10.4230/LIPIcs.TQC.2021.2.
  * [Kum23] Vinayak M. Kumar.  Tight Correlation Bounds for Circuits Between AC0 and TC0.  In Amnon Ta-Shma, editor, 38th Computational Complexity Conference (CCC 2023), volume 264 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:40, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.CCC.2023.18.
  * [KV94] Michael J. Kearns and Umesh V. Vazirani.  An introduction to computational learning theory.  MIT Press, Cambridge, MA, USA, 1994.
  * [LC22] Ching-Yi Lai and Hao-Chung Cheng.  Learning Quantum Circuits of Some $T$ Gates.  IEEE Transactions on Information Theory, 68(6):3951–3964, 2022.  doi:10.1109/TIT.2022.3151760.
  * [LCLP10] Olivier Landon-Cardinal, Yi-Kai Liu, and David Poulin.  Efficient Direct Tomography for Matrix Product States, 2010.  arXiv:1002.4632.
  * [LMN93] Nathan Linial, Yishay Mansour, and Noam Nisan.  Constant depth circuits, Fourier transform, and learnability.  J. ACM, 40(3):607–620, jul 1993.  doi:10.1145/174130.174138.
  * [LOH23] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma.  Learning t-doped stabilizer states, 2023.  arXiv:2305.15398v3.
  * [LQS+23] Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao.  Quantum pseudorandom scramblers, 2023.  arXiv:2309.08941.
  * [Mon17] Ashley Montanaro.  Learning stabilizer states by Bell sampling, 2017.  arXiv:1707.04012.
  * [Moo99] Cristopher Moore.  Quantum circuits: Fanout, parity, and counting, 1999.  arXiv:quant-ph/9903046.
  * [MPS03] G. Mauro D’Ariano, Matteo G.A. Paris, and Massimiliano F. Sacchi.  Quantum Tomography.  Advances in Imaging and Electron Physics, 128:205–308, 2003.  doi:10.1016/S1076-5670(03)80065-4.
  * [MPSY24] Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen.  Simple constructions of linear-depth t-designs and pseudorandom unitaries, 2024.  arXiv:2404.12647.
  * [MR14] Ben Morris and Phillip Rogaway.  Sometimes-recurse shuffle.  In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology – EUROCRYPT 2014, pages 311–326, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
  * [MW16] Ashley Montanaro and Ronald de Wolf.  A Survey of Quantum Property Testing.  Number 7 in Graduate Surveys. Theory of Computing Library, 2016.  doi:10.4086/toc.gs.2016.007.
  * [MW20] Cody D. Murray and R. Ryan Williams.  Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma.  SIAM Journal on Computing, 49(5):STOC18–300–STOC18–322, 2020.  doi:10.1137/18M1195887.
  * [MY23] T. Metger and H. Yuen.  stateQIP = statePSPACE.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1349–1356, Los Alamitos, CA, USA, nov 2023. IEEE Computer Society.  doi:10.1109/FOCS57990.2023.00082.
  * [NC02] Michael A. Nielsen and Isaac Chuang.  Quantum Computation and Quantum Information, 2002.  doi:10.1017/CBO9780511976667.
  * [Nef94] C. Andrew Neff.  Specified precision polynomial root isolation is in NC.  Journal of Computer and System Sciences, 48(3):429–463, 1994.  doi:10.1016/S0022-0000(05)80061-3.
  * [NPVY24] Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen.  On the pauli spectrum of qac0, 2024.  arXiv:2311.09631.
  * [OKHHJ24] Michał Oszmaniec, Marcin Kotowski, Michał Horodecki, and Nicholas Hunter-Jones.  Saturation and recurrence of quantum complexity in random local quantum dynamics, 2024.  arXiv:2205.09734.
  * [OS17] Igor C. Oliveira and Rahul Santhanam.  Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness.  In Proceedings of the 32nd Computational Complexity Conference, CCC ’17, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [OS18] Igor Oliveira and Rahul Santhanam.  Pseudo-Derandomizing Learning and Approximation.  In Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), volume 116 of Leibniz International Proceedings in Informatics (LIPIcs), pages 55:1–55:19, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.APPROX-RANDOM.2018.55.
  * [OW16] Ryan O’Donnell and John Wright.  Efficient Quantum Tomography.  In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, pages 899–912, 2016.  doi:10.1145/2897518.2897544.
  * [RI11] Rizwana Rehman and Ilse C. F. Ipsen.  La budde’s method for computing characteristic polynomials, 2011.  arXiv:1104.3769.
  * [Ros23] Gregory Rosenthal.  Query and depth upper bounds for quantum unitaries via grover search, 2023.  arXiv:2111.07992.
  * [Ros24] Gregory Rosenthal.  Efficient quantum state synthesis with one query.  In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2508–2534, 2024.  doi:10.1137/1.9781611977912.89.
  * [RR97] Alexander A Razborov and Steven Rudich.  Natural proofs.  Journal of Computer and System Sciences, 55(1):24–35, 1997.  doi:10.1006/jcss.1997.1494.
  * [RY13] Thomas Ristenpart and Scott Yilek.  The mix-and-cut shuffle: Small-domain encryption secure against n queries.  In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, pages 392–409, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
  * [RY22] Gregory Rosenthal and Henry Yuen.  Interactive Proofs for Synthesizing Quantum States and Unitaries.  In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 112:1–112:4, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.ITCS.2022.112.
  * [TS16] Yasuhiro Takahashi and Tani Seiichiro.  Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits.  computational complexity, 25:849–881, 2016.  doi:10.1007/s00037-016-0140-0.
  * [Unr23] Dominique Unruh.  Towards compressed permutation oracles.  In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology – ASIACRYPT 2023, pages 369–400, Singapore, 2023. Springer Nature Singapore.
  * [VDB21] Ewout Van Den Berg.  A simple method for sampling random clifford operators.  In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 54–59, 2021.  doi:10.1109/QCE52317.2021.00021.
  * [Vol14] Ilya Volkovich.  On learning, lower bounds and (un)keeping promises.  In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming, pages 1027–1038, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
  * [Vol16] Ilya Volkovich.  A guide to learning arithmetic circuits.  In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1540–1561, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR.  URL: https://proceedings.mlr.press/v49/volkovich16.html.
  * [Wat99] John Watrous.  Space-Bounded Quantum Complexity.  Journal of Computer and System Sciences, 59(2):281–326, 1999.  doi:10.1006/jcss.1999.1655.
  * [Wat02] John Watrous.  Quantum statistical zero-knowledge, 2002.  arXiv:quant-ph/0202111.
  * [Wat03] John Watrous.  On the complexity of simulating space-bounded quantum computations.  compational complexity, 12:48–84, June 2003.  doi:10.1007/s00037-003-0177-8.
  * [Wat18] John Watrous.  The Theory of Quantum Information.  Cambridge University Press, 2018.
  * [WBS16] Jonathan Welch, Alex Bocharov, and Krysta M. Svore.  Efficient Approximation of Diagonal Unitaries over the Clifford+T Basis.  Quantum Info. Comput., 16(1–2):87–104, jan 2016.  doi:10.26421/QIC16.15-16-8.
  * [Wil88] J. H. Wilkinson.  The algebraic eigenvalue problem.  Oxford University Press, Inc., USA, 1988.
  * [Wil14] Ryan Williams.  Nonuniform acc circuit lower bounds.  J. ACM, 61(1), jan 2014.  doi:10.1145/2559903.
  * [Wil18] R. Ryan Williams.  New algorithms and lower bounds for circuits with linear threshold gates.  Theory of Computing, 14(17):1–25, 2018.  doi:10.4086/toc.2018.v014a017.
  * [Yue23] Henry Yuen.  An Improved Sample Complexity Lower Bound for (Fidelity) Quantum State Tomography.  Quantum, 7:890, January 2023.  doi:10.22331/q-2023-01-03-890.
  * [Zha16] Mark Zhandry.  A note on quantum-secure prps, 2016.  arXiv:1611.05564.
  * [Zha21] Mark Zhandry.  How to Construct Quantum Random Functions.  J. ACM, 68(5), aug 2021.  doi:10.1145/3450745.
  * [ZLK+23] Haimeng Zhao, Laura Lewis, Ishaan Kannan, Yihui Quek, Hsin-Yuan Huang, and Matthias C. Caro.  Learning quantum states and unitaries of bounded gate complexity, 2023.  arXiv:2310.19882.

##  Appendix A Decision Problem Circuit Lower Bounds With an Extra Circuit
Constraint

We now show the interesting result that non-trivial quantum state tomography
can imply decision complexity class separations between entirely _classical_
computational models. However, we will need to impose two assumptions on
$\mathfrak{C}$. The weaker assumption is the ability to implement the unitary
$H^{\otimes(n+1)}\cdot I^{\otimes n}\otimes X$, which was used in Lemma 3.8 to
construct binary phase states. The second assumption is the ability to perform
error reduction to arbitrary $\exp(-\mathrm{poly}(n))$ accuracy. The simplest
way to get error reduction is via majority and fanout gates, but since it’s
not clear that $\mathsf{QNC}^{0}$ or $\mathsf{QAC}^{0}$ can compute these
gates, the weakest circuit class that we’ve introduced that _does_ meet these
requirements is $\mathsf{QAC}^{0}_{f}$. As such, we will state our results in
terms of $\mathsf{QAC}^{0}_{f}$ for succinctness, though it should be
understood that any circuit class that meets these two requirements suffices
as well.

######  Lemma A.1.

For arbitrary fixed $f:\mathbb{N}\rightarrow\mathbb{R}^{+}$ and
$\delta:\mathbb{N}\rightarrow[0,1]$, let
$\mathfrak{C}\supseteq\mathsf{QAC}^{0}_{f}$ be a circuit class that is closed
under restrictions and define $\mathcal{C}_{\ell}$ to be the set of pure
states on $\ell$ qubits that can be constructed by
$\mathfrak{C}\left[f(\ell)+\ell\right]$ with depth at most $d+3$. Assume the
existence of an infinitely-often $(\kappa,\ell,m,s,\varepsilon)$-PRF against
uniform quantum computations that can be computed in time $t$ by a
deterministic Turing machine. If the concept class
$\mathcal{C}\coloneqq\bigcup_{\ell\geq 1}\mathcal{C}_{\ell}$ is
$\left(m\circ\ell^{-1},\,s\circ\ell^{-1},\,\varepsilon\circ\ell^{-1}+\sqrt{m\circ\ell^{-1}}\cdot\delta\right)$-distinguishable
then

$\mathsf{DTIME}\left[t\circ\kappa^{-1}\right]\not\subset\text{(depth
$d$)-}\mathfrak{C}\left[f\circ\ell\circ\kappa^{-1}\right].$

###### Proof.

Let $\left(\\{F_{k}\\}_{k\in\\{0,1\\}^{\kappa(n)}}\right)_{n\in\mathbb{N}}$ be
the the infinitely-often PRF against uniform quantum computations. Define the
language $L$ such that inputs $(x,k)\in L$ if and only if $F_{k}(x)=1$ when
$x\in\\{0,1\\}^{\ell}$ and $k\in\\{0,1\\}^{\kappa}$. Because the PRF is
computable in time $t$ by a deterministic Turing machine, $L$ lies in
$\mathsf{DTIME}\left[t\circ\kappa^{-1}\right]$.

We now need to show that $L$ is not in $\text{(depth
$d$)-}\mathfrak{C}\left[f\circ\ell\circ\kappa^{-1}\right]$. For the sake of
contradiction, assume that it was. Then using Lemma 3.8 and error-reduction
via majority and fanout, $\text{(depth
$d+3$)-}\mathfrak{C}\left[n+f\circ\ell\circ\kappa^{-1}(n)\right]$ can create
pseudorandom states. The fact that the depth only increases by $3$ follows
from the fact that $\mathfrak{C}\supset\mathsf{QAC}^{0}_{f}$ allows us to
perform arbitrary classical fanout, approximately compute the PRF, then take
the majority, to perform error reduction using only a depth increase of $2$.
Performing the circuit in Lemma 3.8 adds the final extra layer of depth. Since
this only needs $O(n)$ Hadamard and $X$ gates, the size increases by at most
$O(n)$ as well. Relative to the security parameter $n$: the number of samples
used by the distinguishing algorithm is $m\circ\ell^{-1}\circ\ell=m(n)$, the
running time is $O\left(s\circ\ell^{-1}\circ\ell\right)=O(s(n))$, and the
advantage is
$\varepsilon\circ\ell^{-1}\circ\ell+\sqrt{m\circ\ell^{-1}\circ\ell}\cdot\delta=\varepsilon+\sqrt{m}\cdot\delta$.
Finally, the size of the circuits generating $\mathcal{C}_{\ell}$ are
$O\left(f\circ\ell\right)=O\left(f\circ\ell\circ\kappa^{-1}\circ\kappa\right)$
such that the size relative to the key parameter $\kappa$ is
$O\left(f\circ\ell\circ\kappa^{-1}\right)$. It follows by the parameters of
the PRS and Lemma 4.3 that if $\mathcal{C}$ could be learned then the PRS does
not lie in
$\mathsf{pureState}\mathfrak{C}\left[f\circ\ell\circ\kappa^{-1}\right]_{\delta}$.
This is a contradiction, meaning that $L\not\in\text{(depth
$d$)-}\mathfrak{C}\left[f\circ\ell\circ\kappa^{-1}\right]$. ∎

######  Remark A.2.

Observe that Lemma A.1 requires a PRF while Lemma 6.2 only requires a PRS.
Using [Ros24, Theorem 7.1], if one only wants to show that
$\mathsf{EXP}\not\subset\text{(depth $d+O(1)$)-}\mathfrak{C}$, it is actually
possible to weaken Lemma A.1 to only use a PRS with the special property that
each amplitude (including phase information) can be computed in time
$\exp(\mathrm{poly}(n))$.

We can now combine Lemma A.1 and Corollary 3.11 to show a conditional circuit
lower bound. To handle the other side of the win-win-argument, we need the
following result.

######  Lemma A.3 ([CCZZ22]).

For every $k\in\mathbb{N}$, there exist a language $L_{k}\in\mathsf{PSPACE}$
such that $L_{k}\not\in\mathsf{BQSIZE}[n^{k}]$.

######  Theorem A.4 (Formal Statement of Theorem 1.3).

Let $\mathfrak{C}\supseteq\mathsf{QAC}^{0}_{f}$ be a circuit class that is
closed under restrictions. Define $\mathcal{C}_{\ell}$ to be the set of pure
states on $\ell$ qubits that can be exactly constructed by
$\mathfrak{C}[\mathrm{poly}(\ell)]$ with depth at most $d+3$. If there exists
a fixed constant $c\geq 2$ such that $\mathcal{C}\coloneqq\bigcup_{\ell\geq
1}\mathcal{C}_{\ell}$ is $\left(m,t,\varepsilon\right)$-distinguishable for
$m\leq 2^{\ell^{0.99}}$, $t\leq O\left(2^{\ell^{c}}\right)$, and
$\varepsilon\geq\frac{1}{2^{\ell^{0.99}}}$, then at least one of the following
must be true:

  * •

for all $k\geq 1$,
$\mathsf{BQSUBEXP}\not\subset\mathsf{BQSIZE}\left[n^{k}\right]$,

  * •

$\mathsf{E}\not\subset\text{(depth $d$)-}\mathfrak{C}[\mathrm{poly}(n)]$.

###### Proof Sketch.

We will again use a win-win argument, but now with $\mathsf{PSPACE}$ and
$\mathsf{BQSUBEXP}$. If $\mathsf{PSPACE}\subseteq\mathsf{BQSUBEXP}$ then using
Lemma A.3, we get $\mathsf{BQE}\not\subset\mathsf{BQSIZE}[n^{k}]$.

On the other hand, if $\mathsf{PSPACE}\not\subseteq\mathsf{BQSUBEXP}$ then we
can invoke Corollary 3.11 to show that there exists some infinitely-often
$\left(\kappa,\ell,q,s,\varepsilon\right)$-PRF against uniform quantum
computations where $\kappa(n)\leq n^{\alpha}$, $r(n)=\lfloor
2^{n^{\lambda}}\rfloor$, $\ell\leq\lfloor\log_{2}r\rfloor$, and
$s(n)=2^{n^{2\lambda}}$. By Lemma A.1 and a similar analysis to Theorems 6.3
and 6.4, we find that $\mathsf{E}\not\subset\text{(depth
$d$)-}\mathfrak{C}[\mathrm{poly}(n)]$. ∎

Because $\mathsf{TC}^{0}\subset\mathsf{QAC}^{0}_{f}$ [HS05, TS16], the second
scenario in Theorem A.4 also implies that
$\mathsf{E}\not\subset\mathsf{TC}^{0}$.

##  Appendix B Conditional (Non-Adaptive) Pseudorandom Unitaries and Circuit
Lower Bounds for Unitary Synthesis

Due to the recent results on pseudorandom unitaries, we sketch how the ability
to non-adaptively distinguish unitaries from Haar random (without access to
the inverse) implies unitary synthesis separations. Unitary synthesis capture
an even more general set of problems than state synthesis, such as certain
kinds of problems with quantum inputs and quantum outputs. For details on
unitary synthesis complexity class definitions, see [MY23, BEM+23].

We first need to introduce a distance measure between trace-preserving
completely positive maps. Like  (Trace Distance)., it bounds the maximum
distinguishability between two quantum operations.

######  Definition B.1 (Diamond Distance).

Let $\Phi,\Gamma:\mathcal{D}_{m}\rightarrow\mathcal{D}_{n}$ be two trace-
preserving completely positive maps. We define the diamond distance to be

$d_{\Diamond}(\Phi,\Gamma)\coloneqq\max_{\rho\in\mathcal{D}_{2m}}\lVert\left(\Phi\otimes
1_{m}\right)\rho-\left(\Gamma\otimes 1_{m}\right)\rho\rVert_{1}$

where $1_{m}$ is the identity channel on $m$ qubits.

Note that unlike  (Trace Distance)., diamond distance lies in $[0,2]$.

We also need a version of Corollary 2.6 for trace-preserving completely
positive maps.

######  Lemma B.2.

For trace-preserving completely positive maps $\Psi$ and $\Phi$, and
$m\in\mathbb{N}$,

$d_{\Diamond}(\Psi^{\otimes m},\Phi^{\otimes m})\leq m\cdot
d_{\mathrm{tr}}(\ket{\psi},\ket{\phi}).$

###### Proof.

Follows from the subadditivity of  (Diamond Distance). with respect to the
tensor product. ∎

######  Definition B.3 ($\mathsf{unitaryBQTIME}\\!\left[f\right]_{\delta}$,
$\mathsf{unitaryBQSPACESIZE}\\!\left[f\right]_{\delta}$).

Let $\delta:\mathbb{N}\rightarrow[0,1]$ and
$f:\mathbb{N}\rightarrow\mathbb{R}^{+}$ be functions. Then
$\mathsf{unitaryBQTIME}\\!\left[f\right]_{\delta}$ (resp.
$\mathsf{unitaryBQSPACESIZE}\\!\left[f\right]_{\delta}$) is the class of all
sequences of unitary matrices $(U_{x})_{x\in\\{0,1\\}^{*}}$ such that each
$U_{x}$ is a unitary on $\mathrm{poly}(\lvert x\rvert)$ qubits, and there
exists an $f$-time-uniform (resp. $f$-space-and-size-uniform) family of
general quantum circuits $\left(C_{x}\right)_{x\in\\{0,1\\}^{*}}$ such that
for all sufficiently large input size $\lvert x\rvert$,

$d_{\Diamond}(C_{x},U_{x})\leq\delta.$

######  Definition B.4 ($\mathsf{unitaryBQP}_{\delta}$,
$\mathsf{unitaryPSPACESIZE}_{\delta}$).

$\displaystyle\mathsf{unitaryBQP}_{\delta}\coloneqq\bigcup_{p}\mathsf{unitaryBQTIME}\\!\left[p\right]_{\delta}\,\,\,\text{
and
}\,\,\,\mathsf{unitaryPSPACESIZE}_{\delta}\coloneqq\bigcup_{p}\mathsf{unitaryBQSPACESIZE}\\!\left[p\right]_{\delta}$

where the union is over all polynomials $p:\mathbb{N}\rightarrow\mathbb{R}$.

We can likewise define $\mathsf{unitaryBQE}_{\delta}$ and
$\mathsf{unitaryBQP/poly}$ to be the analogues of $\mathsf{stateBQE}$ and
$\mathsf{stateBQP/poly}$ respectively. Finally, when dealing with _unitary_
circuit families, we will refer to the complexity classes with the prefix
$\mathsf{pureUnitary}$-, such as in $\mathsf{pureUnitaryBQE}$.

We now need to generalize both Lemmas 3.13 and 5.7 but for unitary synthesis.
The high-level idea is that both proofs implicitly work at the level of
unitaries, rather than states, in that they find a unitary that has the
correct property before arguing that the state that the unitary creates also
has a similar property. Put another way, Lemmas 3.13 and 5.7 follow as
corollaries of Lemmas B.5 and B.6.

######  Lemma B.5.

Let $k:\mathbb{N}\rightarrow\mathbb{R}^{+}$. For any
$\mathsf{unitaryA}_{\delta}\subset\mathsf{unitaryBQP/poly}_{\delta}$, if
$\mathsf{unitaryA}_{\delta}\not\subset\mathsf{unitaryBQTIME}\left[k\cdot
f\right]_{\delta+\exp(-k)}$ then
$\mathsf{A}\not\subset\mathsf{BQTIME}\left[\frac{f}{n^{\nu}}\right]$ for some
$\nu\geq 1$.

###### Proof Sketch.

The proof works the same ways as Lemma 3.13 and using the same language. This
is because in the proof of Lemma 3.13, we argue that if
$\mathsf{A}\subset\mathsf{BQTIME}\left[\frac{f}{n^{\nu}}\right]$ then the
description of any unitary in $\mathsf{A}$ could be learned, presenting a
contradiction. ∎

######  Lemma B.6.

For every fixed $k\in\mathbb{N}$,

$\mathsf{pureUnitaryPSPACE}_{0}\not\subset\mathsf{pureUnitaryBQSIZE}[n^{k}]_{0.98}.$

###### Proof Sketch.

The proof of Theorem 5.7 involves finding a unitary $V$ such that all
unitaries $U_{i}$ that can be synthesized by circuits in
$\mathsf{BQSIZE}[n^{k}]$ cannot create the same state as $V$ when acting on
the all zeros state. In fact, no $U_{i}$ can create a state that is even
$0.49$-close in  (Trace Distance).. It follows by the definition of  (Diamond
Distance). that $d_{\Diamond}(U_{i},V)>0.98$ for all $U_{i}$.161616Recall that
(Diamond Distance). lies in $[0,2]$. Since this holds for every $k$, we find
that
$\mathsf{pureUnitaryPSPACE}_{0}\not\subset\mathsf{pureUnitaryBQSIZE}[n^{k}]_{0.98}$.
∎

###  B.1 Pseudorandom Unitaries

We start by adapting our pseudorandom objects from quantum states to
unitaries, which was a notion also introduced by [JLS18]. [MPSY24] recently
showed how to build unitaries that are pseudorandom when the adversary is not
allowed to adapt the algorithm based on prior measurement results.

######  Definition B.7 (PRU).

Let $\kappa,\ell,m:\mathbb{N}\rightarrow\mathbb{N}$, let
$s:\mathbb{N}\rightarrow\mathbb{R}^{+}$, and let
$\varepsilon:\mathbb{N}\rightarrow[0,1]$. We say that a sequence of keyed pure
unitaries $\left(\\{U_{k}\\}_{k\in\\{0,1\\}^{\kappa}}\right)_{n\in\mathbb{N}}$
is an infinitely-often $(\kappa,\ell,m,s,\varepsilon)$-PRU if for a uniformly
random $k\in\\{0,1\\}^{\kappa}$, no quantum algorithm running in time $s$ can
distinguish $m$ queries of $U_{k}$ from $m$ queries to a Haar random unitary
on $\ell$ qubits by at most $\varepsilon$. Formally, for all $s$-time-uniform
quantum oracle circuits $(C_{n}^{(\cdot)})_{n\in\mathbb{N}}$ that output the
one qubit state $\rho_{n}^{\mathcal{O}}$ when querying oracle $\mathcal{O}$:

$\displaystyle\bigg{\lvert}\mathop{\bf
E\/}_{k\sim\\{0,1\\}^{\kappa}}\mathrm{tr}\\!\left[\ket{1}\\!\\!\bra{1}\cdot\rho_{n}^{U_{k}}\right]-\mathop{\bf
E\/}_{\mathcal{U}\sim\mu_{\mathrm{Haar}}}\mathrm{tr}\\!\left[\ket{1}\\!\\!\bra{1}\cdot\rho_{n}^{\mathcal{U}}\right]\bigg{\rvert}\leq\varepsilon\,$

holds on infinitely many $n\in\mathbb{N}$.

We now detail the construction used in [MPSY24]. Denote
$\mathcal{P}_{\ell}:=\\{p:\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}^{\ell}\\}$ as
the set of all permutations on $\ell$-bits, and let $p^{-1}$ refer to the
inverse permutation such that $p\circ p^{-1}$ is the identity function.
Furthermore, for $p\in\mathcal{P}_{\ell}$ denote the $\ell$-qubit in-place
permutation unitary to be $U_{p}\coloneqq\ket{x}\mapsto\ket{p(x)}$.

######  Lemma B.8 (Proof of [MPSY24, Theorem 3.1]).

Let $p\in\mathcal{P}$ be a random permutation on $\ell$-qubits, $F$ be a
$2^{\ell}\times 2^{\ell}$ diagonal matrix whose entries are random $\\{\pm
1\\}$ values (i.e., the diagonal is the truth table for
$f\sim\mathfrak{F}_{\ell,1}$), and $C$ be a random Clifford circuit on $\ell$
qubits. If $\mathcal{U}$ is an $\ell$-qubit Haar random unitary, then
$\left(U_{p}FC\right)^{\otimes m}$ is
$O\\!\left(\frac{m}{\sqrt{2^{n}}}\right)$-close to $\mathcal{U}^{\otimes m}$
in expected  (Diamond Distance)..

Because of these random permutations, we will not introduce the idea of a
pseudorandom permutation.

######  Definition B.9 (PRP).

Let $\kappa,\ell:\mathbb{N}\rightarrow\mathbb{N}$, let
$q,s:\mathbb{N}\rightarrow\mathbb{R}^{+}$, and let
$\varepsilon:\mathbb{N}\rightarrow[0,1]$. We say that a sequence of keyed-
permutations
$\left(\\{P_{k}\in\mathfrak{F}_{\ell,\ell}\\}_{k\in\\{0,1\\}^{\kappa}}\right)_{n\in\mathbb{N}}$
is an infinitely-often $(\kappa,\ell,q,s,\varepsilon)$-PRP if for a uniformly
random $k\in\\{0,1\\}^{\kappa}$, no quantum algorithm running in time $s$ can
distinguish black-box access to $\mathcal{O}_{P_{k}}$ from black-box access to
$\mathcal{O}_{p}$ for random _permutation_ $p\in\mathcal{P}_{\ell}$ using at
most $q$ queries by at most $\varepsilon$. Formally, for all $s$-time-uniform
oracle quantum circuits $(C^{(\cdot)}_{n})_{n\in\mathbb{N}}$ such that each
$C^{\mathcal{O}}_{n}$ takes no inputs, queries $\mathcal{O}$ at most $q$
times, and outputs a single qubit state $\rho_{n}^{\mathcal{O}}$:

$\displaystyle\bigg{\lvert}\mathop{\bf
E\/}_{k\sim\\{0,1\\}^{\kappa}}\mathrm{tr}\\!\left[\ket{1}\\!\\!\bra{1}\cdot\rho_{n}^{\mathcal{O}_{P_{k}}}\right]-\mathop{\bf
E\/}_{p\sim\mathcal{P}_{\ell}}\mathrm{tr}\\!\left[\ket{1}\\!\\!\bra{1}\cdot\rho_{n}^{\mathcal{O}_{f}}\right]\bigg{\rvert}\leq\varepsilon\,$

holds on infinitely many $n\in\mathbb{N}$.

######  Remark B.10.

The above definition, where the quantum adversary can only make XOR queries
for the forward direction of the permutation, is what is known as quantum
chosen-plaintext attack (qCPA) secure. However, for $p\in\mathcal{P}_{\ell}$
note that queries to XOR oracle $\mathcal{O}_{p}$ are not the same as queries
to the in-place permutation $U_{p}$. To achieve security against adversaries
with queries to $U_{p}$ like we will need to invoke Lemma B.8, it suffices to
look at an even stronger notion of security called quantum chosen-ciphertext
attack (qCCA) secure, where the adversary has access to $\mathcal{O}_{p^{-1}}$
as well. This is because one query to $\mathcal{O}_{p}$ and
$\mathcal{O}_{p^{-1}}$ each can be used to simulate $U_{p}$ (see proof of
Corollary B.14).

######  Lemma B.11 (Generalization of proofs of [RY13, MR14, Zha16]).

For $r=\Theta(n^{2})$, let $a_{1},\dots,a_{r}$ be random $n$-bit strings and
$f_{1},\dots,f_{r}$ be random functions from $\mathfrak{F}_{n,1}$. Using these
resources, there is an $\Theta(n^{2})$-time construction of permutations $p$
and $p^{-1}$ that are distinguishable from a true random permutation with
advantage at most $\frac{1}{2^{n}}$, even when the adversary is
computationally unbounded and has learned the entire truth table.

Note that Lemma B.11 is extremely powerful, as the adversary is allowed to
know everything about the permutation, as well as be computationally
unbounded. Because of this combination, even quantum queries to the inverse
can be simulated, showing that the construction is qCCA-secure.171717This
observation is the central point of [Zha16], as the original analyses in
[RY13, MR14] were only for classical security.

######  Lemma B.12.

Let $G$ be an infinitely-often $(\kappa,m,s,\varepsilon)$-PRG against uniform
quantum computations that is computable in time $t$ by a deterministic Turing
machine. Then for $\ell=o\\!\left(\log\frac{m}{\log^{2}m}\right)$, there
exists an infinitely-often qCCA-secure

$\left(\kappa,\,\ell,\,q,\,s-O(q\cdot
m\cdot\ell^{2}),\,\varepsilon+\frac{1}{2^{\ell}}\right)\text{-PRP}$

against uniform quantum computations that can be computed in time
$O(t+m\cdot\ell^{2})$.

###### Proof.

We will simply replace the random strings and random functions in Lemma B.11
with pseudorandom strings and pseudorandom truth tables from the output of the
PRG.

First we show that we have enough pseudorandom bits to do so. Let
$r=\Theta(\ell^{2})$ be the parameter from Lemma B.11. We start by setting
aside $r\cdot\ell$ bits for the $a_{i}$. We then need $r\cdot 2^{\ell}$ bits
for the truth table of the $f_{i}$. This means that we need at most $r\cdot
2^{\ell+1}=\Theta\\!\left(\ell^{2}\cdot 2^{\ell}\right)$ bits, such that if
$\ell=o\\!\left(\log\frac{m}{\log^{2}m}\right)$ then $\Theta(\ell^{2}\cdot
2^{\ell})\leq m$ for sufficiently large $n$.

As for time complexity, getting all of the pseudorandom bits takes $O(m)$
time, for $r=\Theta(\ell^{2})$ rounds. This makes the total time complexity
simply $\Theta(m\cdot\ell^{2})$.

Finally, for security we use two hybrids: first by replacing the pseudorandom
strings and functions with truly random strings and functions, and then
finally comparing this to a truly random permutation. By the reverse triangle
inequality, and Lemma B.11, an advantage of $\varepsilon+\frac{1}{2^{\ell}}$
would suffice to distinguish the underlying PRG with advantage at least
$\varepsilon$. ∎

######  Lemma B.13.

Let $G$ be an infinitely-often $(\kappa,m,s,\varepsilon)$-PRG against uniform
quantum computations that is computable in time $t$ by a deterministic Turing
machine. Then for $\ell=o\\!\left(\log\frac{m}{\log^{2}m}\right)$, there
exists an infinitely-often non-adaptive qPCA-secure

$\left(\kappa,\,\ell,\,q,\,s-O(q\cdot
m\cdot\ell^{2}),\,\varepsilon+O\\!\left(\frac{q}{\sqrt{2^{\ell}}}\right)\right)\text{-PRU}$

against uniform quantum computations that can be computed in time
$O(t+m\cdot\ell^{2})$.

###### Proof.

We split up the output of the PRG to get two different infinitely-often
$(\kappa,m/2,s,\varepsilon)$-PRG. Note that this ensures that the two PRGs are
hard instances at the same time, as opposed to two independent infinitely-
often PRGs that may only be hard on different input lengths. Use Lemma B.12 to
create a pseudorandom permutation $p$ from one of the PRGs and Lemma 3.5 to
create pseudorandom function $f$ using the other PRG. Because the output of
the original PRG was halved, this only additively decreases the maximum value
of $\ell$ (i.e., the number of qubits $p$ and $f$ act on) by at most $1$.

We now need to create a non-adaptive PRU as per Lemma B.8. To turn
$\mathcal{O}_{p}$ into $U_{p}$, we can use the fact that
$\mathcal{O}_{p^{-1}}$ is also efficiently computable to perform

$\mathcal{O}_{p^{-1}}\cdot\mathrm{SWAP}_{AB}\cdot\mathcal{O}_{p}\ket{x}_{A}\ket{0}_{B}=\mathcal{O}_{p^{-1}}\cdot\mathrm{SWAP}_{AB}\ket{x}_{A}{\ket{p(x)}}_{B}=\mathcal{O}_{p^{-1}}\ket{p(x)}_{A}\ket{x}_{B}=\ket{p(x)}_{A}\ket{0}_{B}.$

Likewise, $f$ can be efficiently made into the diagonal of a matrix by the use
of Hadamards.181818This is the standard XOR-to-phase oracle conversion [Aar22,
Lecture 17]

By the reverse Triangle inequality, Definitions B.1, 2.3, 3.5, B.12 and B.8,
the allowed advantage is
$\varepsilon+\frac{1}{2^{\ell}}+O\left(\frac{q}{\sqrt{2^{\ell}}}\right)=\varepsilon+O\left(\frac{q}{\sqrt{2^{\ell}}}\right)$.
Since the infinitely-often PRP $p$ and infinitely-often PRF $f$ are both hard
on the smae instances an infinite number of times, the resulting construction
is an infinitely-often PRU.

Sampling a Clifford circuit on $\ell$-qubits takes $O(\ell^{2})$ time [VDB21],
and creating a phase unitary from an XOR oracle takes $O(m+\ell)$ time given
the output of the PRG. However, creating the permutation from Lemma B.12 takes
$O(m\cdot\ell^{2})$ time, so querying the PRU takes time
$O\left(m\cdot\ell^{2}\right)$ time given access to the output of the PRG.
Therefore, the PRU is secure against $s-O\left(q\cdot
m\cdot\ell^{2}\right)$-time adversaries. The key length becomes
$\kappa^{\prime}\coloneqq\kappa+O(\ell^{2})\leq n^{\alpha^{\prime}}$ for some
$\alpha^{\prime}\geq\alpha\geq 1$, to account for the sampling of the random
Clifford circuit. ∎

######  Corollary B.14.

Suppose there exists a $\gamma>0$ such that
$\mathsf{PSPACE}\not\subset\mathsf{BQTIME}\left[2^{n^{\gamma}}\right]$. Then,
for some choice of constants $\alpha\geq 1$, and $\lambda\in(0,1/5)$ and
sufficiently large $n\in\mathbb{N}$, there exists an infinitely-often non-
adaptive qPCA-secure

$\left(\kappa,\ell,q,s,\frac{1}{r}+O\left(\frac{q}{\sqrt{2^{\ell}}}\right)\right)\text{-PRU}$

against uniform quantum computations where $\kappa\leq n^{\alpha}$, $r=\lfloor
2^{n^{\lambda}}\rfloor$, $\ell=o\\!\left(\log\frac{r}{\log r}\right)$,
$s=2^{n^{2\lambda}}$, and $m=o\left(\frac{s}{r\cdot\ell^{2}}\right)$. In
addition, the PRU lies in $\mathsf{pureUnitaryBQE}_{\exp}$.

###### Proof.

Combine Lemmas 3.10 and B.13. ∎

###  B.2 Unitary Distinguishing Implies Non-Uniform Unitary Synthesis Lower
Bounds

Informally, define $(m,t,\varepsilon)$-distinguishing of unitaries from Haar
random unitaries to be analogous to distinguishing states from Haar random
states (Definition 4.2). For our purposes, the distinguisher will not have
access to the inverse unitary as we do not have proven security for this
learning model using Lemma B.8.

######  Lemma B.15.

For arbitrary fixed $f:\mathbb{N}\rightarrow\mathbb{R}^{+}$ and
$\delta:\mathbb{N}\rightarrow[0,1]$, let $\mathfrak{C}$ be a circuit class
that is closed under restrictions and define $\mathcal{C}_{\ell}$ to be the
set of pure states on $\ell$ qubits that can be constructed by
$\mathfrak{C}\left[f(\ell)\right]$. Assume the existence of an infinitely-
often (resp. non-adaptive) $(\kappa,\ell,q,s,\varepsilon)$-PRU against uniform
quantum computations that can be computed in time $t$. If the concept class
$\mathcal{C}\coloneqq\bigcup_{\ell\geq 1}\mathcal{C}_{\ell}$ is
$\left(q\circ\ell^{-1},\,s\circ\ell^{-1},\,\varepsilon\circ\ell^{-1}+m\circ\ell^{-1}\cdot\delta\right)$-distinguishable
(resp. using non-adaptive queries) then

$\mathsf{pureUnitaryBQTIME}\left[t\circ\kappa^{-1}\right]_{\exp}\not\subset\mathsf{pureUnitary}\mathfrak{C}\left[f\circ\ell\circ\kappa^{-1}\right]_{\delta}.$

###### Proof Sketch.

The proof follows the same way as in Lemma 6.2, except using Lemma B.2 in
place of Corollary 2.6. This change from $\sqrt{m}$ to simply $m$ does not
affect the proof as it is still killed by the $\delta=\exp(-p)$ term for
arbitrary polynomial $p$. ∎

######  Theorem B.16 (Formal Statement of Theorem 1.4).

Let $\mathfrak{C}$ be a circuit class that is closed under restrictions.
Define $\mathcal{C}_{\ell}$ to be the set of unitaries on $\ell$ qubits that
can be exactly constructed by $\mathfrak{C}[\mathrm{poly}(\ell)]$. If there
exists a fixed constant $c\geq 2$ such that
$\mathcal{C}\coloneqq\bigcup_{\ell\geq 1}\mathcal{C}_{\ell}$ is
$\left(m,t,\varepsilon\right)$-distinguishable for $m\leq 2^{\ell^{0.99}}$,
$t\leq O\left(2^{\ell^{c}}\right)$, and
$\varepsilon\geq\omega\left(\frac{1}{2^{\ell^{0.99}}}\right)$ by a non-
adaptive algorithm without access to the inverse, then at least one of the
following is true:

  * •

for every $k\geq 1$:
$\mathsf{pureUnitaryBQSUBEXP}_{\exp}\not\subset\mathsf{pureUnitaryBQSIZE}[n^{k}]_{0.49}$,

  * •

$\mathsf{pureUnitaryBQE}_{\exp}\not\subset\mathsf{pureUnitary}\mathfrak{C}_{\exp}$.

###### Proof Sketch.

We instantiate the win-win argument in the same way as Theorems 6.3 and 6.4,
but replacing the PRS with the PRU from Corollary B.14 and with the cases
based on the relationship between $\mathsf{pureUnitaryPSPACESIZE}_{\exp}$ and
$\mathsf{pureUnitaryBQSUBEXP}_{\exp}$. When
$\mathsf{pureUnitaryPSPACESIZE}_{\exp}\subset\mathsf{pureUnitaryBQSUBEXP}_{\exp}$
then we apply Lemma B.6. In contrast, when
$\mathsf{pureUnitaryPSPACESIZE}_{\exp}\not\subset\mathsf{pureUnitaryBQSUBEXP}_{\exp}$
we use Lemma B.5 to show that $\mathsf{PSPACE}\not\subset\mathsf{BQSUBEXP}$.
This allows us to use Corollaries B.14 and B.15 to complete the proof using a
similar analysis to Theorems 6.3 and 6.4 ∎

######  Remark B.17.

Distinguishing copies of a fixed quantum state from Haar random actually
follows as a special case of algorithms that distinguish unitaries from Haar
random. This makes distinguishing with unitary query access strictly easier,
even when restricted to non-adaptivity and no access to the inverse. It
intuitively follows that the resulting separation is weaker, as state
synthesis separations imply unitary synthesis separations.

######  Remark B.18.

If Lemma B.8 were replaced with a sufficiently efficient and secure PRU
construction that allowed adaptivity then the distinguishing algorithm in
Theorem B.16 would also be allowed adaptivity. Likewise, if the PRU was made
secure against access to the inverse unitary then the learning algorithms in
Theorem B.16 would also be allowed access to the inverse unitary.

######  Remark B.19.

We would ideally like to generalize Theorem B.16 to a version like Corollary
6.5 that deals with _learning_ , as in quantum process tomography, rather than
distinguishing. A naïve approach, assuming access to the inverse, would be to
replace the SWAP test in Lemma 4.5 with the identity property test [MW16].
This simply involves measuring the Choi state of $\widehat{C}\cdot
C^{\dagger}$ in the Bell basis and seeing if it returns the canonical Bell
state. As noted by [MW16, Section 5.1.1], identity testing to even a constant
distance in operator norm requires $\Omega\\!\left(\sqrt{2^{n}}\right)$
queries to the unknown quantum circuit. Instead, these tests work well in an
average-case sense, such as when

$d_{\text{avg}}(U,V)\coloneqq\mathop{\bf
E\/}_{\ket{\psi}\sim\mu_{\text{Haar}}}\left[d_{\mathrm{tr}}(U\ket{\psi},V\ket{\psi})\right]$

is small. Luckily, this soundness lowerbound does not directly apply, as we
only need to have soundness against Haar random unitaries, which is easier
than dealing with adversarially chosen unitaries. We also need our test to be
_tolerant_ , such that when $d_{\Diamond}(U,V)$ (or $d_{\text{avg}}$) is
small, rather than just $0$, then the test accepts with high probability,
giving us the ability to distinguish the two cases. We leave this analysis
(and/or analysis of other candidate tests and learning-to-decision reductions)
as an open question for future work.

We note that learning with respect to the uniform distribution over
computational basis state is the exact setting of [AGG+22, Theorem 3.1] and
uses natural properties to distinguish the unitary from a unitary implementing
the XOR query of a random Boolean function. [ZLK+23] likewise uses learning
with respect to $d_{\text{avg}}$ to distinguish against random Boolean
functions. Both results are (to the authors’ knowledge) not comparable to
distinguishing against Haar random unitaries.

######  Remark B.20.

Because of the additional complexities of constructing the PRU/PRP in
Corollary B.14, it is not clear how to get a version of Theorem A.4 for
unitary distinguishing by building a PRU. Specifically, due to the recursive
nature of the constructions in [RY13, MR14], naïvely implementing the PRP
would increase the circuit depth by an additive factor of $\Theta(n^{2})$.
This would seem to disqualify all of $\mathsf{QAC}_{f}$ and any other shallow-
depth circuit classes for instance. Ideally, we would have have been able to
use a simpler construction of pseudorandom permutations, such as the Ruby-
Lackoff constructions based on balanced Feistel networks with constant rounds,
but there is currently no known proof of security against quantum adversaries
with access to the in-place permutation oracle for these constructions. While
it was shown that 4-round Ruby-Lackoff is qCPA-secure with the XOR oracle
[HI19], 4-rounds was also shown to not be qCCA-secure [IHM+19] (see Remark
B.10 for why this matters).191919Based on [Unr23, Footnote 3] there is reason
to believe that even the qCPA-security of 4-round Ruby-Lackoff is not clear.
Because Clifford circuits fall under $\mathsf{QAC}^{0}_{f}$ [AG04, Ros24], if
$O(1)$-round Ruby-Lackoff _was_ shown to be provably qCCA-secure then the
depth increase from implementing the PRU would only be a constant and allow us
to make a similar statement to Theorem A.4 for process tomography.
Additionally, as we learn more about efficient construction of PRUs [LQS+23,
MPSY24, CBB+24], the need for a pseudorandom permutation might be removed
altogether.

An alternative approach to showing circuit lower bounds for decision problems
via learning algorithms would be to generalize the learning-to-distinguisher
in [ZLK+23, Theorem 19] to adversaries with sub-exponential number of queries
allowed, as the stated result only applies to adversaries with a polynomial
number of allowed queries. By substituting this reduction in place of [AGG+22,
Theorem 3.1], one would recover a result showing that learning with respect to
$d_{\text{avg}}$ (i.e., squared loss under the Haar measure, as opposed to
uniform over computational basis states like in [AGG+22]) implies circuit
lower bounds for decision problems.

##  Appendix C Approximating Trace Distance in Polynomial Space

We combine the ideas behind the proof sketch of [Wat02, Corollary 10 and
Proposition 11] with the proof that $\mathsf{BQP}\subseteq\mathsf{PSPACE}$
[BV97] to show that the trace distance of states produced by
$\mathrm{poly}(n)$ size general quantum circuits can be computed using only
$\mathrm{poly}(n)$ space by a deterministic Turing machine (i.e., Lemma 5.6).

To start, we show the folklore result(s) that, when represented as a matrix,
any state $\rho$ that is produced by a general quantum circuit of size
$\mathrm{poly}(n)$ can have its entries be approximated to arbitrary inverse
exponential precision in $\mathrm{poly}(n)$ space [NC02, Section
4.5.5].202020In the language of [Ros24, Definition 5.1], these would be
considered $\mathsf{polyL}\text{-explicit}$. To do so, we first start with
applying the unitary (Lemma C.1), then tracing out the ancilla qubits
(Corollary C.2).

For ease of notation, we will say that a value can be computed in
$\mathrm{poly}(n)$ space if the value can be approximated to arbitrary
$\exp(-\mathrm{poly}(n))$ accuracy in $\mathrm{poly}(n)$ space. As long as the
values are bounded in $[-1,1]$ and there are not a
$\omega(\exp(\mathrm{poly}(n)))$ many arithmetic operations, then the triangle
inequality and Cauchy-Schwarz ensures us that we can act as if there are no
errors, by simply decreasing the error of each value accordingly.

######  Lemma C.1 (Folklore).

Given _unitary_ quantum circuit $C$ of size $s\leq 2^{\mathrm{poly}(n)}$ and
space $m=\mathrm{poly}(n)$ and a quantum state $\rho$ on at most $m$ qubits
whose entries (i.e., $\rho_{ij}\coloneqq\braket{i}{\rho}{j})$ can computed in
$\mathrm{poly}(n)$ space, the entries of $C\rho C^{\dagger}$ can also be
computed in $\mathrm{poly}(n)$ space.

###### Proof.

The proof idea is similar to the one showing that
$\mathsf{BQP}\subseteq\mathsf{PSPACE}$. Let $C$ be broken up into its
elementary gates as $C\coloneqq C_{1}C_{2}\dots C_{s}$. Since
$I=\sum_{y\in\\{0,1\\}^{m}}\ket{y}\\!\\!\bra{y}$, we can rewrite the output
expression as:

$\displaystyle\braket{i}{C\rho C^{\dagger}}{j}$
$\displaystyle=\braket{i}{C_{1}C_{2}\dots C_{s}\rho C_{s}^{\dagger}\dots
C_{2}^{\dagger}C_{1}^{\dagger}}{j}$
$\displaystyle=\sum_{y_{1},y_{2},\dots,y_{2s}\in\\{0,1\\}^{m}}\braket{i}{C_{1}}{y_{1}}\braket{y_{1}}{C_{2}}{y_{2}}\dots\braket{y_{s-1}}{C_{s}}{y_{s}}\braket{y_{s}}{\rho}{y_{s+1}}\dots\braket{y_{2s}}{C_{1}^{\dagger}}{j}.$

Since each $C_{i}\in\\{H,T,\mathrm{CNOT}\\}$, each
$\braket{y_{i}}{C_{i+1}}{y_{i+1}}$ must lie in the set
$\\{0,\pm\frac{1}{\sqrt{2}},1,i\\}$. Therefore, each
$\braket{y_{i}}{C_{i+1}}{y_{i+1}}$ can be computed exactly using
$\mathrm{poly}(m)$ space.212121If we weren’t using the
$\\{H,\mathrm{CNOT},T\\}$ gate set, then we can just use the  (Solovay-Kitaev
algorithm). to approximate it with the $\\{H,\mathrm{CNOT},T\\}$ gate set to
sufficient error. This will not affect the amount of space used by more than a
polynomial. Furthermore, we observe that each term in the above summation is
the product of $2s$ many $\braket{y_{i}}{C_{i+1}}{y_{i+1}}$ multiplied by
$\braket{y_{s}}{\rho}{y_{s+1}}$, such that the product either has the form
$\braket{y_{s}}{\rho}{y_{s+1}}\frac{i^{\ell}}{\sqrt{2}^{k}}$ for
$\ell\in\\{0,1,2,3\\}$ and $k\in\\{0,\dots,2s\\}$ or is just zero. Either way,
it can be computed using $\mathrm{poly}(n,m,\log s)$ space. It follows that
the entire summation can be approximated to accuracy $\exp(-k)$ in
$\mathrm{poly}(n,m,\log s,k)=\mathrm{poly}(n,k)$ space by approximating up to
$\mathrm{poly}(k)$-bits of precision. ∎

######  Corollary C.2 (Folklore).

Given a _unitary_ quantum circuit $C$ of size $s\leq 2^{\mathrm{poly}(n)}$ and
space $m=\mathrm{poly}(n)$ and let $\rho$ be the output of $C$. The $(i,j)$-th
entry of $\rho$ (i.e., $\rho_{ij}\coloneqq\braket{i}{\rho}{j}$) can be
computed in $\mathrm{poly}(n)$ space.

###### Proof.

Any unitary circuit can be decomposed into the unitary stage and then the
tracing out stage at the end. Since it is clear that the entries of our
starting state, $\ket{0\dots 0}\\!\\!\bra{0\dots 0}$ can be computed in
$\mathrm{poly}(n)$ space, it follows from Lemma C.1 that after applying the
unitary to the all-zeros state, the new quantum state’s entries can be
computed in $\mathrm{poly}(n)$ space. We then need to figure out the effect of
tracing out at most $\mathrm{poly}(n)$-qubits.

We can assume WLOG that we trace out the final qubit(s) because we use SWAP
gates at the end of the unitary to move the qubits that will be traced out to
the end. If we are tracing out $k=\mathrm{poly}(n)$ qubits, we can then
express the new entries to compute as:

$\displaystyle\braket{i}{C\rho C^{\dagger}}{j}$
$\displaystyle=\braket{i}{\left(\sum_{x\in\\{0,1\\}}\left(I^{\otimes
m-k}\otimes\bra{x}\right)\rho\left(I^{\otimes
m-k}\otimes\ket{x}\right)\right)}{j}$
$\displaystyle=\sum_{x\in\\{0,1\\}^{k}}\braket{i,x}{\rho}{j,x},$

which is just the sum of $\exp(\mathrm{poly}(n))$-many things that we can
compute in $\mathrm{poly}(n)$ space. ∎

We now move onto the problem of approximating trace distance. To compute the
trace distance between these two states, we need to find the sum of the
absolute value of its eigenvalues. The following two results will allow us to
find the roots of the characteristic polynomial (i.e., the eigenvalues) of
$\rho-\sigma$.

######  Lemma C.3 ([BOFKT88, Nef94]).

Given a polynomial $p(z)$ of degree $d$ with $m$-bit coefficients and an
integer $\mu$, the problem of determining all its roots with error less than
$2^{-\mu}$ is considered. It is shown that this problem can be solved by a
$\mathrm{polylog}\left(d+m+\mu\right)$-space-uniform _Boolean_ circuit of
depth at most $\mathrm{polylog}\left(d+m+\mu\right)$ on
$\mathrm{poly}\log(d+m+\mu)$ many bits if $p(z)$ has all real roots.

######  Lemma C.4 ([Bor77, Lemma 1]).

A _space-uniform_ Boolean circuit of size $s$ and depth $d$ can be simulated
by a deterministic Turing machine in space at most $d+\log(s)$.

By combining Lemmas C.3 and C.4, we get that the roots of certain polynomials
can be approximate to high precision in $\mathrm{poly}(n)$ space.

We now have the ingredients necessary to show that the trace distance of
states produced by $O\\!\left(2^{\mathrm{poly}(n)}\right)$-size and
$\mathrm{poly}(n)$-space unitary quantum circuits can also be approximated to
high precision in $\mathrm{poly}(n)$ space.

See 5.6

###### Proof.

By Corollary C.2, each entry of both $\rho$ and $\sigma$ can be approximated
to high accuracy using $\mathrm{poly}(n)$ space, so each entry of
$\rho-\sigma$ can also be well approximated. From here, let $f(x)$ be the
characteristic polynomial of $\rho-\sigma$. It follows that any coefficient of
$f(x)$ can be highly approximated using $\mathrm{poly}(n)$ space as well, via
the Faddeev-Leverrier algorithm 222222In principle this approach is not
numerically stable [RI11, Wil88], such that a more numerically stable approach
would be more space efficient. This is because far less bits of precision
would have to be used in previous steps to compensate for the numerical
instability. [Csa75, Corollary 2].

We note that the characteristic polynomial of $\rho-\sigma$ has a degree
$2^{n}$ with all real roots. It follows from Lemmas C.3 and C.4 that
$d_{\mathrm{tr}}(\rho,\sigma)\coloneqq\frac{1}{2}\sum_{i}\lvert\lambda_{i}\rvert$
can be computed by a deterministic Turing machine in $\mathrm{poly}(n)$ space.
∎

##  Appendix D Trivial Learners

Observe that in Corollaries 6.4 and A.4, there are three important parameters
of the algorithm that all must simultaneously meet some condition. In this
section, we highlight how satisfying any two of these conditions is trivially
easy for states produced by polynomial-size unitary quantum circuits. Clearly,
if samples are not a concern then full pure state tomography can be done in
$2^{O(n)}$ time to constant advantage [FBaK21]. If one instead wants to
satisfy the advantage and sample requirements, for instance, then one can run
an exhaustive search using classical shadows [HKP20, BO21, ZLK+23] over all
unitary circuits of size at most $n^{\omega(1)}$. This will only use
$O(n^{\omega(1)})$ samples, but the time complexity will be
$2^{\omega(\mathrm{poly}(n))}$.

Finally, if only $O\\!\left(\frac{1}{2^{n}}\right)$ advantage is desired then
no measurements even have to be taken. Specifically, by outputting a random
stabilizer state, every concept class can be

$\left(0,n^{2},1-\frac{\theta}{2^{n+1}},(1-\theta)^{2}\left(\frac{1}{2}+\frac{1}{2^{n+1}}\right)\right)\text{-learned}$

for arbitrary $\theta\in[0,1]$. In fact, any $2$-design suffices for this
argument, the only difference is how efficiently can such a state be sampled
directly affects the runtime of the “learner”. To this end, we note that
uniformly random stabilizer states can be efficiently sampled in $O(n^{2})$
time.

######  Lemma D.1 ([VDB21]).

There is a classical algorithm that samples a uniformly random element of the
$n$-qubit Clifford group and outputs a Clifford circuit implementation in time
$O(n^{2})$.

To show that we are guaranteed a state with a certain fidelity, we will need
to use the following anti-concentration inequality.

######  Lemma D.2 (Paley-Zygmund inequality).

If $X\geq 0$ is a random variable with finite variance, and if
$\theta\in[0,1]$ then

$\mathop{\bf Pr\/}\left[X>\theta\mathop{\bf
E\/}\left[x\right]\right]\geq(1-\theta)^{2}\frac{\mathop{\bf
E\/}\left[X\right]^{2}}{\mathop{\bf E\/}\left[X^{2}\right]}.$

Let $X$ be the random variable associated with the fidelity of an arbitrary
quantum state with a random stabilizer state. By bounding the moments of $X$,
we can use the  (Paley-Zygmund inequality). to show that our learner succeeds
with a certain probability.

######  Fact D.3.

For arbitrary $\theta\in[0,1]$, with probability at least
$(1-\theta)^{2}\left(\frac{1}{2}+\frac{1}{2^{n+1}}\right)$, a random
stabilizer state $\ket{\phi}$ will have fidelity at least
$\frac{\theta}{2^{n+1}}$ with an arbitrary quantum state $\ket{\psi}$.

###### Proof Sketch.

Because stabilizer states are a $3$-design [KG15], the values of $\mathop{\bf
E\/}_{\ket{\phi}\sim\mathrm{Stab}}\left[\lvert\braket{\psi}{\phi}\rvert^{2}\right]$
and $\mathop{\bf
E\/}_{\ket{\phi}\sim\mathrm{Stab}}\left[\lvert\braket{\psi}{\phi}\rvert^{4}\right]$
are the same as when $\ket{\phi}$ is replaced by a Haar random state. By
symmetry arguments, we get

$\mathop{\bf
E\/}_{\ket{\phi}\sim\mathrm{Stab}}\left[\lvert\braket{\psi}{\phi}\rvert^{2}\right]=\mathop{\bf
E\/}_{\ket{\phi}\sim\mu_{\mathrm{Haar}}}\left[\lvert\braket{\psi}{\phi}\rvert^{2}\right]=\frac{1}{2^{n}}$

and

$\mathop{\bf
E\/}_{\ket{\phi}\sim\mathrm{Stab}}\left[\lvert\braket{\psi}{\phi}\rvert^{4}\right]=\mathop{\bf
E\/}_{\ket{\phi}\sim\mu_{\mathrm{Haar}}}\left[\lvert\braket{\psi}{\phi}\rvert^{4}\right]=\frac{2}{2^{n}(2^{n}+1)}.$

Since the absolute value of inner products of unit vectors are in the interval
$[0,1]$, by the  (Paley-Zygmund inequality).:

$\mathop{\bf
Pr\/}_{\ket{\phi}\sim\mathrm{Stab}}\left[\lvert\braket{\psi}{\phi}\rvert^{2}\geq\frac{\theta}{2^{n}}\right]\geq(1-\theta)^{2}\frac{1}{4^{n}}\frac{2^{n}(2^{n}+1)}{2}=(1-\theta)^{2}\left(\frac{1}{2}+\frac{1}{2^{n+1}}\right).\qed$

######  Lemma D.4.

For arbitrary $\theta\in[0,1]$, every concept class $\mathcal{C}$ can be

$\left(0,n^{2},1-\frac{\theta}{2^{n+1}},(1-\theta)^{2}\left(\frac{1}{2}+\frac{1}{2^{n+1}}\right)\right)\text{-learned}.$

###### Proof.

In $O(n^{2})$ time, we can sample a random $n$-qubit Clifford circuit using
Lemma D.1 and then apply it to the all-zeros state to get a random stabilizer
state. By outputting this state, D.3 ensures us that the fidelity will be at
least $\frac{\theta}{2^{n}}$ with probability at least
$(1-\theta)^{2}\left(\frac{1}{2}+\frac{1}{2^{n+1}}\right)$. Using the upper
bound in 2.5, the trace distance between the unknown quantum and our random
stabilizer state is at most $\sqrt{1-\frac{\theta}{2^{n}}}\leq
1-\frac{\theta}{2^{n+1}}$ ∎