ECCC-Report TR14-151https://eccc.weizmann.ac.il/report/2014/151Comments and Revisions published for TR14-151en-usSat, 10 Mar 2018 08:59:41 +0200
Revision 2
| Amplitude Amplification for Operator Identification and Randomized Classes |
Debajyoti Bera
https://eccc.weizmann.ac.il/report/2014/151#revision2Amplitude 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.Sat, 10 Mar 2018 08:59:41 +0200https://eccc.weizmann.ac.il/report/2014/151#revision2
Revision 1
| Applications of Quantum Amplitude Amplification |
Debajyoti Bera
https://eccc.weizmann.ac.il/report/2014/151#revision1Amplitude 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.
Tue, 26 Apr 2016 11:06:37 +0300https://eccc.weizmann.ac.il/report/2014/151#revision1
Paper TR14-151
| Quantum One-Sided Exact Error Algorithms |
Debajyoti Bera
https://eccc.weizmann.ac.il/report/2014/151We 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.Thu, 13 Nov 2014 20:10:47 +0200https://eccc.weizmann.ac.il/report/2014/151