QIC Abstracts

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