Random quantum circuits are approximate unitary $t$-designs in depth $O\left(nt^{5+o(1)}\right)$

• URL: http://arxiv.org/abs/2203.16571v3
• Date: Tue, 30 Aug 2022 09:13:53 GMT
• Title: Random quantum circuits are approximate unitary $t$-designs in depth $O\left(nt^{5+o(1)}\right)$
• Authors: Jonas Haferkamp
• Abstract summary: We show that random quantum circuits generate approximate unitary $t$-designs in depth $O(nt5+o(1))$. Our techniques involve Gao's quantum union bound and the unreasonable effectiveness of the Clifford group.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The applications of random quantum circuits range from quantum computing and quantum many-body systems to the physics of black holes. Many of these applications are related to the generation of quantum pseudorandomness: Random quantum circuits are known to approximate unitary $t$-designs. Unitary $t$-designs are probability distributions that mimic Haar randomness up to $t$th moments. In a seminal paper, Brand\~{a}o, Harrow and Horodecki prove that random quantum circuits on qubits in a brickwork architecture of depth $O(n t^{10.5})$ are approximate unitary $t$-designs. In this work, we revisit this argument, which lower bounds the spectral gap of moment operators for local random quantum circuits by $\Omega(n^{-1}t^{-9.5})$. We improve this lower bound to $\Omega(n^{-1}t^{-4-o(1)})$, where the $o(1)$ term goes to $0$ as $t\to\infty$. A direct consequence of this scaling is that random quantum circuits generate approximate unitary $t$-designs in depth $O(nt^{5+o(1)})$. Our techniques involve Gao's quantum union bound and the unreasonable effectiveness of the Clifford group. As an auxiliary result, we prove fast convergence to the Haar measure for random Clifford unitaries interleaved with Haar random single qubit unitaries.

Related papers

• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma. This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles. Even with sublinear barriers, we use Feynman-Kac techniques to lift classical to quantum ones establishing tight lower bound $T_mathrmmix = 2Omega(nalpha)$.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• On verifiable quantum advantage with peaked circuit sampling [9.551919087634522]
  We show that getting $1/textpoly(n)$ peakedness from such circuits requires $tau_p = Omega(tau_r/n)0.19)$ with overwhelming probability. We also give numerical evidence that nontrivial peakedness is possible in this model.
  arXiv  Detail & Related papers  (2024-04-22T18:00:06Z)
• 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)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  We perform classical simulations of the 127-qubit kicked Ising model, which was recently emulated using a quantum circuit with error mitigation. Our approach is based on the projected entangled pair operator (PEPO) in the Heisenberg picture. We develop a Clifford expansion theory to compute exact expectation values and use them to evaluate algorithms.
  arXiv  Detail & Related papers  (2023-08-06T10:24:23Z)
• Unitary k-designs from random number-conserving quantum circuits [0.0]
  Local random circuits scramble efficiently and accordingly have a range of applications in quantum information and quantum dynamics. We show that finite moments cannot distinguish the ensemble that local random circuits generate from the Haar ensemble on the entire group of number-conserving unitaries.
  arXiv  Detail & Related papers  (2023-06-01T18:00:00Z)
• 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 pseudorandom quantum state generators via inflationary quantum gates [3.5072186061740904]
  We propose a mechanism for reaching pseudorandom quantum states, computationally indistinguishable from Haar random, with shallow log-n depth quantum circuits. We prove that IQ-gates cannot be implemented with 2-qubit gates, but can be realized either as a subset of 2-qudit-gates in $U(d2)$ with $dge 3$ and $d$ prime, or as special 3-qubit gates.
  arXiv  Detail & Related papers  (2023-04-19T18:00:01Z)
• 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)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Quantum supremacy and hardness of estimating output probabilities of quantum circuits [0.0]
  We prove under the theoretical complexity of the non-concentration hierarchy that approximating the output probabilities to within $2-Omega(nlogn)$ is hard. We show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including trivial circuit with identity gates.
  arXiv  Detail & Related papers  (2021-02-03T09:20:32Z)
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions [0.0]
  We show that $1D$ random quantum circuits have a spectral gap scaling as $Omega(n-1)$, provided that $t$ is small compared to the local dimension: $t2leq O(q)$. Our second result is an unconditional spectral gap bounded below by $Omega(n-1log-1(n) t-alpha(q))$ for random quantum circuits with all-to-all interactions.
  arXiv  Detail & Related papers  (2020-12-09T19:00:50Z)

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.