Randomness is an intrinsic feature of quantum theory. The outcome of any 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 therefore seems to be a natural technological application of quantum devices. And indeed, certain random sampling tasks have been proposed to experimentally demonstrate the speedup of quantum over classical computation, so-called “quantum computational supremacy”. In the research presented in this thesis, I investigate the complexity-theoretic and physical foundations of quantum sampling algorithms. Using the theory of computational complexity, 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). In particular, I prove anticoncentration for quantum circuit families that give rise to a 2-design and review methods for proving average-case hardness. I present quantum random sampling schemes that are tailored to large-scale quantum simulation hardware but at the same time rise up to the highest standard in terms of their complexity-theoretic underpinning. Using methods from property testing and quantum system identification, I shed light on the question, how and under which conditions quantum sampling devices can be tested or verified in regimes that are not simulable on classical computers (Part II). I present a no-go result that prevents efficient verification of quantum random sampling schemes as well as approaches using which this no-go result can be circumvented. In particular, I develop fully efficient verification protocols in what I call the measurement-device-dependent scenario in which single-qubit measurements are assumed to function with high accuracy. Finally, I try to understand the physical mechanisms governing the computational boundary between classical and quantum computing devices by challenging their computational power using tools from computational physics and the theory of computational complexity (Part III). 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.
Randomness is an intrinsic feature of quantum theory. The outcome of any 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 therefore seems to be a natural technological application of quantum devices. And indeed, certain random sampling tasks have been proposed to experimentally demonstrate the speedup of quantum over classical computation, so-called “quantum computational supremacy”. In the research presented in this thesis, I investigate the complexity-theoretic and physical foundations of quantum sampling algorithms. Using the theory of computational complexity, 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). In particular, I prove anticoncentration for quantum circuit families that give rise to a 2-design and review methods for proving average-case hardness. I present quantum random sampling schemes that are tailored to large-scale quantum simulation hardware but at the same time rise up to the highest standard in terms of their complexity-theoretic underpinning. Using methods from property testing and quantum system identification, I shed light on the question, how and under which conditions quantum sampling devices can be tested or verified in regimes that are not simulable on classical computers (Part II). I present a no-go result that prevents efficient verification of quantum random sampling schemes as well as approaches using which this no-go result can be circumvented. In particular, I develop fully efficient verification protocols in what I call the measurement-device-dependent scenario in which single-qubit measurements are assumed to function with high accuracy. Finally, I try to understand the physical mechanisms governing the computational boundary between classical and quantum computing devices by challenging their computational power using tools from computational physics and the theory of computational complexity (Part III). 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.
A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS satisfies an anti-concentration property, making it the first supremacy proposal with both average-case hardness and anti-concentration.
It remains questionable whether all physically realizable computational model can be simulated by currently available digital computer in an efficient manner. The theory of Quantum Mechanics offers an answer to this question through one of its branches that intersects with Computer Science, known as Quantum Computing. It claims that current computers, which is operating based on classical mechanics cannot efficiently simulate quantum mechanical process. Under this claim, a computer that is operating based on quantum mechanics holds more computational power than classical computers, promising a possibility to computationally solve problems that are classically intractable. To show that this claim holds, numerous quantum computational models have been proposed and analyzed through the lens of Computational Complexity Theory, providing a rigorous notion of efficiency. Models that are more feasible experimentally, although not necessarily universal, have also been of a particular interests given the numerous complicated challenges surrounding the experimental implementation of a universal quantum computer. One of this non-universal models is called Gaussian Boson Sampling (GBS), which embraces the methods of Quantum Optics by sampling the number of photon outputs from a linear optical network as a means to process quantum information. Compared to its prototype model, Boson Sampling, GBS is more experimentally feasible due to its method of generating photon that is based on the Continuous Variable (CV) paradigm of Quantum Information. Nevertheless as with Boson Sampling, it was also shown that classical simulation of GBS cannot be performed efficiently under some highly plausible conjectures. In the work presented in this thesis, we probe the complexity of classically constructing the probability distribution induced by GBS using the method of Quantum Homodyne Tomography. Instead of photon number measurement, this method further embraces the CV paradigm in the measurement of GBS by using Homodyne measurements that outputs real numbers. Sample data obtained from the measurement outcomes is then classically processed using Pattern Functions, which we use to approximate the probability distribution of GBS. A series of computer simulations that approximates some probability values of GBS are presented here, which shows that the number of samples needed to decrease the error of the approximation increases rapidly for more accurate approximation. We have derived a bound for the approximation error which can be achieved given that the sampled data satisfies a certain statistical property. This statistical property can eventually be satisfied as the number of Homodyne samples increases. Having shown another evidence for the complexity of approximating GBS using Homodyne Tomography, we further investigate the nature of the complexity of GBS by analyzing its classical-quantum computational boundary in the spectrum of amount of noise present in a GBS setup. In doing this, we built our discussions on the measure of non-classicality using the presence of negative values in the Quasi-probability distribution (QPD) representation of states of a quantum system. We then discuss existing results that shows the possibility of efficient classical simulation of a quantum computational model given a sufficient amount of noise. These results impose a necessary criteria of the minimum amount of noise that an experiment has to surpass in order for it to be impossible to simulate classically in an efficient manner. We extend this idea for GBS, where we propose a modified GBS where we consider noise in its measurements that opens a way for a possible formulation of a noise condition that a GBS experiment has to fulfill to rule out possible efficient classical simulation. To further probe the classical-quantum computational boundary, we also propose a different quantum computational model called the Photon-added Thermal State CV-Sampling (PATS CVS), which can be formulated similarly to our noisy GBS model. We then discuss existing results that analyzes the negativity of the QPD representation of a noisy Photon-added Thermal state (PATS), which constitutes the inputs for PATS CVS. Using the result that shows the quantum-classical transition in terms of the QPD negativity for a PATS state when the amount of noise changes, we discuss the potential of PATS CVS model as a possible avenue to further probe the transition between efficiently simulable and non-efficiently simulable quantum mechanical experiment.
As Moore's law reaches its limits, quantum computers are emerging with the promise of dramatically outperforming classical computers. We have witnessed the advent of quantum processors with over 50 quantum bits (qubits), which are expected to be beyond the reach of classical simulation. Quantum supremacy is the event at which the old Extended Church-Turing Thesis is overturned: A quantum computer performs a task that is practically impossible for any classical (super)computer. The demonstration requires both a solid theoretical guarantee and an experimental realization. The lead candidate is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of random quantum circuits. Google recently announced a 53−qubit experimental demonstration of RCS. Soon after, classical algorithms appeared that challenge the supremacy of random circuits by estimating their outputs. How hard is it to classically simulate the output of random quantum circuits? We prove that estimating the output probabilities of random quantum circuits is formidably hard (#P-Hard) for any classical computer. This makes RCS the strongest candidate for demonstrating quantum supremacy relative to all other proposals. The robustness to the estimation error that we prove may serve as a new hardness criterion for the performance of classical algorithms. To achieve this, we introduce the Cayley path interpolation between any two gates of a quantum computation and convolve recent advances in quantum complexity and information with probability and random matrices. Furthermore, we apply algebraic geometry to generalize the well-known Berlekamp-Welch algorithm that is widely used in coding theory and cryptography. Our results imply that there is an exponential hardness barrier for the classical simulation of most quantum circuits.
Simulations play a crucial role in the investigation of complex quantum systems. In this thesis, locality structures of quantum systems are exploited to obtain complexity theoretic results with various physical implications. More specifically, rigorous mathematical tools are used and developed further, to investigate open quantum systems and thermal states. Moreover, important advances in photonic quantum simulations are discussed. For open quantum spin lattice systems new simulation schemes are provided. It is shown that Markovian dynamics can be simulated efficiently in the unitary circuit model, which can be seen as a dissipative Church-Turing type theorem. Moreover, Markovian dynamics is quasi-local and can be locally simulated on classical computers with a cost scaling polynomially in the system size. These results generalize standard tools from the investigation of Hamiltonian systems to open quantum systems. In particular, they provide a rigorous basis for their numerical simulation. However, also a major roadblock for making such simulations reliable is identified: Testing positivity of certain common approximations to mixed quantum states, called matrix product operators, is shown to be NP-hard in the system size and undecidable in the thermodynamic limit. Also more state space structures, originating from the spatial locality structure are discussed: Most states in state space cannot be generated efficiently with local Liouvillian dynamics and pure states generated in real- space renormalization schemes turn out to have local corrections in spatial dimensions larger than one. For thermal states on spin and fermionic lattice systems, a perturbation formula is provided and exponential clustering of correlations at high enough temperature is proven. This has various consequences: It leads to the extension of the concept of intensive temperature to interacting quantum systems, allows for efficient classical local simulations at high enough temperature, provides an upper bound on phase transition temperatures, and implies stability of thermal states against Hamiltonian perturbations. For photonic quantum simulations, sample complexity lower bounds for the verification of Boson-Sampling simulations are explained, which are applicable to a restricted setting. These bounds rely on a lower bound on the min-entropy of the output distribution of Boson-Sampling. This indicates that Boson-Sampling cannot be verified efficiently classically. Complementary to that, a reliable verification scheme for photonic state preparations is discussed, which uses single mode measurements as a simple quantum resource. The verification scheme is efficient for a large class of photonic simulations, including Boson-Sampling experiments with constantly many photons and state preparations necessary for measurement based quantum computing.
Abstract There is a large body of evidence for the potential of greater computational power using information carriers that are quantum mechanical over those governed by the laws of classical mechanics. But the question of the exact nature of the power contributed by quantum mechanics remains only partially answered. Furthermore, there exists doubt over the practicality of achieving a large enough quantum computation that definitively demonstrates quantum supremacy. Recently the study of computational problems that produce samples from probability distributions has added to both our understanding of the power of quantum algorithms and lowered the requirements for demonstration of fast quantum algorithms. The proposed quantum sampling problems do not require a quantum computer capable of universal operations and also permit physically realistic errors in their operation. This is an encouraging step towards an experimental demonstration of quantum algorithmic supremacy. In this paper, we will review sampling problems and the arguments that have been used to deduce when sampling problems are hard for classical computers to simulate. Two classes of quantum sampling problems that demonstrate the supremacy of quantum algorithms are BosonSampling and Instantaneous Quantum Polynomial-time Sampling. We will present the details of these classes and recent experimental progress towards demonstrating quantum supremacy in BosonSampling.
While quantum speed-up in solving certain decision problems by a fault-tolerant universal quantum computer has been promised, a timely research interest includes how far one can reduce the resource requirement to demonstrate a provable advantage in quantum devices without demanding quantum error correction, which is crucial for prolonging the coherence time of qubits. We propose a model device made of locally interacting multiple qubits, designed such that simultaneous single-qubit measurements on it can output probability distributions whose average-case sampling is classically intractable, under similar assumptions as the sampling of noninteracting bosons and instantaneous quantum circuits. Notably, in contrast to these previous unitary-based realizations, our measurement-based implementation has two distinctive features. (i) Our implementation involves no adaptation of measurement bases, leading output probability distributions to be generated in constant time, independent of the system size. Thus, it could be implemented in principle without quantum error correction. (ii) Verifying the classical intractability of our sampling is done by changing the Pauli measurement bases only at certain output qubits. Our usage of random commuting quantum circuits in place of computationally universal circuits allows a unique unification of sampling and verification, so they require the same physical resource requirements in contrast to the more demanding verification protocols seen elsewhere in the literature.