Classically estimating observables of noiseless quantum circuits

• URL: http://arxiv.org/abs/2409.01706v1
• Date: Tue, 3 Sep 2024 08:44:33 GMT
• Title: Classically estimating observables of noiseless quantum circuits
• Authors: Armando Angrisani, Alexander Schmidhuber, Manuel S. Rudolph, M. Cerezo, Zoë Holmes, Hsin-Yuan Huang,
• Abstract summary: We present a classical algorithm for estimating expectation values of arbitrary observables on most quantum circuits. 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.
• Score: 36.688706661620905
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT circuits are a common building block of general quantum circuits. This article presents state-of-the-art algorithms for optimizing the number of CNOT gates. A simulated evaluation shows that the suggested is almost always beneficial and reduces the number of CNOT gates by up to 10%.
  arXiv  Detail & Related papers  (2024-08-07T19:51:22Z)
• A polynomial-time classical algorithm for noisy quantum circuits [1.2708457954150887]
  We provide a-time classical algorithm for noisy quantum circuits. Our approach is based upon the intuition that noise exponentially damps non-local correlations. For constant noise rates, any quantum circuit for which error mitigation is efficient on most input states, is also classically simulable on most input states.
  arXiv  Detail & Related papers  (2024-07-17T17:48:39Z)
• Noise-induced shallow circuits and absence of barren plateaus [2.5295633594332334]
  We show that any noise truncates' most quantum circuits to effectively logarithmic depth. We then prove that quantum circuits under any non-unital noise exhibit lack of barren plateaus for cost functions composed of local observables.
  arXiv  Detail & Related papers  (2024-03-20T19:00:49Z)
• Learning shallow quantum circuits [7.411898489476803]
  We present an algorithm for learning the description of any unknown $n$-qubit shallow quantum circuit $U$. We also provide a classical algorithm for learning the description of any unknown $n$-qubit state $lvert psi rangle$. Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions.
  arXiv  Detail & Related papers  (2024-01-18T16:05:00Z)
• A noise-limiting quantum algorithm using mid-circuit measurements for dynamical correlations at infinite temperature [0.0]
  We introduce a quantum channel built out of mid-circuit measurements and feed-forward. In the presence of a depolarizing channel it still displays a meaningful, non-zero signal in the large depth limit. We showcase the noise resilience of this quantum channel on Quantinuum's H1-1 ion-trap quantum computer.
  arXiv  Detail & Related papers  (2024-01-04T11:25:04Z)
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach [1.806183113759115]
  Large-scale variational quantum algorithms are widely recognized as a potential pathway to achieve quantum advantages. We present a novel $gammaPPP method based on the integral path of observables back-propagation on paths. We conduct classical simulations of IBM's zeronoised experimental results on the 127-qubit Eagle processor.
  arXiv  Detail & Related papers  (2023-06-09T10:42:07Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Gaussian initializations help deep variational quantum circuits escape from the barren plateau [87.04438831673063]
  Variational quantum circuits have been widely employed in quantum simulation and quantum machine learning in recent years. However, quantum circuits with random structures have poor trainability due to the exponentially vanishing gradient with respect to the circuit depth and the qubit number. This result leads to a general belief that deep quantum circuits will not be feasible for practical tasks.
  arXiv  Detail & Related papers  (2022-03-17T15:06:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.