Solving the sampling problem of the Sycamore quantum circuits

• URL: http://arxiv.org/abs/2111.03011v2
• Date: Sun, 28 Aug 2022 01:30:21 GMT
• Title: Solving the sampling problem of the Sycamore quantum circuits
• Authors: Feng Pan, Keyang Chen, Pan Zhang
• Abstract summary: 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.
• Score: 6.0604034858265345
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of generating independent samples from the output distribution of Google's Sycamore quantum circuits with a target fidelity, which is believed to be beyond the reach of classical supercomputers and has been used to demonstrate quantum supremacy. We propose a new method to classically solve this problem by contracting the corresponding tensor network just once, and is massively more efficient than existing methods in obtaining a large number of uncorrelated samples with a target fidelity. For the Sycamore quantum supremacy circuit with $53$ qubits and $20$ cycles, we have generated one million uncorrelated bitstrings $\{\mathbf s\}$ which are sampled from a distribution $\hat P(\mathbf s)=|\hat \psi(\mathbf s)|^2$, where the approximate state $\hat \psi$ has fidelity $F\approx 0.0037$. The whole computation has cost about $15$ hours on a computational cluster with $512$ GPUs. The obtained one million samples, the contraction code and contraction order is made public. If our algorithm could be implemented with high efficiency on a modern supercomputer with ExaFLOPS performance, we estimate that ideally, the simulation would cost a few dozens of seconds, which is faster than Google's quantum hardware.

Related papers

• 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)
• End-to-end complexity for simulating the Schwinger model on quantum computers [0.6449786007855248]
  We propose an efficient implementation of block-encoding of the Schwinger model Hamiltonian. As an end-to-end application, we compute the vacuum persistence amplitude. Our results provide insights into predictions about the performance of quantum computers in the FTQC era.
  arXiv  Detail & Related papers  (2023-11-29T06:36:11Z)
• 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)
• 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)
• Classically Simulating Quantum Supremacy IQP Circuits trough a Random Graph Approach [0.0]
  A good candidate for demonstrating quantum supremacy with random circuit sampling is to use emphIQP circuits. We introduce improved techniques for classically simulating random IQP circuits. We estimate that 70-qubit circuits are within reach for a large computing cluster.
  arXiv  Detail & Related papers  (2022-12-16T17:38:42Z)
• Validating quantum-supremacy experiments with exact and fast tensor network contraction [21.99404639937004]
  We provide a direct verification by computing three million exact amplitudes for the experimentally generated bitstrings. The leap of simulation capability is built on a multiple-amplitude tensor network contraction algorithm. Our method has a far-reaching impact in solving quantum many-body problems, statistical problems as well as optimization problems.
  arXiv  Detail & Related papers  (2022-12-09T10:01:02Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45: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)
• Redefining the Quantum Supremacy Baseline With a New Generation Sunway Supercomputer [17.816108993297664]
  A major milestone in the era of noisy intermediate scale quantum computers is textitquantum supremacy [Nature textbf574, 505] claimed on the Sycamore quantum processor of $53$ qubits. This record has been renewed with two recent experiments on the Zuchongzhi $2.0$ ($56$ qubits) and Zuchongzhi $2.1$ ($60$ qubits) quantum processors. Here we report the full-scale simulations of these problems on new generation Sunway supercomputer, based on a customized tensor network contraction algorithm.
  arXiv  Detail & Related papers  (2021-11-01T16:28:51Z)
• What limits the simulation of quantum computers? [5.22339562024796]
  We demonstrate that real quantum computers can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer. Our algorithms compress the representations of quantum wavefunctions using matrix product states (MPS), which capture states with low to moderate entanglement very accurately. For a two dimensional array of $N=54$ qubits and a circuit with Control-Z gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours.
  arXiv  Detail & Related papers  (2020-02-18T17:00:39Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

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.