Non-Boolean quantum amplitude amplification and quantum mean estimation

DOI10.1007/S11128-023-04146-3MaRDI QIDQ6176970zbMATH OpenOpenAlexFDO

Authors Prasanth Shyamsundar

Publication date 16 January 2024

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.04975, https://www.osti.gov/biblio/1780589

zbMATH Keywords

Grover's algorithmquantum algorithmquantum machine learningquantum speedupstate overlap

Mathematics Subject Classification ID

Quantum computation (81P68)

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_{v}arphi$ on an eigenstate $|xangle$ is to apply a state-dependent phase-shift $varphi(x)$. Unlike boolean oracles, the eigenvalues $exp(ivarphi(x))$ of a non-boolean oracle are not restricted to be $pm1$. 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 $|ps{i}_{0}angle$, 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 $langleps{i}_0|U_{v}arphi|ps{i}_{0}angle$, i.e., the expected value of $exp(ivarphi(x))$ for a random $x$ sampled by making a measurement on $|ps{i}_{0}angle$. 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.

Recommendations

• scientific article; zbMATH DE number 2103524
• Amplitude estimation without phase estimation
• Quantum Probability Oracles & Multidimensional Amplitude Estimation
• A different Deutsch-Jozsa
• Generalized quantum counting algorithm for non-uniform amplitude distribution

Cites work

• A NEW QUANTUM ALGORITHM FOR SOLVING THE MINIMUM SEARCHING PROBLEM
• A polynomial quantum algorithm for approximating the Jones polynomial
• Amplitude estimation without phase estimation
• Dynamic Grover search: applications in recommendation systems and optimization problems
• Grover's Quantum Algorithm Applied to Global Optimization
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• Quantum algorithms revisited
• Quantum cryptanalysis of hash and claw-free functions
• Quantum optimization
• Quantum search with certainty based on modified Grover algorithms: optimum choice of parameters
• Solving NP-Complete Problems with Quantum Search
• Strengths and Weaknesses of Quantum Computing
• Testing product states, quantum Merlin-Arthur games and tensor optimization
• The quantum query complexity of approximating the median and related statistics

Cited in

(2)

• Quantum chosen-ciphertext attacks based on Simon's algorithm against unified structures
• High-entanglement capabilities for variational quantum algorithms: the Poisson equation case

This page was built for publication: Non-Boolean quantum amplitude amplification and quantum mean estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6176970)