Vol.2 No.3 April. 15, 2002 (print: May 15,
2002)
Finding cliques by quantum
adiabatic evolution
(pp181-191)
A.M. Childs, E. Farhi, J. Goldstone, and
S. Gutmann
Quantum adiabatic evolution provides a general technique
for the solution of combinatorial search problems on quantum
computers. We present the results of a numerical study of a particular
application of quantum adiabatic evolution, the problem of finding the
largest clique in a random graph. An n-vertex random graph has
each edge included with probability 1/2, and a clique is a completely
connected subgraph. There is no known classical algorithm that finds the
largest clique in a random graph with high probability and runs in a
time polynomial in n. For the small graphs we are able to
investigate ($n \le 18$), the quantum algorithm appears to require only
a quadratic run time. Quantum algorithm
for measuring the eigenvalues of UÄU-1
for a black-box unitary
transformation U
(pp192-197)
D. Janzing and T. Beth
Estimating the eigenvalues of a
unitary transformation U by standard phase estimation requires
the implementation of controlled-U-gates which are not available
if U is only given as a black box. We show that a simple trick allows to
measure eigenvalues of
U\otimesU^\deggar
even in this case. Running the
algorithm several times allows therefore to estimate the autocorrelation
function of the density of eigenstates of U. This can be applied
to find periodicities in the energy spectrum of a quantum system with
unknown Hamiltonian if it can be coupled to a quantum computer.
Finding cliques by quantum
adiabatic evolution
(pp181-191)
A.M. Childs, E. Farhi, J. Goldstone, and
S. Gutmann
Quantum adiabatic evolution provides a general technique
for the solution of combinatorial search problems on quantum
computers. We present the results of a numerical study of a particular
application of quantum adiabatic evolution, the problem of finding the
largest clique in a random graph. An n-vertex random graph has
each edge included with probability 1/2, and a clique is a completely
connected subgraph. There is no known classical algorithm that finds the
largest clique in a random graph with high probability and runs in a
time polynomial in n. For the small graphs we are able to
investigate ($n \le 18$), the quantum algorithm appears to require only
a quadratic run time. Quantum algorithm
for measuring the energy of n qubits with unknown pair-interactions
(pp198-207)
D. Janzing
The well-known algorithm for quantum phase estimation
requires that the considered unitary is available as a conditional
transformation depending on the quantum state of an ancilla register. We
present an algorithm converting an unknown n-qubit
pair-interaction Hamiltonian into a conditional one such that standard
phase estimation can be applied to measure the energy. Our essential
assumption is that the considered system can be brought into interaction
with a quantum computer. For large n the algorithm could still be
applicable for estimating the density of energy states and might
therefore be useful for finding energy gaps in solid states. Purification of entangled coherent states
(pp208-221)
H. Jeong and M.S. Kim
We suggest an entanglement purification scheme for
mixed entangled coherent states using 50-50 beam splitters and
photodetectors. This scheme is directly applicable for mixed entangled
coherent states of the Werner type, and can be useful for general mixed
states using additional nonlinear interactions. We apply our scheme to
entangled coherent states decohered in a vacuum environment and find the
decay time until which they can be purified. Numerical
analysis of entanglement properties of density matrices
in
C2ÄC2
systems
(pp222-239)
R.V. Ramos and A. Karlsson
Quantum
entanglement is an enigmatic and powerful property that has attracted
much attention due to its usefulness in new ways of communications, like
quantum teleportation and quantum key distribution. Much effort has been
done to quantify entanglement. Indeed, there exist some well-established
separability criterion and analytical formulas for the entanglement of
bipartite systems. In both, the crucial element is the partial transpose
of the density matrix. In this paper, we show numerically that one can
also have information about the entanglement of bipartite
state, in C2ÄC2,
without looking at the partial transpose. We furthermore study
properties of disentanglement operation, as well as properties of the
relative entropy. Equivalence
classes of non-local unitary operations
(pp240-254)
W. Duer and J.I. Cirac
We study when a multipartite non--local unitary
operation can deterministically or probabilistically simulate another
one when local operations of a certain kind ---in some cases including
also classical communication--- are allowed. In the case of
probabilistic simulation and allowing for arbitrary local operations, we
provide necessary and sufficient conditions for the simulation to be
possible. Deterministic and probabilistic interconversion under certain
kinds of local operations are used to define equivalence relations
between gates. In the probabilistic, bipartite case this induces a
finite number of classes. In multiqubit systems, however, two unitary
operations typically cannot simulate each other with non-zero
probability of success. We also show which kind of entanglement can be
created by a given non--local unitary operation and generalize our
results to arbitrary operators.
QIC Webcorner:
Update
(pp255-256)
P. Kok
back to QIC online Front page
|