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:2208.00162

Few Quantum Algorithms on Amplitude Distribution

Debajyoti Bera, Tharrmashastha Sapv

Published Jul 30, 2022• 0 citations
arXivHTMLPDF

Abstract

Amplitude filtering is concerned with identifying basis-states in a superposition whose amplitudes are greater than a specified threshold; probability filtering is defined analogously for probabilities. Given the scarcity of qubits, the focus of this work is to design log-space algorithms for them. Both algorithms follow a similar pattern of estimating the amplitude (or, probability for the latter problem) of each state, in superposition, then comparing each estimate against the threshold for setting up a flag qubit upon success, finally followed by amplitude amplification of states in which the flag is set. We show how to implement each step using very few qubits by designing three subroutines. Our first algorithm performs amplitude amplification even when the "good state'' operator has a small probability of being incorrect -- here we improve upon the space complexity of the previously known algorithms. Our second algorithm performs "true amplitude estimation'' in roughly the same complexity as that of "amplitude estimation'', which actually estimates a probability instead of an amplitude. Our third algorithm is for performing amplitude estimation in parallel (superposition) which is difficult when each estimation branch involves different oracles. As an immediate reward, we observed that the above algorithms for the filtering problems directly improved the upper bounds on the space-bounded query complexity of problems such as non-linearity estimation of Boolean functions and $k$-distinctness.

DOI
10.48550/arxiv.2208.00162

Related papers

HighDist Framework: Algorithms and Applications

Debajyoti Bera, Tharrmashastha Sapv

We introduce the problem of determining if the mode of the output distribution of a quantum circuit (given as a black-box) is larger than a given threshold, named HighDist, and a similar problem based on the absolute values of the amplitudes, named HighAmp. We design quantum algorithms for promised versions of these problems whose space complexities are logarithmic in the size of the domain of the distribution, but the query complexities are independent. Using these, we further design algorithms to estimate the largest probability and the largest amplitude among the output distribution of a quantum black-box. All of these allow us to improve the query complexity of a few recently studied problems, namely, $k$-distinctness and its gapped version, estimating the largest frequency in an array, estimating the min-entropy of a distribution, and the non-linearity of a Boolean function, in the $\tilde{O}(1)$-qubits scenario. The time-complexities of almost all of our algorithms have a small overhead over their query complexities making them efficiently implementable on currently available quantum backends.

arXiv:2103.09033•Mar 16, 2021•0 citations

Quantum amplitude estimation from classical signal processing

Farrokh Labib, B. D. Clader, Nikitas Stamatopoulos +1 more

We demonstrate that the problem of amplitude estimation, a core subroutine used in many quantum algorithms, can be mapped directly to a problem in signal processing called direction of arrival (DOA) estimation. The DOA task is to determine the direction of arrival of an incoming wave with the fewest possible measurements. The connection between amplitude estimation and DOA allows us to make use of the vast amount of signal processing algorithms to post-process the measurements of the Grover iterator at predefined depths. Using an off-the-shelf DOA algorithm called ESPRIT together with a compressed-sensing based sampling approach, we create a phase-estimation free, parallel quantum amplitude estimation (QAE) algorithm with a worst-case sequential query complexity of $\sim 4.3/\varepsilon$ and a parallel query complexity of $\sim 0.26/\varepsilon$ at 95% confidence. This performance is statistically equivalent and a $16\times$ improvement over Rall and Fuller [Quantum 7, 937 (2023)], for sequential and parallel query complexity respectively, which to our knowledge is the best published result for amplitude estimation. The approach presented here provides a simple, robust, parallel method to performing QAE, with many possible avenues for improvement borrowing ideas from the wealth of literature in classical signal processing.

arXiv:2405.14697•May 23, 2024•0 citations

Modified Iterative Quantum Amplitude Estimation is Asymptotically Optimal

Shion Fukuzawa, Christopher Ho, Sandy Irani +1 more

In this work, we provide the first QFT-free algorithm for Quantum Amplitude Estimation (QAE) that is asymptotically optimal while maintaining the leading numerical performance. QAE algorithms appear as a subroutine in many applications for quantum computers. The optimal query complexity achievable by a quantum algorithm for QAE is log queries, providing a speedup of a factor of 1/ε over any other classical algorithm for the same problem. The original algorithm for QAE utilizes the quantum Fourier transform (QFT) which is expected to be a challenge for near-term quantum hardware. To solve this problem, there has been interest in designing a QAE algorithm that avoids using QFT. Recently, the iterative QAE algorithm (IQAE) [1] was introduced with a near-optimal query complexity and small constant factors. In this work, we combine ideas from the preceding line of work to introduce a QFT-free QAE algorithm that maintains the asymptotically optimal query complexity while retaining small constant factors. We supplement our analysis with numerical experiments comparing our performance with IQAE where we find that our modifications retain the high performance, and in some cases even improve the numerical results.

arXiv:2208.14612•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2023•6 citations

Efficient quantum algorithms for set operations

Rehab Elgendy, Ahmed Younes, H.M. Abu-Donia +1 more

Abstract Analyzing the relations between Boolean functions has many applications in many fields, such as database systems, cryptography, and collision problems. This paper proposes four quantum algorithms that use amplitude amplification techniques to perform set operations, including Intersection, Difference, and Union, on two Boolean functions in $$\mathcal {O}(\sqrt{\mathcal {N}} )$$ O ( N ) time complexity. The proposed algorithms employ two quantum amplitude amplification techniques divided into two stages. The first stage uses the Younes et al. algorithm for quantum searching via entanglement and partial diffusion to prepare incomplete superpositions of the truth set of the first Boolean function. In the second stage, a modified version of Arima’s algorithm, along with an oracle that represent the second Boolean function, is employed to handle the set operations. The proposed algorithms have a higher probability of success in more general and comprehensive applications when compared with relevant techniques in literature.

Scientific Reports•Mar 25, 2024•2 citations

Chapter 4: Amplitude amplification and estimation

Giacomo Nannicini

In Chs. 2 and 3 we described several quantum algorithms that are exponentially faster than classical algorithms for the same problem, under some measure of complexity. Unfortunately, the algorithms of Ch. 2 apply to rather contrived problems that do not have known direct applications. We now describe a quantum algorithm that gives only a polynomial—more specifically, quadratic—speedup with respect to classical algorithms, but it applies to a large class of problems and finds many useful applications, both directly and as an algorithmic design tool. The algorithm is known as Grover’s search [89], and its generalization is known as amplitude amplification [43]. Amplitude amplification is widely used as part of many quantum algorithms. It also serves as the basis for amplitude estimation, a way of estimating probabilities quadratically faster than with classical Monte Carlo, and for quantum minimum finding. All these topics are discussed in this chapter.

Society for Industrial and Applied Mathematics eBooks•Dec 17, 2025•0 citations

Space efficient quantum algorithms for mode, min-entropy and k-distinctness.

Debajyoti Bera, Tharrmashastha Sapv

We study the problem of determining if the mode of the output distribution of a quantum circuit given as a black-box is larger than a given threshold. We design a quantum algorithm for a promised version of this problem whose space complexity is logarithmic in the size of the domain of the distribution. Developing on top of that we further design an algorithm to estimate the largest probability among the outcomes of that circuit. This allows to revisit a few recently studied problems in the few-qubits scenario, namely $k$-distinctness and its gapped version, estimating the largest frequency in an array, and estimating the min-entropy of a distribution. In particular, our algorithm for $k$-distinctness on $n$-sized $m$-valued arrays requires $O(\log n + \log m)$ qubits compared to $\Omega(poly(n))$ qubits required by all the previous algorithms, and its query complexity is optimal for $k=\Omega(n)$. We also study reductions between the above problems and derive better lower bounds for some of them. The time-complexities of our algorithms have a small overhead over their query complexities making them efficiently implementable on currently available quantum backends.

•Mar 16, 2021•0 citations
Amplitude filtering is concerned with identifying basis-states in a superposition whose amplitudes are greater than a specified threshold; probability filtering is defined analogously for probabilities. Given the scarcity of qubits, the focus of this work is to design log-space algorithms for them. Both algorithms follow a similar pattern of estimating the amplitude (or, probability for the latter problem) of each state, in superposition, then comparing each estimate against the threshold for setting up a flag qubit upon success, finally followed by amplitude amplification of states in which the flag is set. We show how to implement each step using very few qubits by designing three subroutines. Our first algorithm performs amplitude amplification even when the "good state'' operator has a small probability of being incorrect -- here we improve upon the space complexity of the previously known algorithms. Our second algorithm performs "true amplitude estimation'' in roughly the same complexity as that of "amplitude estimation'', which actually estimates a probability instead of an amplitude. Our third algorithm is for performing amplitude estimation in parallel (superposition) which is difficult when each estimation branch involves different oracles. As an immediate reward, we observed that the above algorithms for the filtering problems directly improved the upper bounds on the space-bounded query complexity of problems such as non-linearity estimation of Boolean functions and kkk-distinctness.
We introduce the problem of determining if the mode of the output distribution of a quantum circuit (given as a black-box) is larger than a given threshold, named HighDist, and a similar problem based on the absolute values of the amplitudes, named HighAmp. We design quantum algorithms for promised versions of these problems whose space complexities are logarithmic in the size of the domain of the distribution, but the query complexities are independent. Using these, we further design algorithms to estimate the largest probability and the largest amplitude among the output distribution of a quantum black-box. All of these allow us to improve the query complexity of a few recently studied problems, namely, kkk-distinctness and its gapped version, estimating the largest frequency in an array, estimating the min-entropy of a distribution, and the non-linearity of a Boolean function, in the O~(1)\tilde{O}(1)O~(1)-qubits scenario. The time-complexities of almost all of our algorithms have a small overhead over their query complexities making them efficiently implementable on currently available quantum backends.
We demonstrate that the problem of amplitude estimation, a core subroutine used in many quantum algorithms, can be mapped directly to a problem in signal processing called direction of arrival (DOA) estimation. The DOA task is to determine the direction of arrival of an incoming wave with the fewest possible measurements. The connection between amplitude estimation and DOA allows us to make use of the vast amount of signal processing algorithms to post-process the measurements of the Grover iterator at predefined depths. Using an off-the-shelf DOA algorithm called ESPRIT together with a compressed-sensing based sampling approach, we create a phase-estimation free, parallel quantum amplitude estimation (QAE) algorithm with a worst-case sequential query complexity of ∼4.3/ε\sim 4.3/\varepsilon∼4.3/ε and a parallel query complexity of ∼0.26/ε\sim 0.26/\varepsilon∼0.26/ε at 95% confidence. This performance is statistically equivalent and a 16×16\times16× improvement over Rall and Fuller [Quantum 7, 937 (2023)], for sequential and parallel query complexity respectively, which to our knowledge is the best published result for amplitude estimation. The approach presented here provides a simple, robust, parallel method to performing QAE, with many possible avenues for improvement borrowing ideas from the wealth of literature in classical signal processing.
In this work, we provide the first QFT-free algorithm for Quantum Amplitude Estimation (QAE) that is asymptotically optimal while maintaining the leading numerical performance. QAE algorithms appear as a subroutine in many applications for quantum computers. The optimal query complexity achievable by a quantum algorithm for QAE is log queries, providing a speedup of a factor of 1/ε over any other classical algorithm for the same problem. The original algorithm for QAE utilizes the quantum Fourier transform (QFT) which is expected to be a challenge for near-term quantum hardware. To solve this problem, there has been interest in designing a QAE algorithm that avoids using QFT. Recently, the iterative QAE algorithm (IQAE) [1] was introduced with a near-optimal query complexity and small constant factors. In this work, we combine ideas from the preceding line of work to introduce a QFT-free QAE algorithm that maintains the asymptotically optimal query complexity while retaining small constant factors. We supplement our analysis with numerical experiments comparing our performance with IQAE where we find that our modifications retain the high performance, and in some cases even improve the numerical results.
Abstract Analyzing the relations between Boolean functions has many applications in many fields, such as database systems, cryptography, and collision problems. This paper proposes four quantum algorithms that use amplitude amplification techniques to perform set operations, including Intersection, Difference, and Union, on two Boolean functions in O(N)\mathcal {O}(\sqrt{\mathcal {N}} )O(N​) O ( N ) time complexity. The proposed algorithms employ two quantum amplitude amplification techniques divided into two stages. The first stage uses the Younes et al. algorithm for quantum searching via entanglement and partial diffusion to prepare incomplete superpositions of the truth set of the first Boolean function. In the second stage, a modified version of Arima’s algorithm, along with an oracle that represent the second Boolean function, is employed to handle the set operations. The proposed algorithms have a higher probability of success in more general and comprehensive applications when compared with relevant techniques in literature.
In Chs. 2 and 3 we described several quantum algorithms that are exponentially faster than classical algorithms for the same problem, under some measure of complexity. Unfortunately, the algorithms of Ch. 2 apply to rather contrived problems that do not have known direct applications. We now describe a quantum algorithm that gives only a polynomial—more specifically, quadratic—speedup with respect to classical algorithms, but it applies to a large class of problems and finds many useful applications, both directly and as an algorithmic design tool. The algorithm is known as Grover’s search [89], and its generalization is known as amplitude amplification [43]. Amplitude amplification is widely used as part of many quantum algorithms. It also serves as the basis for amplitude estimation, a way of estimating probabilities quadratically faster than with classical Monte Carlo, and for quantum minimum finding. All these topics are discussed in this chapter.
We study the problem of determining if the mode of the output distribution of a quantum circuit given as a black-box is larger than a given threshold. We design a quantum algorithm for a promised version of this problem whose space complexity is logarithmic in the size of the domain of the distribution. Developing on top of that we further design an algorithm to estimate the largest probability among the outcomes of that circuit. This allows to revisit a few recently studied problems in the few-qubits scenario, namely kkk-distinctness and its gapped version, estimating the largest frequency in an array, and estimating the min-entropy of a distribution. In particular, our algorithm for kkk-distinctness on nnn-sized mmm-valued arrays requires O(log⁡n+log⁡m)O(\log n + \log m)O(logn+logm) qubits compared to Ω(poly(n))\Omega(poly(n))Ω(poly(n)) qubits required by all the previous algorithms, and its query complexity is optimal for k=Ω(n)k=\Omega(n)k=Ω(n). We also study reductions between the above problems and derive better lower bounds for some of them. The time-complexities of our algorithms have a small overhead over their query complexities making them efficiently implementable on currently available quantum backends.