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

arXiv:quant-ph/0208112

Creating superpositions that correspond to efficiently integrable probability distributions

Lov K. Grover, Terry Rudolph

Published Aug 15, 2002• 615 citations
arXivHTMLPDF

Abstract

We give a simple and efficient process for generating a quantum superposition of states which form a discrete approximation of any efficiently integrable (such as log concave) probability density functions.
DOI
10.48550/arxiv.quant-ph/0208112

Related papers

An efficient quantum algorithm for preparation of uniform quantum superposition states

Alok Shukla, Prakash Vedula

arXiv:2306.11747•Quantum Information Processing•Jan 29, 2024•48 citations

Efficient Quantum State Preparation for the Cauchy Distribution Based on Piecewise Arithmetic

Ethan T. Wang

The benefits of the quantum Monte Carlo algorithm heavily rely on the efficiency of the superposition state preparation. So far, most reported Monte Carlo algorithms use Grover's state preparation algorithm which is suitable for efficiently integrable distribution functions. Consequently, most reported works are based on log-concave distributions, such as normal distributions. However, non-log-concave distributions still have many uses, such as in financial modeling. Recently, a new method was proposed that does not need integration to calculate the rotation angle for state preparation. However, performing efficient state preparation is still difficult due to the high cost associated with high precision and low error in the calculation for the rotation angle. Many methods of quantum state preparation use polynomial Taylor approximations to reduce the computation cost. However, Taylor approximations do not work well with heavy-tailed distribution functions that are not bounded exponentially. In this work, we present a method of efficient state preparation for heavy-tailed distribution functions. Specifically, we present a quantum gate-level algorithm to prepare quantum superposition states based on the Cauchy distribution which is a non-log-concave heavy-tailed distribution. Our procedure relies on a piecewise polynomial function instead of a single Taylor approximation to reduce computational cost and increase accuracy. The Cauchy distribution is an even function, so the proposed piecewise polynomial contains only a quadratic term and a constant term to maintain the simplest approximation of an even function. Numerical analysis shows that the required number of subdomains increases linearly as the approximation error decreases exponentially. Furthermore, the computation complexity of the proposed algorithm is independent of the number of subdomains in the quantum implementation of the piecewise function due to quantum parallelism. An example of the proposed algorithm based on a simulation conducted in Qiskit is presented to demonstrate its capability to perform state preparation based on the Cauchy distribution.

IEEE Transactions on Quantum Engineering•Dec 28, 2021•2 citations

Probability Distributions as Alternatives of the Density Operator and Wave Function for Describing Quantum States

Margarita A. Man’ko, Vladimir I. Man’ko

Springer eBooks•Jan 1, 2023•1 citation

Approximating outcome probabilities of linear optical circuits

Youngrong Lim, Changhun Oh

Abstract Quasiprobability representations are important tools for analyzing a quantum system, such as a quantum state or a quantum circuit. In this work, we propose classical algorithms specialized for approximating outcome probabilities of a linear optical circuit using quasiprobability distributions. Notably, we can reduce the negativity bound of a circuit from exponential to at most polynomial for specific cases by modulating the shapes of quasiprobability distributions thanks to the symmetry of the linear optical transformation in the phase space. Consequently, our scheme provides an efficient estimation of outcome probabilities within an additive-error whose precision depends on the classicality of the input state. When the classicality is high enough, we reach a polynomial-time estimation algorithm of a probability within a multiplicative-error by an efficient sampling from a log-concave function. By choosing appropriate input states and measurements, our results provide plenty of quantum-inspired classical algorithms for approximating various matrix functions beating best-known results. Moreover, we give sufficient conditions for the classical simulability of Gaussian Boson sampling using our approximating algorithm for any (marginal) outcome probability under the poly-sparse condition.

arXiv:2211.07184•npj Quantum Information•Dec 16, 2023•8 citations

A non-linear LLR approximation for LDPC decoding over impulsive noise channels

Yi Hou, Rongke Liu, Ling Zhao

The performance of Low-Density Parity-Check codes over symmetric alpha-stable impulsive noise channels is considered in this paper. Due to the lack of closed-form expressions for the probability density functions of almost all the alpha-stable distributions, an efficient non-linear approximation method for channel log-likelihood ratio is presented to achieve high decoding performance covering the range of characteristic exponent from 1 to 2 and avoid the use of complicated numerical integrations. The simulations for both long and short codes show that the parameter selection of the proposed method is not sensitive to the noise level. Even fixed parameter setting for the proposed non-linear approximation can obtain a satisfying decoding performance.

IEEE/CIC International Conference on Communications in China (ICCC)•Oct 1, 2014•10 citations

Generating quantum channels from functions on discrete sets

Alice C. Quillen, Nathan Skerrett

arXiv:2308.06084•Quantum Information Processing•Feb 8, 2024•2 citations
The benefits of the quantum Monte Carlo algorithm heavily rely on the efficiency of the superposition state preparation. So far, most reported Monte Carlo algorithms use Grover's state preparation algorithm which is suitable for efficiently integrable distribution functions. Consequently, most reported works are based on log-concave distributions, such as normal distributions. However, non-log-concave distributions still have many uses, such as in financial modeling. Recently, a new method was proposed that does not need integration to calculate the rotation angle for state preparation. However, performing efficient state preparation is still difficult due to the high cost associated with high precision and low error in the calculation for the rotation angle. Many methods of quantum state preparation use polynomial Taylor approximations to reduce the computation cost. However, Taylor approximations do not work well with heavy-tailed distribution functions that are not bounded exponentially. In this work, we present a method of efficient state preparation for heavy-tailed distribution functions. Specifically, we present a quantum gate-level algorithm to prepare quantum superposition states based on the Cauchy distribution which is a non-log-concave heavy-tailed distribution. Our procedure relies on a piecewise polynomial function instead of a single Taylor approximation to reduce computational cost and increase accuracy. The Cauchy distribution is an even function, so the proposed piecewise polynomial contains only a quadratic term and a constant term to maintain the simplest approximation of an even function. Numerical analysis shows that the required number of subdomains increases linearly as the approximation error decreases exponentially. Furthermore, the computation complexity of the proposed algorithm is independent of the number of subdomains in the quantum implementation of the piecewise function due to quantum parallelism. An example of the proposed algorithm based on a simulation conducted in Qiskit is presented to demonstrate its capability to perform state preparation based on the Cauchy distribution.
Abstract Quasiprobability representations are important tools for analyzing a quantum system, such as a quantum state or a quantum circuit. In this work, we propose classical algorithms specialized for approximating outcome probabilities of a linear optical circuit using quasiprobability distributions. Notably, we can reduce the negativity bound of a circuit from exponential to at most polynomial for specific cases by modulating the shapes of quasiprobability distributions thanks to the symmetry of the linear optical transformation in the phase space. Consequently, our scheme provides an efficient estimation of outcome probabilities within an additive-error whose precision depends on the classicality of the input state. When the classicality is high enough, we reach a polynomial-time estimation algorithm of a probability within a multiplicative-error by an efficient sampling from a log-concave function. By choosing appropriate input states and measurements, our results provide plenty of quantum-inspired classical algorithms for approximating various matrix functions beating best-known results. Moreover, we give sufficient conditions for the classical simulability of Gaussian Boson sampling using our approximating algorithm for any (marginal) outcome probability under the poly-sparse condition.
The performance of Low-Density Parity-Check codes over symmetric alpha-stable impulsive noise channels is considered in this paper. Due to the lack of closed-form expressions for the probability density functions of almost all the alpha-stable distributions, an efficient non-linear approximation method for channel log-likelihood ratio is presented to achieve high decoding performance covering the range of characteristic exponent from 1 to 2 and avoid the use of complicated numerical integrations. The simulations for both long and short codes show that the parameter selection of the proposed method is not sensitive to the noise level. Even fixed parameter setting for the proposed non-linear approximation can obtain a satisfying decoding performance.