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
- What is computable and non-computable in the quantum domain: 7 statements and 3 conjectures [0.7892577704654171]
There is no universal approach that helps to define a scope of problems that quantum computers are able to speed up.
On the one hand, the class of quantum states that is of interest for quantum computing should be complex.
On the other hand, such quantum states should be reachable on a practical quantum computer.
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) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Quantum Sampling Algorithms, Phase Transitions, and Computational
Complexity [0.0]
Drawing independent samples from a probability distribution is an important computational problem with applications in Monte Carlo algorithms, machine learning, and statistical physics.
The problem can in principle be solved on a quantum computer by preparing a quantum state that encodes the entire probability distribution followed by a projective measurement.
We investigate the complexity of adiabatically preparing such quantum states for the Gibbs distributions of various models including the Ising chain, hard-sphere models on different graphs, and a model encoding the unstructured search problem.
arXiv Detail & Related papers (2021-09-07T11:43:45Z) - 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.