The hardness of quantum spin dynamics
- URL: http://arxiv.org/abs/2312.07658v1
- Date: Tue, 12 Dec 2023 19:00:03 GMT
- Title: The hardness of quantum spin dynamics
- Authors: Chae-Yeun Park, Pablo A. M. Casares, Juan Miguel Arrazola, and Joonsuk
Huh
- Abstract summary: We show that sampling from the output distribution generated by a wide class of quantum spin Hamiltonians is a hard problem for classical computers.
We estimate that an instance involving about 200 spins will be challenging for classical devices but feasible for intermediate-scale quantum computers with fault-tolerant qubits.
- Score: 1.1999555634662633
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent experiments demonstrated quantum computational advantage in random
circuit sampling and Gaussian boson sampling. However, it is unclear whether
these experiments can lead to practical applications even after considerable
research effort. On the other hand, simulating the quantum coherent dynamics of
interacting spins has been considered as a potential first useful application
of quantum computers, providing a possible quantum advantage. Despite evidence
that simulating the dynamics of hundreds of interacting spins is challenging
for classical computers, concrete proof is yet to emerge. We address this
problem by proving that sampling from the output distribution generated by a
wide class of quantum spin Hamiltonians is a hard problem for classical
computers. Our proof is based on the Taylor series of the output probability,
which contains the permanent of a matrix as a coefficient when bipartite spin
interactions are considered. We devise a classical algorithm that extracts the
coefficient using an oracle estimating the output probability. Since
calculating the permanent is #P-hard, such an oracle does not exist unless the
polynomial hierarchy collapses. With an anticoncentration conjecture, the
hardness of the sampling task is also proven. Based on our proof, we estimate
that an instance involving about 200 spins will be challenging for classical
devices but feasible for intermediate-scale quantum computers with
fault-tolerant qubits.
Related papers
- Computational supremacy in quantum simulation [22.596358764113624]
We show that superconducting quantum annealing processors can generate samples in close agreement with solutions of the Schr"odinger equation.
We conclude that no known approach can achieve the same accuracy as the quantum annealer within a reasonable timeframe.
arXiv Detail & Related papers (2024-03-01T19:00:04Z) - Quantum data learning for quantum simulations in high-energy physics [55.41644538483948]
We explore the applicability of quantum-data learning to practical problems in high-energy physics.
We make use of ansatz based on quantum convolutional neural networks and numerically show that it is capable of recognizing quantum phases of ground states.
The observation of non-trivial learning properties demonstrated in these benchmarks will motivate further exploration of the quantum-data learning architecture in high-energy physics.
arXiv Detail & Related papers (2023-06-29T18:00:01Z) - Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
We present an approach where the quantum computation is supplemented by a classical result.
Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative.
In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
arXiv Detail & Related papers (2022-09-12T15:47:44Z) - Noisy Quantum Kernel Machines [58.09028887465797]
An emerging class of quantum learning machines is that based on the paradigm of quantum kernels.
We study how dissipation and decoherence affect their performance.
We show that decoherence and dissipation can be seen as an implicit regularization for the quantum kernel machines.
arXiv Detail & Related papers (2022-04-26T09:52:02Z) - On the effects of biased quantum random numbers on the initialization of
artificial neural networks [3.0736361776703562]
A common property of quantum computers is that they can exhibit instances of true randomness as opposed to pseudo-randomness.
Recent results suggest that benefits can indeed be achieved from the use of quantum random numbers.
arXiv Detail & Related papers (2021-08-30T15:50:07Z) - An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian
Simulation [55.41644538483948]
Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates.
We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions.
The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
arXiv Detail & Related papers (2021-08-06T19:38:03Z) - Depth-efficient proofs of quantumness [77.34726150561087]
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover.
In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
arXiv Detail & Related papers (2021-07-05T17:45:41Z) - Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor.
We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
arXiv Detail & Related papers (2021-01-21T22:18:49Z) - Sampling and the complexity of nature [0.0]
I investigate the complexity-theoretic and physical foundations of quantum sampling algorithms.
I shed light on how and under which conditions quantum sampling devices can be tested or verified.
An overarching theme of the thesis is the quantum sign problem which arises due to destructive interference between paths.
arXiv Detail & Related papers (2020-12-14T19:35:27Z) - Characterizing quantum correlations in spin chains [0.0]
We show that a single element of the density matrix carries the answer to how quantum is a chain of spins.
This method can be used to tailor and witness highly non-classical effects in many-body systems.
As a proof of principle, we investigate the extend of non-locality and entanglement in ground states and thermal states of experimentally accessible spin chains.
arXiv Detail & Related papers (2020-05-19T17:25:37Z) - Quantum reservoir computing with a single nonlinear oscillator [0.0]
We propose continuous variable quantum reservoir computing in a single nonlinear oscillator.
We demonstrate quantum-classical performance improvement, and identify its likely source: the nonlinearity of quantum measurement.
We study how the performance of our quantum reservoir depends on Hilbert space dimension, how it is impacted by injected noise, and briefly comment on its experimental implementation.
arXiv Detail & Related papers (2020-04-30T17:14:34Z)
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.