|
| related topics |
| {algorithm, log, probability} |
| {state, algorithm, problem} |
| {qubit, qubits, gate} |
| {error, code, errors} |
| {measurement, state, measurements} |
| {cos, sin, state} |
| {phase, path, phys} |
| {classical, space, random} |
| {states, state, optimal} |
| {state, phys, rev} |
| {wave, scattering, interference} |
| {information, entropy, channel} |
|
A new algorithm for fixed point quantum search
Tathagat Tulsi, Lov Grover, Apoorva Patel
abstract: The standard quantum search lacks a feature, enjoyed by many classical
algorithms, of having a fixed point, i.e. monotonic convergence towards the
solution. Recently a fixed point quantum search algorithm has been discovered,
referred to as the Phase-$\pi/3$ search algorithm, which gets around this
limitation. While searching a database for a target state, this algorithm
reduces the error probability from $\epsilon$ to $\epsilon^{2q+1}$ using $q$
oracle queries, which has since been proved to be asymptotically optimal. A
different algorithm is presented here, which has the same worst-case behavior
as the Phase-$\pi/3$ search algorithm but much better average-case behavior.
Furthermore the new algorithm gives $\epsilon^{2q+1}$ convergence for all
integral $q$, whereas the Phase-$\pi/3$ search algorithm requires $q$ to be
$(3^{n}-1)/2$ with $n$ a positive integer. In the new algorithm, the operations
are controlled by two ancilla qubits, and fixed point behavior is achieved by
irreversible measurement operations applied to these ancillas. It is an example
of how measurement can allow us to bypass some restrictions imposed by
unitarity on quantum computing.
- oai_identifier:
- oai:arXiv.org:quant-ph/0505007
- categories:
- quant-ph
- comments:
- 12 pages, 4 figures. Accepted for publication in QIC
- arxiv_id:
- quant-ph/0505007
- report_no:
- IISc-CHEP-5/05
- created:
- 2005-05-02
- updated:
- 2006-03-21
Full article ▸
|
|
| related documents |
| 0511272v1 |
| 0201152v1 |
| 9905026v1 |
| 9706003v4 |
| 9903071v1 |
| 0207131v1 |
| 0302022v1 |
| 0011052v2 |
| 0010034v1 |
| 0304131v1 |
| 0206089v2 |
| 0504067v3 |
| 0403140v2 |
| 0106152v1 |
| 0410042v1 |
| 0010021v1 |
| 9907020v2 |
| 0609220v1 |
| 0607148v3 |
| 0303175v1 |
| 0609166v1 |
| 0210077v1 |
| 0609160v1 |
| 0508156v3 |
| 0612052v2 |
|