Vol.4 No.4 July 05, 2004
Research and Review Articles:
Implementation of Shor's algorithm on a linear nearest neighbour qubit array  (pp237-251) 
        A.G. Fowler, S.J. Devitt and L.C.L. Hollenberg
Shor's algorithm, which given appropriate hardware can factorise an integer N in a time polynomial in its binary length L, has arguably spurred the race to build a practical quantum computer. Several different quantum circuits implementing Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits within the computer can be interacted. While some quantum computer architectures possess this property, many promising proposals are best suited to realising a single line of qubits with nearest neighbour interactions only. In light of this, we present a circuit implementing Shor's factorisation algorithm designed for such a linear nearest neighbour architecture. Despite the interaction restrictions, the circuit requires just 2L+4 qubits and to leading order requires 8L^4 2-qubit gates arranged in a circuit of depth 32L^3 --- identical to leading order to that possible using an architecture that can interact arbitrary pairs of qubits.

Connections between relative entropy of entanglement and geometric measure of entanglement  (pp252-272) 
        T.-C. Wei, M. Ericsson, P.M. Goldbart and W.J. Munro
As two of the most important entanglement measures---the entanglement of formation and the entanglement of distillation---have so far been limited to bipartite settings, the study of other entanglement measures for multipartite systems appears necessary. Here, connections between two other entanglement measures---the relative entropy of entanglement and the geometric measure of entanglement---are investigated. It is found that for arbitrary pure states the latter gives rise to a lower bound on the former. For certain pure states, some bipartite and some multipartite, this lower bound is saturated, and thus their relative entropy of entanglement can be found analytically in terms of their known geometric measure of entanglement. For certain mixed states, upper bounds on the relative entropy of entanglement are also established. Numerical evidence strongly suggests that these upper bounds are tight, i.e., they are actually the relative entropy of entanglement.

Self testing quantum apparatus  (pp273-286) 
        D. Mayers and A. Yao
We study, in the context of quantum information and quantum communication, a configuration of devices that includes (1) a source of some unknown bipartite quantum state that is claimed to be the Bell state $\Phi^+$ and (2) two spatially separated but otherwise unknown measurement apparatus, one on each side, that are each claimed to execute an orthogonal measurement at an angle $\theta \in \{-\pi/8, 0, \pi/8\}$ that is chosen by the user. We show that, if the nine distinct probability distributions that are generated by the self checking configuration, one for each pair of angles, are consistent with the specifications, the source and the two measurement apparatus are guaranteed to be identical to the claimed specifications up to a local change of basis on each side. We discuss the connection with quantum cryptography.

Cluster states, algorithms and graphs  (pp287-324) 
        D. Schlingemann
The present paper is concerned with the concept of the one-way quantum computer, beyond binary-systems, and its relation to the concept of stabilizer quantum codes. This relation is exploited to analyze a particular class of quantum algorithms, called graph algorithms, which correspond in the binary case to the Clifford group part of a network and which can efficiently be implemented on a one-way quantum computer. These algorithms can ``completely be solved" in the sense that the manipulation of quantum states in each step can be computed explicitly. Graph algorithms are precisely those which implement encoding schemes for graph codes. Starting from a given initial graph, which represents the underlying resource of multipartite entanglement, each step of the algorithm is related to a explicit transformation on the graph.

back to QIC online Front page