On verifiable quantum advantage with peaked circuit sampling

• URL: http://arxiv.org/abs/2404.14493v2
• Date: Tue, 21 May 2024 17:48:41 GMT
• Title: On verifiable quantum advantage with peaked circuit sampling
• Authors: Scott Aaronson, Yuxuan Zhang,
• Abstract summary: 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.
• Score: 9.551919087634522
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Over a decade after its proposal, the idea of using quantum computers to sample hard distributions has remained a key path to demonstrating quantum advantage. Yet a severe drawback remains: verification seems to require classical computation exponential in the system size, $n$. As an attempt to overcome this difficulty, we propose a new candidate for quantum advantage experiments with otherwise random "peaked circuits", i.e., quantum circuits whose outputs have high concentrations on a computational basis state. Naturally, the heavy output string can be used for classical verification. In this work, we analytically and numerically study an explicit model of peaked circuits, in which $\tau_r$ layers of uniformly random gates are augmented by $\tau_p$ layers of gates that are optimized to maximize peakedness. We show that getting $1/\text{poly}(n)$ peakedness from such circuits requires $\tau_{p} = \Omega((\tau_r/n)^{0.19})$ with overwhelming probability. However, we also give numerical evidence that nontrivial peakedness is possible in this model -- decaying exponentially with the number of qubits, but more than can be explained by any approximation where the output of a random quantum circuit is treated as a Haar-random state. This suggests that these peaked circuits have the potential for future verifiable quantum advantage experiments. Our work raises numerous open questions about random peaked circuits, including how to generate them efficiently, and whether they can be distinguished from fully random circuits in classical polynomial time.

Related papers

• Maximising Quantum-Computing Expressive Power through Randomised Circuits [4.604271571912073]
  variational quantum algorithms (VQAs) have emerged as a promising avenue to obtain quantum advantage. We numerically demonstrate a novel approach for VQAs, utilizing randomised quantum circuits to generate the variational wavefunction. This random-circuit approach presents a trade-off between the expressive power of the variational wavefunction and time cost.
  arXiv  Detail & Related papers  (2023-12-04T15:04:42Z)
• 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)
• 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)
• Estimating the randomness of quantum circuit ensembles up to 50 qubits [9.775777593425452]
  We show that the ability of random circuits to approximate any random unitaries has consequences on their complexity, expressibility, and trainability. Our work shows that large-scale tensor network simulations could provide important hints toward open problems in quantum information science.
  arXiv  Detail & Related papers  (2022-05-19T23:43:15Z)
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(nt^{5+o(1)}\right)$ [0.0]
  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.
  arXiv  Detail & Related papers  (2022-03-30T18:02:08Z)
• 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)
• Learnability of the output distributions of local quantum circuits [53.17490581210575]
  We investigate, within two different oracle models, the learnability of quantum circuit Born machines. We first show a negative result, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable. We show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable.
  arXiv  Detail & Related papers  (2021-10-11T18:00:20Z)
• 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)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.