Sampling and the complexity of nature

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.

PhD Thesis, Freie Universität Berlin (2020). Chapters 2, 3, 7, 8, 9 contain unpublished overview material

References in corpus (43)

• Many-Body Physics with Ultracold Gases
• Entanglement detection
• Quantum walks of correlated particles
• Efficient quantum state tomography
• Photonic Boson Sampling in a Tunable Circuit
• Direct Fidelity Estimation from Few Pauli Measurements
• Spectral signatures of many-body localization with interacting photons
• Universal computation by multi-particle quantum walk
• Controlled exchange interaction between pairs of neutral atoms in an optical lattice
• Evenly distributed unitaries: on the structure of unitary designs
• Digital quantum simulation of fermionic models with a superconducting circuit
• The `Higgs' Amplitude Mode at the Two-Dimensional Superfluid-Mott Insulator Transition
• Device-independent tests of classical and quantum dimensions
• Semi-device-independent security of one-way quantum key distribution
• Signatures of Many-Body Localization in a Controlled Open Quantum System
• Emergence of coherence and the dynamics of quantum phase transitions
• Sublattice addressing and spin-dependent motion of atoms in a double-well lattice
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
• The Higgs mode in a two-dimensional superfluid
• Geometry Dependence of the Sign Problem
• Both Toffoli and Controlled-NOT need little help to do universal quantum computation
• Semi-device-independent bounds on entanglement
• Quantum Chaos, Delocalization, and Entanglement in Disordered Heisenberg Models
• Efficient synthesis of probabilistic quantum circuits with fallback
• The Clifford group fails gracefully to be a unitary 4-design
• On the simulation of quantum circuits
• Non-destructive selective probing of phononic excitations in a cold Bose gas using impurities
• Exact Boson Sampling using Gaussian continuous variable measurements
• Non-local updates for quantum Monte Carlo simulations
• Nested Cluster Algorithm for Frustrated Quantum Antiferromagnets
• Quantum pseudo-randomness from cluster-state quantum computation
• Clock Quantum Monte Carlo: an imaginary-time method for real-time quantum dynamics
• Noise Threshold of Quantum Supremacy
• On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
• Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes
• Efficient algorithm for optimizing data pattern tomography
• Fourier analysis of sampling from noisy chaotic quantum circuits
• Solution to the sign problem in a frustrated quantum impurity model
• On the Complexity of Random Quantum Computations and the Jones Polynomial
• Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise?
• The Computational Complexity of Ball Permutations
• Analogue Quantum Simulation: A Philosophical Prospectus