Few Quantum Algorithms on Amplitude Distribution
- URL: http://arxiv.org/abs/2208.00162v2
- Date: Fri, 20 Jan 2023 18:53:50 GMT
- Title: Few Quantum Algorithms on Amplitude Distribution
- Authors: Debajyoti Bera and Tharrmashastha Sapv
- Abstract summary: Amplitude filtering is concerned with identifying basis-states in a superposition whose amplitudes are greater than a specified threshold.
Given the scarcity of qubits, the focus of this work is to design log-space algorithms for them.
- Score: 0.5584060970507505
- License: http://creativecommons.org/licenses/by/4.0/
- 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.
Related papers
- Quantum amplitude estimation from classical signal processing [0.0]
We show that the problem of amplitude estimation can be mapped directly to a problem in signal processing called direction of arrival estimation.
We create a phase-estimation free, parallel quantum amplitude estimation (QAE) algorithm with a total query complexity of $sim 4.9/varepsilon$ and a parallel query complexity of $sim 0.40/varepsilon$ at 95% confidence.
arXiv Detail & Related papers (2024-05-23T15:31:46Z) - Optimal Coherent Quantum Phase Estimation via Tapering [0.0]
Quantum phase estimation is one of the fundamental primitives that underpins many quantum algorithms.
We propose an improved version of the standard algorithm called the tapered quantum phase estimation algorithm.
Our algorithm achieves the optimal query complexity without requiring the expensive coherent median technique.
arXiv Detail & Related papers (2024-03-27T18:17:23Z) - On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
We study the problem of best-arm identification with fixed budget in multi-armed bandits with Bernoulli rewards.
For the problem with two arms, also known as the A/B testing problem, we prove that there is no algorithm that performs as well as the algorithm sampling each arm equally.
arXiv Detail & Related papers (2023-08-23T08:38:53Z) - Amplitude amplification-inspired QAOA: Improving the success probability
for solving 3SAT [55.78588835407174]
The amplitude amplification algorithm can be applied to unstructured search for satisfying variable assignments.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for solving 3SAT for Noisy Intermediate-Scale Quantum devices.
We introduce amplitude amplification-inspired variants of QAOA to improve the success probability for 3SAT.
arXiv Detail & Related papers (2023-03-02T11:52:39Z) - The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal
Control [0.0]
This note complements the paper "One-Way Ticket to Las Vegas and the Quantum Adversary"
I develop the ideas behind the adversary bound - universal algorithm duality therein in a different form, using the same perspective as Barnum-Saks-Szegedy.
arXiv Detail & Related papers (2022-11-29T15:25:45Z) - Amplitude Estimation from Quantum Signal Processing [0.30458514384586405]
Amplitude estimation algorithms are based on Grover's algorithm: alternating reflections about the input state and the desired outcome.
We find that quantum signal processing lets us estimate the amplitude in a more flexible way.
arXiv Detail & Related papers (2022-07-18T14:22:10Z) - Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
We propose an adaptive algorithm for interval estimation of amplitudes.
The proposed algorithm uses a similar number of quantum queries to achieve the same level of precision.
We rigorously prove that the number of oracle queries achieves $O(1/epsilon)$, i.e., a quadratic speedup over classical Monte Carlo sampling.
arXiv Detail & Related papers (2022-06-16T21:11:15Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits.
Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
arXiv Detail & Related papers (2021-11-14T21:49:58Z) - A Systematic Characterization of Sampling Algorithms for Open-ended
Language Generation [71.31905141672529]
We study the widely adopted ancestral sampling algorithms for auto-regressive language models.
We identify three key properties that are shared among them: entropy reduction, order preservation, and slope preservation.
We find that the set of sampling algorithms that satisfies these properties performs on par with the existing sampling algorithms.
arXiv Detail & Related papers (2020-09-15T17:28:42Z) - Beyond Worst-Case Analysis in Stochastic Approximation: Moment
Estimation Improves Instance Complexity [58.70807593332932]
We study oracle complexity of gradient based methods for approximation problems.
We focus on instance-dependent complexity instead of worst case complexity.
Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation.
arXiv Detail & Related papers (2020-06-08T09:25:47Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc.
Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource.
We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
arXiv Detail & Related papers (2020-05-09T02:48:23Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.