Validating quantum-supremacy experiments with exact and fast tensor network contraction

• URL: http://arxiv.org/abs/2212.04749v2
• Date: Wed, 17 Jan 2024 01:36:14 GMT
• Title: Validating quantum-supremacy experiments with exact and fast tensor network contraction
• Authors: Yong Liu, Yaojian Chen, Chu Guo, Jiawei Song, Xinmin Shi, Lin Gan, Wenzhao Wu, Wei Wu, Haohuan Fu, Xin Liu, Dexun Chen, Zhifeng Zhao, Guangwen Yang, Jiangang Gao
• Abstract summary: 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.
• Score: 21.99404639937004
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The quantum supremacy experiment, such as Google Sycamore [Nature \textbf{574}, 505 (2019)], poses great challenge for classical verification due to the exponentially-increasing compute cost. Using a new-generation Sunway supercomputer within $8.5$ days, we provide a direct verification by computing three million exact amplitudes for the experimentally generated bitstrings, obtaining an XEB fidelity of $0.191\%$ (the estimated value is $0.224\%$). The leap of simulation capability is built on a multiple-amplitude tensor network contraction algorithm which systematically exploits the ``classical advantage" (the inherent ``store-and-compute" operation mode of von Neumann machines) of current supercomputers, and a fused tensor network contraction algorithm which drastically increases the compute efficiency on heterogeneous architectures. Our method has a far-reaching impact in solving quantum many-body problems, statistical problems as well as combinatorial optimization problems.

Related papers

• Fast classical simulation of Harvard/QuEra IQP circuits [4.415661493715816]
  A quantum advantage is achieved once a certain computational capability of a quantum computer is so complex that it can no longer be reproduced by classical means. We report a classical simulation algorithm that takes only $0.00947$ seconds to compute an amplitude for a $48$-qubit computation. Our algorithm is furthermore not subject to a significant decline in performance due to the additional CNOT layers.
  arXiv  Detail & Related papers  (2024-02-05T17:22:41Z)
• 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)
• 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)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• 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)
• Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer [8.314468031947694]
  We develop a high-performance tensor-based simulator for random quantum circuits(RQCs) on the new Sunway supercomputer. Our major innovations include: (1) a near-optimal slicing scheme, and a path-optimization strategy that considers both complexity and compute density; (2) a three-level parallelization scheme that scales to about 42 million cores; and (3) a fused permutation and multiplication design that improves the compute efficiency for a wide range of tensor contraction scenarios.
  arXiv  Detail & Related papers  (2021-10-27T15:14:59Z)
• A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
  We show that conditions amenable to classical trainability via gradient descent coincide with those necessary for efficiently solving quantum linear systems. We numerically demonstrate that the MNIST image dataset satisfies such conditions. We provide empirical evidence for $O(log n)$ training of a convolutional neural network with pooling.
  arXiv  Detail & Related papers  (2021-07-19T23:41:03Z)
• 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)
• Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor Network States Algorithm [0.0]
  Algorithm is up to $2$ orders of magnitudes faster than Sch$ddottexto$dinger-Feynman algorithm. We simulate larger random quantum circuits up to $104$ qubits, showing that this algorithm is an ideal tool to verify relatively shallow quantum circuits on near-term quantum computers.
  arXiv  Detail & Related papers  (2020-11-05T02:20:56Z)

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.