Vol.7 No.4 May 1, 2007

Review: 
Quantum computaton from a quantum logical perspective (pp281-296) PDF
          J. Bub
It is well-known that Shor's factorization algorithm, Simon's period-finding algorithm, and Deutsch's original XOR algorithm can all be formulated as solutions to a hidden subgroup problem. Here the salient features of the information-processing in the three algorithms are presented from a different perspective, in terms of the way in which the algorithms exploit the non-Boolean quantum logic represented by the projective geometry of Hilbert space. From this quantum logical perspective, the XOR algorithm appears directly as a special case of Simon's algorithm, and all three algorithms can be seen as exploiting the non-Boolean logic represented by the subspace structure of Hilbert space in a similar way. Essentially, a global property of a function (such as a period, or a disjunctive property) is encoded as a subspace in Hilbert space representing a quantum proposition, which can then be efficiently distinguished from alternative propositions, corresponding to alternative global properties, by a measurement (or sequence of measurements) that identifies the target proposition as the proposition represented by the subspace containing the final state produced by the algorithm.

Research Articles: 
Noise threshold for a fault-tolerant two-dimensional lattice architecture (pp297-318) PDF
          K.M. Svore, D.P. DiVincenzo, and B.M. Terhal
We consider a model of quantum computation in which the set of operations is limited to nearest-neighbor interactions on a 2D lattice. We model movement of qubits with noisy \SWAP\ operations. For this architecture we design a fault-tolerant coding scheme using the concatenated $[[7,1,3]]$ Steane code. Our scheme is potentially applicable to ion-trap and solid-state quantum technologies. We calculate a lower bound on the noise threshold for our local model using a detailed failure probability analysis. We obtain a threshold of $1.85 \times 10^{-5}$ for the local setting, where memory error rates are one-tenth of the failure rates of gates, measurement, and preparation steps. For the analogous nonlocal setting, we obtain a noise threshold of $3.61 \times 10^{-5}$. Our results thus show that the additional \SWAP\ operations required to move qubits in the local model affect the noise threshold only moderately.

Winning strategies for pseudo-telepathy games using single non-local box (pp319-328) PDF
          S. Kunkri, G. Kar, S. Ghosh, and A. Roy  
Using a single NL-box, a winning strategy is given for the impossible colouring pseudo-telepathy game for the set of vectors having Kochen-Specker property in four dimension. A sufficient condition given regarding the structure of the impossible colouring pseudo-telepathy game for general $d$-dimension. A winning strategy for this game is then described with single use of NL-box.

A simple participant attack on the Bradler-Dusek protocol (pp329-334) PDF
          F. Gao, S. Qin, Q. Wen, and F. Zhu   
The ring-arrangement quantum secret sharing protocol in the paper [K. Br\'{a}dler and M. Du\v{s}ek (2004) {\textit{J. Opt. B: Quantum Semiclass. Opt.}} {\textbf{6}} 63] is analyzed and it is shown that this protocol is secure for any eavesdropper except for a dishonest participant. For example, by a special strategy, Bob can steal Charlie's portion of information without being detected and then recover Alice's secret by himself. We give a description of this strategy and point out a possible way to improve the protocol to stand against this attack.

Computational complexity of the quantum separability problem (pp335-370) PDF
          L.M. Ioannou  
Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or \emph{separable}, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper's main focus. I then give a thorough treatment of the problem's relationship with NP, NP-completeness, and co-NP. I also discuss extensions of Gurvits' NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem \cite{DPS02,DPS04,qphCKMR06}; and the entanglement-witness search (via interior-point algorithms and global optimization) \cite{ITCE04,IT06}. These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.

Mutually unbiased bases and orthogonal  decompositions of Lie algebras (pp371-382) PDF
          P.O. Boykin, M. Sitharam, P.H. Tiep, and P. Wocjan
We establish a connection between the problem of constructing maximal collections of mutually unbiased bases (MUBs) and an open problem in the theory of Lie algebras. More precisely, we show that a collection of $\mu$ MUBs in $\K^n$ gives rise to a collection of $\mu$ Cartan subalgebras of the special linear Lie algebra $sl_n(\K)$ that are pairwise orthogonal with respect to the Killing form, where $\K=\R$ or $\K=\C$. In particular, a complete collection of MUBs in $\C^n$ gives rise to a so-called orthogonal decomposition (OD) of $sl_n(\C)$. The converse holds if the Cartan subalgebras in the OD are also $\dag$-closed, i.e., closed under the adjoint operation. In this case, the Cartan subalgebras have unitary bases, and the above correspondence becomes equivalent to a result of \cite{bbrv02} relating collections of MUBs to collections of maximal commuting classes of unitary error bases, i.e., orthogonal unitary matrices. This connection implies that for $n\le 5$ an essentially unique complete collection of MUBs exists. We define \emph{monomial MUBs}, a class of which all known MUB constructions are members, and use the above connection to show that for $n=6$ there are at most three monomial MUBs.

The quantum Fourier transform on a linear nearest neighbor architecture (pp383-391) PDF
          Y. Takahashi, N. Kunihiro, and K. Ohta
We show how to construct an efficient quantum circuit for computing a good approximation of the quantum Fourier transform on a linear nearest neighbor architecture. The constructed circuit uses no ancillary qubits and its depth and size are $O(n)$ and $O(n\log n)$, respectively, where $n$ is the length of the input. The circuit is useful for decreasing the size of Fowler et al.'s quantum circuit for Shor's factoring algorithm on a linear nearest neighbor architecture.

General classes of impossible operations through the existence of incomparable states (pp392-400) PDF
          I. Chattopadhyay and D. Sarkar
In this work we show that the most general class of anti-unitary operators are nonphysical in nature through the existence of incomparable pure bipartite entangled states. It is also shown that a large class of inner-product-preserving operations defined only on the three qubits having spin-directions along x,y and z are impossible. If we perform such an operation locally on a particular pure bipartite state then it will exactly transform to another pure bipartite state that is incomparable with the original one. As subcases of the above results we find the nonphysical nature of universal exact flipping operation and existence of universal Hadamard gate. Beyond the information conservation in terms of entanglement, this work shows how an impossible local operation evolve with the joint system in a nonphysical way.
 

back to QIC online Front page