Papers
Topics
Authors
Recent
Search
2000 character limit reached

Classically estimating observables of noiseless quantum circuits

Published 3 Sep 2024 in quant-ph, cs.CC, math-ph, and math.MP | (2409.01706v1)

Abstract: We present a classical algorithm for estimating expectation values of arbitrary observables on most quantum circuits across all circuit architectures and depths, including those with all-to-all connectivity. We prove that for any architecture where each circuit layer is equipped with a measure invariant under single-qubit rotations, our algorithm achieves a small error $\varepsilon$ on all circuits except for a small fraction $\delta$. The computational time is polynomial in qubit count and circuit depth for any small constant $\varepsilon, \delta$, and quasi-polynomial for inverse-polynomially small $\varepsilon, \delta$. For non-classically-simulable input states or observables, the expectation values can be estimated by augmenting our algorithm with classical shadows of the relevant state or observable. Our approach leverages a Pauli-path method under Heisenberg evolution. While prior works are limited to noisy quantum circuits, we establish classical simulability in noiseless regimes. Given that most quantum circuits in an architecture exhibit chaotic and locally scrambling behavior, our work demonstrates that estimating observables of such quantum dynamics is classically tractable across all geometries.

Definition Search Book Streamline Icon: https://streamlinehq.com
References (32)
  1. Y.-Y. Shi, L.-M. Duan, and G. Vidal, Classical simulation of quantum many-body systems with a tree tensor network, Phys. Rev. A 74, 022320 (2006).
  2. J. Biamonte and V. Bergholm, Tensor networks in a nutshell, arXiv preprint arXiv:1708.00006  (2017).
  3. J. Hauschild and F. Pollmann, Efficient numerical simulations with tensor networks: Tensor network python (tenpy), SciPost Physics Lecture Notes , 005 (2018).
  4. L. Causer, M. C. Bañuls, and J. P. Garrahan, Optimal sampling of dynamical large deviations in two dimensions via tensor networks, Physical Review Letters 130, 147401 (2023).
  5. I. L. Markov and Y. Shi, Simulating quantum computation by contracting tensor networks, SIAM Journal on Computing 38, 963 (2008).
  6. S. Singh, R. N. C. Pfeifer, and G. Vidal, Tensor network decompositions in the presence of a global symmetry, Phys. Rev. A 82, 050301 (2010).
  7. D. Gottesman, The heisenberg representation of quantum computers, talk at, in International Conference on Group Theoretic Methods in Physics (Citeseer, 1998).
  8. S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Physical Review A 70, 052328 (2004).
  9. S. Bravyi and D. Gosset, Improved classical simulation of quantum circuits dominated by clifford gates, Phys. Rev. Lett. 116, 250501 (2016).
  10. T. Begušić, K. Hejazi, and G. K. Chan, Simulating quantum circuit expectation values by clifford perturbation theory, arXiv preprint arXiv:2306.04797  (2023).
  11. V. Galitski, Quantum-to-classical correspondence and hubbard-stratonovich dynamical systems: A lie-algebraic approach, Phys. Rev. A 84, 012118 (2011).
  12. G. Carleo and M. Troyer, Solving the quantum many-body problem with artificial neural networks, Science 355, 602 (2017).
  13. D. A. Roberts and B. Yoshida, Chaos and complexity by design, Journal of High Energy Physics 2017, 121 (2017).
  14. G. González-García, J. I. Cirac, and R. Trivedi, Pauli path simulations of noisy quantum circuits beyond average case, arXiv preprint arXiv:2407.16068  (2024).
  15. H.-Y. Hu, S. Choi, and Y.-Z. You, Classical shadow tomography with locally scrambled quantum dynamics, Physical Review Research 5, 023027 (2023).
  16. H.-Y. Huang, S. Chen, and J. Preskill, Learning to predict arbitrary quantum processes, arXiv preprint arXiv:2210.14894  (2022).
  17. H.-K. Zhang, S. Liu, and S.-X. Zhang, Absence of barren plateaus in finite local-depth circuits with long-range entanglement, Physical Review Letters 132, 150603 (2024).
  18. J. Napp, Quantifying the barren plateau phenomenon for a model of unstructured variational ansätze, arXiv preprint arXiv:2203.06174  (2022).
  19. A. Letcher, S. Woerner, and C. Zoufal, Tight and efficient gradient bounds for parameterized quantum circuits, arXiv preprint arXiv:2309.12681  (2023).
  20. N. A. Nemkov, E. O. Kiktenko, and A. K. Fedorov, Fourier expansion in variational quantum algorithms, Phys. Rev. A 108, 032406 (2023).
  21. T. Begušić and G. K. Chan, Fast classical simulation of evidence for the utility of quantum computing before fault tolerance, arXiv preprint arXiv:2306.16372  (2023).
  22. H.-Y. Huang, S. Chen, and J. Preskill, Learning to predict arbitrary quantum processes, PRX Quantum 4, 040337 (2023).
  23. E. Gil-Fuster, J. Eisert, and C. Bravo-Prieto, Understanding quantum machine learning also requires rethinking generalization, Nature Communications 15, 2277 (2024).
  24. S. Aaronson and S. Gunn, On the classical hardness of spoofing linear cross-entropy benchmarking, arXiv preprint arXiv:1910.12085 https://doi.org/10.48550/arXiv.1910.12085 (2019).
  25. A. Tanggara, M. Gu, and K. Bharti, Classically spoofing system linear cross entropy score benchmarking, arXiv preprint arXiv:2405.00789 https://doi.org/10.48550/arXiv.2405.00789 (2024).
  26. N. Yu and T.-C. Wei, Learning marginals suffices!, arXiv preprint arXiv:2303.08938 https://doi.org/10.48550/arXiv.2303.08938 (2023).
  27. A. W. Harrow, Approximate orthogonality of permutation operators, with application to quantum information, Letters in Mathematical Physics 114, 1 (2023).
  28. H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measurements, Nature Physics 16, 1050 (2020).
  29. A. S. Nemirovskij and D. B. Yudin, Problem complexity and method efficiency in optimization (1983).
  30. M. R. Jerrum, L. G. Valiant, and V. V. Vazirani, Random generation of combinatorial structures from a uniform distribution, Theoretical computer science 43, 169 (1986).
  31. T. Schuster, J. Haferkamp, and H.-Y. Huang, Random unitaries in extremely low depth, arXiv preprint arXiv:2407.07754  (2024b).
  32. A. A. Mele, Introduction to haar measure tools in quantum information: A beginner’s tutorial, Quantum 8, 1340 (2024).
Citations (6)
View on Semantic Scholar

Summary

  • The paper presents a novel classical algorithm that approximates expectation values on noiseless quantum circuits via low‐weight Pauli propagation to achieve a small mean squared error.
  • The algorithm operates in polynomial time in terms of qubits and circuit depth for constant error probabilities, demonstrating scalable efficiency.
  • Rigorous error analysis shows exponential suppression with increased truncation weight, challenging claims of quantum supremacy in certain simulation tasks.

Classically Estimating Observables of Noiseless Quantum Circuits

The paper "Classically estimating observables of noiseless quantum circuits" presents an exploration into the feasibility of classically estimating the expectation values of observables on quantum circuits. Specifically, it introduces a classical algorithm that can perform this task on a wide range of quantum circuits, including those with arbitrary architectures and depths. The algorithm achieves a computational efficiency that is polynomial in the number of qubits and the circuit depth for small constant error and failure probabilities, and quasi-polynomial for inverse-polynomially small parameters.

Key Results

  1. Algorithm Design: The core contribution is a classical simulation algorithm that approximates the expectation values of observables on noiseless quantum circuits using low-weight Pauli propagation. This approach involves back-propagating each Pauli operator in the observable through the circuit and truncating the high-weight Pauli terms at each layer. The resulting estimator is shown to provide a small mean squared error (MSE) on average.
  2. Error Analysis: The paper rigorously establishes an upper bound on the MSE of the proposed algorithm. For any locally scrambling circuit ensemble, it shows that the average error is exponentially suppressed in the truncation weight. Specifically, for a truncation weight kk, the MSE is bounded by (23)k+1⋅OPauli,22(\frac{2}{3})^{k+1} \cdot {O}_{\mathrm{Pauli},2}^2, where OPauli,2{O}_{\mathrm{Pauli},2} is the normalized Hilbert-Schmidt norm of the observable. This result implies that for sufficiently large kk, the classical algorithm can achieve a high precision with a high probability.
  3. Computational Complexity: The computational time required by the algorithm is polynomial in the number of qubits nn and the circuit depth LL for constant error and failure probabilities. For small constant ϵ\epsilon and δ\delta, the complexity is O(LnO(log⁡(ϵ−1δ−1)))\mathcal{O}(Ln^{\mathcal{O}(\log (\epsilon^{-1} \delta^{-1}))}). When the circuit has geometric locality, and the depth is L=O(log⁡(n))L = \mathcal{O}(\log(n)), the complexity further tightens to O(LO(log⁡(ϵ−1δ−1)))\mathcal{O}(L^{\mathcal{O}(\log (\epsilon^{-1} \delta^{-1}))}).
  4. Extending to Quantum-Enhanced Classical Simulation: When the initial state or the observable is not classically simulable, the research introduces a hybrid approach leveraging classical shadows to estimate the state or observable. The sample complexity for this setup is also shown to be favorable, being polynomial in nn for constant ϵ\epsilon and δ\delta.

Practical and Theoretical Implications

  • Variational Quantum Algorithms (VQAs): The results are particularly pertinent for VQAs, where estimating expectation values plays a crucial role. The ability to classically simulate these quantities efficiently under certain conditions raises questions about the potential quantum advantage offered by these algorithms.
  • Emerging Quantum Architectures: Given the broad applicability of locally scrambling circuits, these findings suggest that many modern quantum architectures, including those used in noisy intermediate-scale quantum (NISQ) devices, might be more classically tractable than previously thought.
  • Challenges in Quantum Supremacy: The research offers insights into the limitations of achieving quantum supremacy, particularly for tasks that involve estimating expectation values. The classical algorithms presented might pose significant competition to quantum algorithms intended to demonstrate supremacy on relevant benchmarks.

Future Developments in AI and Quantum Computing

Looking forward, the approach and results presented in this paper could stimulate several advancements:

  1. Improved Classical Simulation Techniques: Further refinements and extensions of the Pauli propagation method might enable even more efficient classical algorithms for simulating broader classes of quantum circuits.
  2. Hybrid Quantum-Classical Systems: The demonstrated efficacy of combining classical algorithms with quantum data collection (via classical shadows) suggests robust frameworks for hybrid quantum-classical systems, which might be pivotal during the NISQ era.
  3. Reevaluation of Quantum Advantage: The findings could prompt a reevaluation of the domains where quantum advantage is truly achievable. This might influence the direction of both theoretical research and practical implementations in quantum computing.
  4. Algorithmic Innovations: The integration of classical simulation techniques with quantum error mitigation strategies could lead to innovative algorithms for more accurate and efficient quantum computations.

In conclusion, the paper delivers a significant contribution to the understanding and capability of classical algorithms in estimating observables of quantum circuits. By showing that many circuits can indeed be classically simulated with high precision, it constructs a bridge between classical and quantum computational paradigms, advancing the frontier of efficient quantum simulation techniques.

Paper to Video (Beta)

No one has generated a video about this paper yet.

Sign Up to Generate All Videos Subscribe on YouTube

Whiteboard

No one has generated a whiteboard explanation for this paper yet.

Sign Up to Generate

Open Problems

We haven't generated a list of open problems mentioned in this paper yet.

Generate Now

Collections

Sign up for free to add this paper to one or more collections.

Sign Up

Tweets

Sign up for free to view the 1 tweet with 67 likes about this paper.

Sign Up for Free