Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits

• URL: http://arxiv.org/abs/2407.19561v1
• Date: Sun, 28 Jul 2024 19:10:46 GMT
• Title: Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
• Authors: Bill Fefferman, Soumik Ghosh, Wei Zhan,
• Abstract summary: We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure. We show that the scrambling speed of a random quantum circuit is lower bounded.
• Score: 12.786353781073242
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure, by showing that the probability of a polynomial in the entries of a random unitary falling into an $\varepsilon$ range is at most a polynomial in $\varepsilon$. Using it, we show that the scrambling speed of a random quantum circuit is lower bounded: Namely, every input qubit has an influence that is at least exponentially small in depth, on any output qubit touched by its lightcone. We give three applications of this new scrambling speed lower bound that apply to random quantum circuits with Haar random gates: $\bullet$ An optimal $\Omega(\log \varepsilon^{-1})$ depth lower bound for $\varepsilon$-approximate unitary designs; $\bullet$ A polynomial-time quantum algorithm that computes the depth of a bounded-depth circuit, given oracle access to the circuit; $\bullet$ A polynomial-time algorithm that learns log-depth circuits up to polynomially small diamond distance, given oracle access to the circuit. The first depth lower bound works against any architecture. The latter two algorithms apply to architectures defined over any geometric dimension, and can be generalized to a wide class of architectures with good lightcone properties.

Related papers

• Learning quantum states prepared by shallow circuits in polynomial time [1.127500169412367]
  We learn a constant depth quantum circuit that prepares $vertpsirangle$ on a finite-dimensional lattice. The algorithm extends to the case when the depth of $U$ is $mathrmpolylog(n)$, with a quasi-polynomial run-time. As an application, we give an efficient algorithm to test whether an unknown quantum state on a lattice has low or high quantum circuit complexity.
  arXiv  Detail & Related papers  (2024-10-31T04:12:49Z)
• Classically estimating observables of noiseless quantum circuits [36.688706661620905]
  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.
  arXiv  Detail & Related papers  (2024-09-03T08:44:33Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose arbitrary exponentials into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions. We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Random unitaries in extremely low depth [0.8680580889074451]
  We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over $n$ qubits in $log n$ depth. In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in $textpoly log n $ depth, and in all-to-all-connected circuits in $textpoly log log n $ depth.
  arXiv  Detail & Related papers  (2024-07-10T15:27:48Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
  Current quantum algorithms for solving CFD problems use a single quantum circuit and, in some cases, lattice-based methods. We introduce the a novel multiple circuits algorithm that makes use of a quantum lattice Boltzmann method (QLBM) The problem is cast as a stream function--vorticity formulation of the 2D Navier-Stokes equations and verified and tested on a 2D lid-driven cavity flow.
  arXiv  Detail & Related papers  (2024-01-20T15:32:01Z)
• 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)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
  We describe an algorithm with quasipolynomial runtime $nO(logn)$ that samples from the output distribution of a peaked constant-depth circuit. Our algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error.
  arXiv  Detail & Related papers  (2023-09-15T14:01:13Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• Fast quantum circuit cutting with randomized measurements [0.0]
  We propose a new method to extend the size of a quantum computation beyond the number of physical qubits available on a single device. This is accomplished by randomly inserting measure-and-prepare channels to express the output state of a large circuit as a separable state across distinct devices.
  arXiv  Detail & Related papers  (2022-07-29T15:13:04Z)

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.