Classical Sampling of Random Quantum Circuits with Bounded Fidelity

• URL: http://arxiv.org/abs/2112.15083v1
• Date: Thu, 30 Dec 2021 14:51:39 GMT
• Title: Classical Sampling of Random Quantum Circuits with Bounded Fidelity
• Authors: Gleb Kalachev, Pavel Panteleev, PengFei Zhou, Man-Hong Yung
• Abstract summary: We present a classical sampling algorithm for producing the probability distribution of any given random quantum circuit. We classically produced 1 million samples with the fidelity bounded by 0.2%, based on the 20-cycle circuit of the Sycamore 53-qubit quantum chip. We estimate that for the Zuchongzhi 56-qubit 20-cycle circuit one can produce 1M samples with fidelity 0.066% using the Selene supercomputer.
• Score: 0.5735035463793007
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random circuit sampling has become a popular means for demonstrating the superiority of quantum computers over classical supercomputers. While quantum chips are evolving rapidly, classical sampling algorithms are also getting better and better. The major challenge is to generate bitstrings exhibiting an XEB fidelity above that of the quantum chips. Here we present a classical sampling algorithm for producing the probability distribution of any given random quantum circuit, where the fidelity can be rigorously bounded. Specifically, our algorithm performs rejection sampling after the introduced very recently multi-tensor contraction algorithm. We show that the fidelity can be controlled by partially contracting the dominant paths in the tensor network and by adjusting the number of batches used in the rejection sampling. As a demonstration, we classically produced 1 million samples with the fidelity bounded by 0.2%, based on the 20-cycle circuit of the Sycamore 53-qubit quantum chip. Though this task was initially estimated to take 10,000 years on the Summit supercomputer, it took about 14.5 days using our algorithm on a relatively small cluster with 32 GPUs (Tesla V100 16GB). Furthermore, we estimate that for the Zuchongzhi 56-qubit 20-cycle circuit one can produce 1M samples with fidelity 0.066% using the Selene supercomputer with 4480 GPUs (Tesla A100 80GB) in about 4 days.

Related papers

• Leapfrogging Sycamore: Harnessing 1432 GPUs for 7$\times$ Faster Quantum Random Circuit Sampling [40.83618005962484]
  Random quantum circuit sampling serves as a benchmark to demonstrate quantum computational advantage. Recent progress in classical algorithms has significantly reduced the classical simulation time. Our work provides the first unambiguous experimental evidence to refute textitSycamore's claim of quantum advantage.
  arXiv  Detail & Related papers  (2024-06-27T05:01:47Z)
• 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)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• 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)
• Solving the sampling problem of the Sycamore quantum circuits [6.0604034858265345]
  We study the problem of generating independent samples from the output distribution of Google's Sycamore quantum circuits with a target fidelity. We propose a new method to classically solve this problem by contracting the corresponding tensor network just once. For the Sycamore quantum supremacy circuit with $53$ qubits and $20$ cycles, we have generated one million uncorrelated bitstrings.
  arXiv  Detail & Related papers  (2021-11-04T17:13:09Z)
• Quantum Computational Advantage via 60-Qubit 24-Cycle Random Circuit Sampling [33.18018507595303]
  The readout fidelity of textitZuchongzhi 2.1 is considerably improved to an average of 97.74%. The more powerful quantum processor enables us to achieve larger-scale random quantum circuit sampling.
  arXiv  Detail & Related papers  (2021-09-08T08:34:28Z)
• Multi-Tensor Contraction for XEB Verification of Quantum Circuits [0.0]
  We present a multi-tensor contraction algorithm for speeding up the calculations of XEB for quantum circuits. If the algorithm was implemented on the Summit supercomputer, we estimate that for the supremacy (20 cycles) circuits, it would only cost 7.5 days.
  arXiv  Detail & Related papers  (2021-08-12T11:15:49Z)
• The Boundary for Quantum Advantage in Gaussian Boson Sampling [44.62475518267084]
  State-of-the-art quantum photonics experiments would require 600 million years to simulate using the best pre-existing classical algorithms. We present substantially faster classical GBS simulation methods, including speed and accuracy improvements. This reduces the run-time of simulating state-of-the-art GBS experiments to several months -- a nine orders of magnitude improvement over previous estimates.
  arXiv  Detail & Related papers  (2021-08-03T16:49:40Z)
• Simulating the Sycamore quantum supremacy circuits [7.15956388718641]
  We propose a general tensor network method for simulating quantum circuits. As an application, we study the sampling problem of Google's Sycamore circuits.
  arXiv  Detail & Related papers  (2021-03-04T14:55:15Z)
• 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)

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.