Non-Boolean Quantum Amplitude Amplification and Quantum Mean Estimation
- URL: http://arxiv.org/abs/2102.04975v1
- Date: Tue, 9 Feb 2021 17:48:38 GMT
- Title: Non-Boolean Quantum Amplitude Amplification and Quantum Mean Estimation
- Authors: Prasanth Shyamsundar
- Abstract summary: This paper generalizes the quantum amplitude amplification and amplitude estimation algorithms to work with non-boolean oracles.
The eigenvalues $exp(ivarphi(x)$ of a non-boolean oracle are not restricted to be $pm 1$.
Two new oracular algorithms based on such non-boolean oracles are introduced.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper generalizes the quantum amplitude amplification and amplitude
estimation algorithms to work with non-boolean oracles. The action of a
non-boolean oracle $U_\varphi$ on an eigenstate $|x\rangle$ is to apply a
state-dependent phase-shift $\varphi(x)$. Unlike boolean oracles, the
eigenvalues $\exp(i\varphi(x))$ of a non-boolean oracle are not restricted to
be $\pm 1$. Two new oracular algorithms based on such non-boolean oracles are
introduced. The first is the non-boolean amplitude amplification algorithm,
which preferentially amplifies the amplitudes of the eigenstates based on the
value of $\varphi(x)$. Starting from a given initial superposition state
$|\psi_0\rangle$, the basis states with lower values of $\cos(\varphi)$ are
amplified at the expense of the basis states with higher values of
$\cos(\varphi)$. The second algorithm is the quantum mean estimation algorithm,
which uses quantum phase estimation to estimate the expectation
$\langle\psi_0|U_\varphi|\psi_0\rangle$, i.e., the expected value of
$\exp(i\varphi(x))$ for a random $x$ sampled by making a measurement on
$|\psi_0\rangle$. It is shown that the quantum mean estimation algorithm offers
a quadratic speedup over the corresponding classical algorithm. Both algorithms
are demonstrated using simulations for a toy example. Potential applications of
the algorithms are briefly discussed.
Related papers
- Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer [7.319050391449301]
Trace distance and infidelity, as basic measures of the closeness of quantum states, are commonly used in quantum state discrimination, certification, and tomography.
We present a quantum algorithm that estimates the trace distance and square root fidelity between pure states to within additive error $varepsilon$, given sample access to their identical copies.
arXiv Detail & Related papers (2024-10-28T16:48:21Z) - Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
We revisit the sample and computational complexity of completing a rank-1 tensor in $otimes_i=1N mathbbRd$.
We present a characterization of the problem which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems.
arXiv Detail & Related papers (2024-08-10T04:26:19Z) - Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
We consider the preparation for $n$-qubit sparse quantum states with $s$ non-zero amplitudes and propose two algorithms.
The first algorithm uses $O(ns/log n + n)$ gates, improving upon previous methods by $O(log n)$.
The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path.
arXiv Detail & Related papers (2024-04-08T02:13:40Z) - Do you know what q-means? [50.045011844765185]
Clustering is one of the most important tools for analysis of large datasets.
We present an improved version of the "$q$-means" algorithm for clustering.
We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
arXiv Detail & Related papers (2023-08-18T17:52:12Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$.
Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
arXiv Detail & Related papers (2023-07-13T18:59:28Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis.
Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
arXiv Detail & Related papers (2021-12-15T21:44:05Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
We learn the set of $epsilon$-optimal goal-conditioned policies attaining all states that are incrementally reachable within $L$ steps.
DisCo is the first algorithm that can return an $epsilon/c_min$-optimal policy for any cost-sensitive shortest-path problem.
arXiv Detail & Related papers (2020-12-29T14:06:09Z) - Low depth algorithms for quantum amplitude estimation [6.148105657815341]
We design and analyze two new low depth algorithms for amplitude estimation (AE)
These algorithms bring quantum speedups for Monte Carlo methods closer to realization.
arXiv Detail & Related papers (2020-12-06T18:39:20Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
We present a quantum algorithm to solve systems of linear equations of the form $Amathbfx=mathbfb$.
The algorithm achieves an exponential improvement with respect to $N$ over classical methods.
arXiv Detail & Related papers (2020-09-09T18:00:09Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings.
In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$.
We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
arXiv Detail & Related papers (2020-02-25T19:18:36Z)
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.