Vol.5 No.6 September 1, 2005
Research Articles:
Surface-electrode architecture for ion-trap quantum information processing  (pp419-439)
         J. Chiaverini, R.B. Blakestad, J. Britton, J.D. Jost, C. Langer, D. Leibfried, R. Ozeri and D.J. Wineland
We investigate a surface-mounted electrode geometry for miniature linear radio frequency Paul ion traps. The electrodes reside in a single plane on a substrate, and the pseudopotential minimum of the trap is located above the substrate at a distance on the order of  the electrodes' lateral extent or separation. This architecture provides the possibility to apply standard microfabrication principles to the construction of multiplexed ion traps, which may be of particular importance in light of recent proposals for large-scale quantum computation based on individual trapped ions.

A linear-size quantum circuit for addition with no ancillary qubits (pp440-448)
         Y. Takahashi and N. Kunihiro
We construct a quantum circuit for addition of two $n$-bit binary numbers that uses no ancillary qubits. The circuit is based on the ripple-carry approach. The depth and size of the circuit are $O(n)$. This is an affirmative answer to the question of Kutin \cite{Kutin} as to whether a linear-depth quantum circuit for addition can be constructed without ancillary qubits using the ripple-carry approach. We also construct quantum circuits for addition modulo $2^n$, subtraction, and comparison that use no ancillary qubits by modifying the circuit for addition.

Two slightly-entangled NP-complete problems (pp449-455)
         R. Orus
We perform a mathematical analysis of the classical computational complexity of two genuine quantum-mechanical problems, which are inspired in the calculation of the expected magnetizations and the entanglement between subsystems for a quantum spin system. These problems, which we respectively call SES and SESSP, are specified in terms of pure slightly-entangled quantum states of $n$ qubits, and rigorous mathematical proofs that they belong to the NP-Complete complexity class are presented. Both SES and SESSP are, therefore, computationally equivalent to the relevant $3$-SAT problem, for which an efficient algorithm is yet to be discovered.

Secure assisted quantum computation (pp456-466)
         A.M.  Childs
Suppose Alice wants to perform some computation that could be done quickly on a quantum computer, but she cannot do universal quantum computation. Bob can do universal quantum computation and claims he is willing to help, but Alice wants to be sure that Bob cannot learn her input, the result of her calculation, or perhaps even the function she is trying to compute. We describe a simple, efficient protocol by which Bob can help Alice perform the computation, but there is no way for him to learn anything about it. We also discuss techniques for Alice to detect whether Bob is honestly helping her or if he is introducing errors.

Transformation of quantum states using uniformly controlled rotations (pp467-473)
         M. Mottonen, J. J. Vartiainen, V. Bergholm and M. M. Salomaa
 We consider a unitary transformation which maps any given pure state of an $n$-qubit quantum register into another one. This transformation has applications in the initialization of a quantum computer, and also in some quantum algorithms. Employing uniformly controlled rotations, we present a quantum circuit of $2^{n+2}-4n-4$ CNOT gates and $2^{n+2}-5$ one-qubit elementary rotations that effects the state transformation. The complexity of the circuit is noticeably lower than the previously published results. Moreover, we present an analytic expression for the rotation angles needed for the transformation.

Optimized quantum implementation of elliptic curve arithmetic over binary fields  (pp474-491)
         P.R. Kaye
Shor's quantum algorithm for discrete logarithms applied to elliptic curve groups forms the basis of a ``quantum attack'' of elliptic curve cryptosystems. To implement this algorithm on a quantum computer requires the efficient implementation of the elliptic curve group operation. Such an implementation requires we be able to compute inverses in the underlying field. In \cite{PZ03}, Proos and Zalka show how to implement the extended Euclidean algorithm to compute inverses in the prime field $\GF(p)$. They employ a number of optimizations to achieve a running time of $O(n^2)$, and a space-requirement of $O(n)$ qubits, where $n$ is the number of bits in the binary representation of $p$ (there are some trade-offs that they make, sacrificing a few extra qubits to reduce running-time). In practice, elliptic curve cryptosystems often use curves over the binary field $\GF(2^m)$. In this paper, I show how to implement the extended Euclidean algorithm for polynomials to compute inverses in $\GF(2^m)$. Working under the assumption that qubits will be an `expensive' resource in realistic implementations, I optimize specifically to reduce the qubit space requirement, while keeping the running-time polynomial. The implementation here differs from that in $\cite{PZ03}$ for $\GF(p)$, and we are able to take advantage of some properties of the binary field $\GF(2^m)$. I also optimize the overall qubit space requirement for computing the group operation for elliptic curves over $\GF(2^m)$ by decomposing the group operation to make it ``piecewise reversible'' (similar to what is done in \cite{PZ03} for curves over $\GF(p)$).

Physically-motivated dynamical algorithms  for the graph isomorphism problem (pp492-506)
         S.-Y. Shiau, R. Joynt and S.N. Coppersmith
The graph isomorphism problem (GI) plays a central role in the theory of computational complexity and has importance in physics and chemistry as well \cite{kobler93,fortin96}. No polynomial-time algorithm for solving GI is known. We investigate classical and quantum physics-based polynomial-time algorithms for solving the graph isomorphism problem in which the graph structure is reflected in the behavior of a dynamical system. We show that a classical dynamical algorithm proposed by Gudkov and Nussinov \cite{gudkov02} as well as its simplest quantum generalization fail to distinguish pairs of non-isomorphic strongly regular graphs. However, by combining the algorithm of Gudkov and Nussinov with a construction proposed by Rudolph \cite{rudolph02} in which one examines a graph describing the dynamics of two particles on the original graph, we find an algorithm that successfully distinguishes all pairs of non-isomorphic strongly regular graphs that we tested with up to 29 vertices.

Mini- tutorial:
A simple proof of the strong subadditivity inequality (pp507-513)
         M.A. Nielsen and D. Petz
 Arguably the deepest fact known about the von~Neumann entropy, the strong subadditivity inequality is a potent hammer in the quantum information theorist's toolkit. This short tutorial describes a simple proof of strong subadditivity due to Petz [Rep. on Math. Phys. \textbf{23} (1), 57--65 (1986)]. It assumes only knowledge of elementary linear algebra and quantum mechanics.

back to QIC online Front page