Total Rejection Sampling and the Reduction of the Wave Function

noureddine kermiche

Published Jul 29, 2022• 0 citations

Abstract

We propose an exact new sampling algorithm using classical statistical theory. The algorithm is powered by white noise and non-local information. The proposed method will process an infinite number of rejected samples in parallel before accepting one exact single sample from a target distribution using an optimization mechanism. The algorithm is applied to sampling from general distributions in addition to sampling from the wave function density distribution which lies at the heart of the measurement problem in quantum physics.

DOI: 10.36227/techrxiv.20369322

Related papers

Total Rejection Sampling and the Reduction of the Wave Function

noureddine kermiche

Aug 31, 20231 citation

Total Rejection Sampling and the Reduction of the Wave Function

noureddine kermiche

We propose an exact new sampling algorithm using classical statistical theory. The proposed method will process an infinite amount of rejected samples in parallel before accepting one exact single sample from a target distribution using a winner-take-all mechanism. The algorithm is applied for sampling from general distributions in addition to sampling from the wave function density distribution which lies at the heart of the measurement problem in quantum physics.

Jul 29, 20220 citations

Quantum rejection sampling

Māris Ozols, Martin Roetteler, Jérémie Roland

Rejection sampling is a well-known method to sample from a target distribution, given the ability to sample from a given distribution. The method has been first formalized by von Neumann [1951] and has many applications in classical computing. We define a quantum analogue of rejection sampling: given a black box producing a coherent superposition of (possibly unknown) quantum states with some amplitudes, the problem is to prepare a coherent superposition of the same states, albeit with different target amplitudes. The main result of this article is a tight characterization of the query complexity of this quantum state generation problem. We exhibit an algorithm, which we call quantum rejection sampling, and analyze its cost using semidefinite programming. Our proof of a matching lower bound is based on the automorphism principle that allows to symmetrize any algorithm over the automorphism group of the problem. Our main technical innovation is an extension of the automorphism principle to continuous groups that arise for quantum state generation problems where the oracle encodes unknown quantum states, instead of just classical data. Furthermore, we illustrate how quantum rejection sampling may be used as a primitive in designing quantum algorithms, by providing three different applications. We first show that it was implicitly used in the quantum algorithm for linear systems of equations by Harrow et al. [2009]. Second we show that it can be used to speed up the main step in the quantum Metropolis sampling algorithm by Temme et al. [2011]. Finally, we derive a new quantum algorithm for the hidden shift problem of an arbitrary Boolean function and relate its query complexity to “water-filling” of the Fourier spectrum.

ACM Transactions on Computation TheoryAug 1, 201353 citations

Quantum rejection sampling

Māris Ozols, Martin Roetteler, Jérémie Roland

Rejection sampling is a well-known method to sample from a target distribution, given the ability to sample from a given distribution. The method has been first formalized by von Neumann (1951) and has many applications in classical computing. We define a quantum analogue of rejection sampling: given a black box producing a coherent superposition of (possibly unknown) quantum states with some amplitudes, the problem is to prepare a coherent superposition of the same states, albeit with different target amplitudes. The main result of this paper is a tight characterization of the query complexity of this quantum state generation problem. We exhibit an algorithm, which we call quantum rejection sampling, and analyze its cost using semidefinite programming. Our proof of a matching lower bound is based on the automorphism principle which allows to symmetrize any algorithm over the automorphism group of the problem. Our main technical innovation is an extension of the automorphism principle to continuous groups that arise for quantum state generation problems where the oracle encodes unknown quantum states, instead of just classical data. Furthermore, we illustrate how quantum rejection sampling may be used as a primitive in designing quantum algorithms, by providing three different applications. We first show that it was implicitly used in the quantum algorithm for linear systems of equations by Harrow, Hassidim and Lloyd. Secondly, we show that it can be used to speed up the main step in the quantum Metropolis sampling algorithm by Temme et al.. Finally, we derive a new quantum algorithm for the hidden shift problem of an arbitrary Boolean function and relate its query complexity to "water-filling" of the Fourier spectrum.

arXiv:1103.2774Conference on Innovations in Theoretical Computer ScienceJan 8, 201225 citations

Optimum and efficient sampling for variational quantum Monte Carlo

J. R. Trail, Ryo Maezono

Quantum mechanics for many-body systems may be reduced to the evaluation of integrals in 3N dimensions using Monte Carlo, providing the Quantum Monte Carlo ab initio methods. Here we limit ourselves to expectation values for trial wave functions, that is to variational quantum Monte Carlo. Almost all previous implementations employ samples distributed as the physical probability density of the trial wave function, and assume the central limit theorem to be valid. In this paper we provide an analysis of random error in estimation and optimization that leads naturally to new sampling strategies with improved computational and statistical properties. A rigorous lower limit to the random error is derived, and an efficient sampling strategy presented that significantly increases computational efficiency. In addition the infinite variance heavy tailed random errors of optimum parameters in conventional methods are replaced with a Normal random error, strengthening the theoretical basis of optimization. The method is applied to a number of first row systems and compared with previously published results.

arXiv:1011.4344The Journal of Chemical PhysicsNov 4, 20108 citations

Quantum-enhanced Markov chain Monte Carlo

David Layden, Guglielmo Mazzola, Ryan V. Mishmash +4 more

Sampling from complicated probability distributions is a hard computational problem arising in many fields, including statistical physics, optimization, and machine learning. Quantum computers have recently been used to sample from complicated distributions that are hard to sample from classically, but which seldom arise in applications. Here we introduce a quantum algorithm to sample from distributions that pose a bottleneck in several applications, which we implement on a superconducting quantum processor. The algorithm performs Markov chain Monte Carlo (MCMC), a popular iterative sampling technique, to sample from the Boltzmann distribution of classical Ising models. In each step, the quantum processor explores the model in superposition to propose a random move, which is then accepted or rejected by a classical computer and returned to the quantum processor, ensuring convergence to the desired Boltzmann distribution. We find that this quantum algorithm converges in fewer iterations than common classical MCMC alternatives on relevant problem instances, both in simulations and experiments. It therefore opens a new path for quantum computers to solve useful--not merely difficult--problems in the near term.

arXiv:2203.12497Mar 23, 20220 citations