Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR14-151 | 26th April 2016 11:06

Applications of Quantum Amplitude Amplification


Revision #1
Authors: Debajyoti Bera
Accepted on: 26th April 2016 11:06
Downloads: 183


Amplitude amplification is a central tool used in Grover’s quantum search algorithm and has been used in various forms in numerous quantum algorithms since then. It has been shown to completely eliminate one-sided error of quantum search algorithms where input is accessed in the form of black-box queries. We generalize amplitude amplification for decision problems in the familiar form where input is accessed in the form of initial states of quantum circuits and where arbitrary projective measurements may be used to ascertain success or failure. This generalization allows us to derive interesting applications of amplitude amplification for distinguishing between two given distributions based on their samples, detection of faults in quantum circuits and eliminating error of one and two-sided quantum algorithms with exact errors.

Changes to previous version:

1. Generalized technique.
2. Added two-sided error amplification.
3. Added applications.


TR14-151 | 13th November 2014 19:48

Quantum One-Sided Exact Error Algorithms

Authors: Debajyoti Bera
Publication: 13th November 2014 20:10
Downloads: 597


We define a complexity class for randomized algorithms with one-sided error that is exactly equal to a constant (unlike the usual definitions, in which the error is only bounded above or below by a constant). We show that the corresponding quantum classes (one each for a different error probability) are in fact all equivalent to each other and to $\mathbf{EQP}$, the quantum analogue of $\mathbf{P}$. The technique used is a form of quantum amplitude amplification.

ISSN 1433-8092 | Imprint