Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #2 to TR14-151 | 10th March 2018 08:59

Amplitude Amplification for Operator Identification and Randomized Classes


Revision #2
Authors: Debajyoti Bera
Accepted on: 10th March 2018 08:59
Downloads: 778


Amplitude amplification (AA) is tool of choice for quantum algorithm designers to increase the success probability of query algorithms that reads its input in the form of oracle gates. Geometrically speaking, the technique can be understood as rotation in a specific two- dimensional space. We study and use a generalized form of this rotation operator to design algorithms in a geometric manner. Specifically, we apply AA to algorithms that take their input in the form of input states and in which rotations with different angles and directions are used in a unified manner. We show that AA can be used to sequentially discriminate between two unitary operators, both without error and with bounded-error, in an asymptotically optimal manner. We also show how to reduce error probability in one and two-sided bounded error algorithms more efficiently than the usual parallel repetitions technique; in particular, errors can be completely eliminated from the exact error algorithms.

Changes to previous version:

Entirely rewritten.

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


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


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