Fetching the paper…
Reading the bibliography…
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 $\Omega(n)$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states, an exponential improvement over the previously known bound.
The Uncertainty Relations in Quantum Mechanics. Zum Heisenbergschen Unschärfeprinzip
Erwin Schrödinger · 1930
Earlier work this paper cites.
A Theory of the Learnable
Leslie G. Valiant · 1972
Earlier work this paper cites.
Another 𝖭𝖯 \mathsf{NP} -complete partition problem and the complexity of computing short vectors in lattices
Peter van Emde Boas · 1981
Earlier work this paper cites.
Toward efficient agnostic learning
Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie · 1992
Earlier work this paper cites.
Matching Pursuit with Time-Frequency Dictionaries
Stéphane Mallat and Zhifeng Zhang · 1994
Earlier work this paper cites.
Scheme for reducing decoherence in quantum computer memory
Peter W. Shor · 1995
Earlier work this paper cites.
Good quantum error-correcting codes exist
A. R. Calderbank and Peter W. Shor · 1996
Earlier work this paper cites.
Robust Characterizations of Polynomials with Applications to Program Testing
Ronitt Rubinfeld and Madhu Sudan · 1996
Earlier work this paper cites.
The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations
Sanjeev Arora, László Babai, Jacques Stern, and Z Sweedyk · 1997
Earlier work this paper cites.
Stabilizer Codes and Quantum Error Correction
Daniel Gottesman · 1997
Earlier work this paper cites.
Approximating-CVP to within almost-polynomial factors is 𝖭𝖯 \mathsf{NP} -hard
Irit Dinur, Guy Kindler, and Shmuel Safra · 1998
Earlier work this paper cites.
Property Testing and Its Connection to Learning and Approximation
Oded Goldreich, Shari Goldwasser, and Dana Ron · 1998
Earlier work this paper cites.
Quantum computing via measurements only, 2000
Robert Raussendorf and Hans J. Briegel · 2000
Earlier work this paper cites.
Quantum Computation and Quantum Information, 2002
Michael A. Nielsen and Isaac Chuang · 2002
Earlier work this paper cites.
Improved Simulation of Stabilizer Circuits
Scott Aaronson and Daniel Gottesman · 2004
Earlier work this paper cites.
Universal quantum computation with ideal Clifford gates and noisy ancillas
Sergey Bravyi and Alexei Kitaev · 2005
Earlier work this paper cites.
Hudson’s theorem for finite-dimensional quantum systems
David Gross · 2006
Earlier work this paper cites.
Tolerant property testing and distance approximation
Michal Parnas, Dana Ron, and Ronitt Rubinfeld · 2006
Earlier work this paper cites.
The worst-case time complexity for generating all maximal cliques and computational experiments
Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi · 2006
Earlier work this paper cites.
The learnability of quantum states
Scott Aaronson · 2007
Earlier work this paper cites.
About Heisenberg Uncertainty Relation (by E. Schrodinger), 2008
A. Angelow and M. C. Batoni · 2008
Earlier work this paper cites.
Identifying Stabilizer States, 2008
Scott Aaronson and Daniel Gottesman · 2008
Earlier work this paper cites.
Cryptography with Constant Computational Overhead
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai · 2008
Earlier work this paper cites.
Randomized benchmarking of quantum gates
E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland · 2008
Cited alongside, same era.
Efficient quantum state tomography
Marcus Cramer, Martin B. Plenio, Steven T. Flammia, Rolando Somma, David Gross, Stephen D. Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu · 2010
Cited alongside, same era.
Improved Strong Simulation of Universal Quantum Circuits, 2022
Lucas Kocia · 2012
Cited alongside, same era.
Analysis of Boolean Functions
Ryan O’Donnell · 2014
Cited alongside, same era.
The resource theory of stabilizer quantum computation
Victor Veitch, S A Hamed Mousavian, Daniel Gottesman, and Joseph Emerson · 2014
Cited alongside, same era.
Qubit stabilizer states are complex projective 3-designs, 2015
Quantum Pseudoentanglement, 2022
Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou · 2022
Later among the works it cites.
Cryptography from Pseudorandom Quantum States
Prabhanjan Ananth, Luowen Qian, and Henry Yuen · 2022
Later among the works it cites.
The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity
Zhiyuan Fan, Jiatu Li, and Tianqi Yang · 2022
Later among the works it cites.
On the Hardness of PAC-learning Stabilizer States with Noise
Aravind Gollakota and Daniel Liang · 2022
Later among the works it cites.
Learning Quantum Circuits of Some T T Gates
Ching-Yi Lai and Hao-Chung Cheng · 2022
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Richard Kueng and David Gross · 2015
Cited alongside, same era.
Trading Classical and Quantum Computational Resources
Sergey Bravyi, Graeme Smith, and John A. Smolin · 2016
Cited alongside, same era.
The Clifford Group Forms a Unitary 3-Design
Zak Webb · 2016
Cited alongside, same era.
Learning stabilizer states by Bell sampling, 2017
Ashley Montanaro · 2017
Cited alongside, same era.
Multiqubit Clifford groups are unitary 3-designs
Huangjun Zhu · 2017
Cited alongside, same era.
Shadow Tomography of Quantum States
Scott Aaronson · 2018
Cited alongside, same era.
Optimality in Stabilizer Testing
Raja Oktovin Parhasian Damanik · 2018
Cited alongside, same era.
Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd, and Alioscia Hamma · 2022
Later among the works it cites.
Quantum Commitments And Signatures Without One-Way Functions
Tomoyuki Morimae and Takashi Yamakawa · 2022
Later among the works it cites.
A survey on the complexity of learning quantum states, 2023
Anurag Anshu and Srinivasan Arunachalam · 2023
Closest in time.
Optimal Algorithms for Learning Quantum Phase States
Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder · 2023
Closest in time.
Efficient Tomography of Non-Interacting-Fermion States
Scott Aaronson and Sabee Grewal · 2023
Closest in time.
Black-Hole Radiation Decoding Is Quantum Cryptography
Zvika Brakerski · 2023
Closest in time.
Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates, 2023
Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang · 2023
Closest in time.
Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang · 2023
Closest in time.
Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang · 2023
Closest in time.
A little magic means a lot, 2023
Andi Gu, Lorenzo Leone, Soumik Ghosh, Jens Eisert, Susanne Yelin, and Yihui Quek · 2023
Closest in time.
Bell sampling from quantum circuits, 2023
Dominik Hangleiter and Michael J. Gullans · 2023
Closest in time.
One T T Gate Makes Distribution Learning Hard
Marcel Hinsche, Marios Ioannou, Alexander Nietner, Jonas Haferkamp, Yihui Quek, Dominik Hangleiter, Jean-Pierre Seifert, Jens Eisert, and Ryan Sweke · 2023
Closest in time.
Scalable Measures of Magic Resource for Quantum Computers
Tobias Haug and M. S. Kim · 2023
Closest in time.
From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments
Minki Hhan, Tomoyuki Morimae, and Takashi Yamakawa · 2023
Closest in time.
Quantum Cryptography in Algorithmica
William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal · 2023
Closest in time.
Learning t-doped stabilizer states, 2023
Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma · 2023
Closest in time.
Lower bounds on the non-Clifford resources for quantum computations
Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov · 2058
Closest in time.