Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Total Rejection Sampling and the Reduction of the Wave Function

noureddine kermiche

Published Aug 31, 2023• 1 citation
Publisher

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.v2

Related papers

Total Rejection Sampling and the Reduction of the Wave Function

noureddine kermiche

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.

•Jul 29, 2022•0 citations

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, 2022•0 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 Theory•Aug 1, 2013•60 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.2774•Conference on Innovations in Theoretical Computer Science•Jan 8, 2012•37 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.4344•The Journal of Chemical Physics•Nov 4, 2010•8 citations

Symmetric Sampling and the Discrete Laws of Physics (2): Measuring Quanta arriving in a Sensor

Marin van Heel

The classical sampling theorem was refuted in part-1 of this series due to its circular proof: the proof is always true, whether the input signal is under-sampled or not. The symmetric-sampling theory of part-1, is here presented, while minimizing on the mathematics. The classical sampling theorem [Shannon 1949] is based on sampling deterministic signals and produces a finite number of measurements at specific sampling points. At each sampling point, however, the measurement must reach infinite precision. That creates a measurement problem in sampling theory, which is mirrored by an equally fundamental measurement problem in Quantum Mechanics and in all of Physics. Deterministic Classical Physics does not include measurements; it only includes predicting infinitely precise results postulated by “Laws of Physics”. Those postulated results serve only to confirm theoretical predictions. Physics must rather be based on collecting information, that is, on learning from the real physical experiments. Classical Physics is thus constructed with “inverted logic”. Solving this measurement problem calls for a reformulation of the Laws of Physics in discrete form. The mathematical details of such a Discrete Physics are covered in part-3 of this series. Discrete measurements (the act of information collection) on a physical system can never lead to deterministic results since measuring anything to infinite precision requires an infinite amount of energy. Representing a deterministic function in a digital computer to infinite precision, is equally impossible. Symmetric-sampling allows one to assess the physical world by measurements and calculations, without ever deranging into singularities or infinities: not at the small-scale (high-frequency) limit, and not at the large-scale (low-frequency) limit. Symmetric-sampling, combined with a coherent information harvesting strategy, resolves the measurement problem in Physics, including Classical Sampling; Quantum Mechanics; General Relativity, etc. Jumping ahead to the overall conclusions of this series: the 1920s Classical Quantum Mechanics is not only “incomplete”, but it is also superfluous. That conclusion will allow us to leapfrog straight into the realm of a discrete version of Quantum Field Theory (QFT) in future parts of this series.

•Jan 6, 2025•2 citations
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.
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.
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.
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.
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.
The classical sampling theorem was refuted in part-1 of this series due to its circular proof: the proof is always true, whether the input signal is under-sampled or not. The symmetric-sampling theory of part-1, is here presented, while minimizing on the mathematics. The classical sampling theorem [Shannon 1949] is based on sampling deterministic signals and produces a finite number of measurements at specific sampling points. At each sampling point, however, the measurement must reach infinite precision. That creates a measurement problem in sampling theory, which is mirrored by an equally fundamental measurement problem in Quantum Mechanics and in all of Physics. Deterministic Classical Physics does not include measurements; it only includes predicting infinitely precise results postulated by “Laws of Physics”. Those postulated results serve only to confirm theoretical predictions. Physics must rather be based on collecting information, that is, on learning from the real physical experiments. Classical Physics is thus constructed with “inverted logic”. Solving this measurement problem calls for a reformulation of the Laws of Physics in discrete form. The mathematical details of such a Discrete Physics are covered in part-3 of this series. Discrete measurements (the act of information collection) on a physical system can never lead to deterministic results since measuring anything to infinite precision requires an infinite amount of energy. Representing a deterministic function in a digital computer to infinite precision, is equally impossible. Symmetric-sampling allows one to assess the physical world by measurements and calculations, without ever deranging into singularities or infinities: not at the small-scale (high-frequency) limit, and not at the large-scale (low-frequency) limit. Symmetric-sampling, combined with a coherent information harvesting strategy, resolves the measurement problem in Physics, including Classical Sampling; Quantum Mechanics; General Relativity, etc. Jumping ahead to the overall conclusions of this series: the 1920s Classical Quantum Mechanics is not only “incomplete”, but it is also superfluous. That conclusion will allow us to leapfrog straight into the realm of a discrete version of Quantum Field Theory (QFT) in future parts of this series.