Information Technology Reference
In-Depth Information
efficient quantum algorithms for extensions of the quantum Fourier
transform: to the approximate quantum Fourier transform (Coppersmith
[174]), over various domains (Griffiths, Niu [175], Hoyer [176]), over
symmetric groups (Beals [177]), and over certain nonabelian groups
(Pueschel, Roetteler, Bet [178]). Vedral, Barenco, Ekert [179] give efficient
quantum networks for elementary arithmetic operations using the quan-
tum Fourier transform. Grigoriev [180] used the quantum Fourier trans-
form to test shift-equivalence of polynomials.
Quantum Factoring. The most notable algorithmic result in QC to date is
the quantum algorithm of Shor [181, 182] for discrete logarithm and
integer factorization in polynomial time (with modest amplitude precision).
(Also see a review of the algorithm by Ekert and Jozsa [183].) Shor's
algorithm uses an efficient reduction (due to Miller [184]) from integer
factoring to the problem of approximately computing the period (length of
a orbit) within an integer ring. Shor approximates the period by repeated
use of a quantum Fourier transform over an integer ring and greatest
common divisor computations. There has been further considerable work
on Shor's quantum factoring algorithm: Zalka [185] improved the time
complexity; Beckman et al. [186] describe its execution on quantum
networks with small size and depth; Obenland, Despain [187], Plenio,
Knight [188] consider the feasibility of executing Shor's quantum factoring
algorithm on various quantum computer architectures. (The latter provide
somewhat pessimistic lower bounds for the factorization time of large
numbers on a quantum computer in the presence of decoherance errors.)
[189] describes a 7-qubit demonstration of Shor's factorization algorithm
using nuclear magnetic resonance. Kitaev [190] gave an independent
derivation of Shor's factoring result using a reduction to find an abelian
stabilizer.
Quantum Search. Another significant efficient QC algorithmic result is the
algorithm of Grover [191], which searches within a database of size N in
time
p . (An interesting property of Grover's algorithm for search is its
similarity to the quantum Zeno affect technique for quantum measurement
[94, 95]. In particular, the algorithm also uses O ð N
p
Þ stages of unitary
operations, each quite similar to a stage of the quantum Zeno sensing
method.) Grover refined his result to require only a single query [192] and
to use almost any unitary transformation [193]; Zalka [194] showed
Grover's algorithm cannot be further asymptotically sped up and so is
optimal for database search; and Pati [195] gave further improvements to
the bounds. Biron et al. [196] extended Grover's algorithm to arbitrary
initial amplitude distribution. Cockshott [197] gave fast quantum algo-
rithms for executing more general operations on relational databases, and
Benjamin, Johnson [198] discuss the use of Grover's algorithm and related
quantum algorithms for other data processing problems. Farhi et al. [199]
showed that Grover's algorithm could not be extend to quickly determine
 
Search WWH ::




Custom Search