Sampling and the complexity of nature

• URL: http://arxiv.org/abs/2012.07905v1
• Date: Mon, 14 Dec 2020 19:35:27 GMT
• Title: Sampling and the complexity of nature
• Authors: Dominik Hangleiter
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Randomness is an intrinsic feature of quantum theory. The outcome of any quantum measurement will be random, sampled from a probability distribution that is defined by the measured quantum state. The task of sampling from a prescribed probability distribution is therefore a natural technological application of quantum devices. In the research presented in this thesis, I investigate the complexity-theoretic and physical foundations of quantum sampling algorithms. I assess the computational power of natural quantum simulators and close loopholes in the complexity-theoretic argument for the classical intractability of quantum samplers (Part I). I shed light on how and under which conditions quantum sampling devices can be tested or verified in regimes that are not simulable on classical computers (Part II). Finally, I explore the computational boundary between classical and quantum computing devices (Part III). In particular, I develop efficiently computable measures of the infamous Monte Carlo sign problem and assess those measures both in terms of their practicability as a tool for alleviating or easing the sign problem and the computational complexity of this task. An overarching theme of the thesis is the quantum sign problem which arises due to destructive interference between paths -- an intrinsically quantum effect. The (non-)existence of a sign problem takes on the role as a criterion which delineates the boundary between classical and quantum computing devices. I begin the thesis by identifying the quantum sign problem as a root of the computational intractability of quantum output probabilities. It turns out that the intricate structure of the probability distributions the sign problem gives rise to, prohibits their verification from few samples. In an ironic twist, I show that assessing the intrinsic sign problem of a quantum system is again an intractable problem.

Related papers

• Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
  Recent separations have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if hierarchy collapses. We show that quantum cryptography can be based on the extremely mild assumption that $mathsfP#P notsubseteq mathsf(io)BQP/qpoly$.
  arXiv  Detail & Related papers  (2024-09-23T17:45:33Z)
• Computable and noncomputable in the quantum domain: statements and conjectures [0.70224924046445]
  We consider an approach to the question of describing a class of problems whose solution can be accelerated by a quantum computer. The unitary operation that transforms the initial quantum state into the desired one must be decomposable into a sequence of one- and two-qubit gates.
  arXiv  Detail & Related papers  (2024-03-25T15:47:35Z)
• The hardness of quantum spin dynamics [1.1999555634662633]
  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.
  arXiv  Detail & Related papers  (2023-12-12T19:00:03Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Quantum Conformal Prediction for Reliable Uncertainty Quantification in Quantum Machine Learning [47.991114317813555]
  Quantum models implement implicit probabilistic predictors that produce multiple random decisions for each input through measurement shots. This paper proposes to leverage such randomness to define prediction sets for both classification and regression that provably capture the uncertainty of the model.
  arXiv  Detail & Related papers  (2023-04-06T22:05:21Z)
• Sample-size-reduction of quantum states for the noisy linear problem [0.0]
  We show that it is possible to reduce a quantum sample size in a quantum random access memory (QRAM) to the linearithmic order. We achieve a shorter run-time for the noisy linear problem.
  arXiv  Detail & Related papers  (2023-01-08T05:53:17Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  "Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation. We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-09T19:00:00Z)
• 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)
• Sign Problems in Quantum Field Theory: Classical and Quantum Approaches [0.0]
  lattice field computation theory provides non-perturbative access to equilibrium physics of quantum fields. When applied to certain fermionic systems, or to the calculation of out-of-equilibrium physics, Monte Carlo calculations encounter the so-called sign problem. This thesis details two methods for mitigating or avoiding the sign problem.
  arXiv  Detail & Related papers  (2020-06-05T20:57:51Z)
• An Application of Quantum Annealing Computing to Seismic Inversion [55.41644538483948]
  We apply a quantum algorithm to a D-Wave quantum annealer to solve a small scale seismic inversions problem. The accuracy achieved by the quantum computer is at least as good as that of the classical computer.
  arXiv  Detail & Related papers  (2020-05-06T14:18:44Z)

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.