Fault-tolerant renormalization group decoder for abelian topological codes (pp0721-0740)
          Guillaume Duclos-Cianci and David Poulin
We present a three-dimensional generalization of a renormalization group decoding algorithm for topological codes with Abelian anyonic excitations that we introduced for two dimensions in \cite{DP09a,DP10a}. We also provide a complete detailed description of the structure of the algorithm, which should be sufficient for anyone interested in implementing it. This 3D implementation extends our previous 2D algorithm by incorporating a failure probability of the syndrome measurements, i.e., it enables fault-tolerant decoding. We report a fault-tolerant storage threshold of $\sim1.9(4)\%$ for Kitaev's toric code subject to a 3D bit-flip channel (i.e. including imperfect syndrome measurements). This number is to be compared with the $2.9\%$ value obtained via perfect matching \cite{H04a}. The 3D generalization inherits many properties of the 2D algorithm, including a complexity linear in the space-time volume of the memory, which can be parallelized to logarithmic time.

Dynamics of coupled cavity arrays embedded in a non-Markovian bath (pp0741-0756)
          Xinyu Zhao, Jun Jing, J.Q. You, and Ting Yu
In this paper, the non-Markovian quantum dynamics of a coupled $N$-cavity model is studied based on the quantum state diffusion (QSD) approach. The time-local Di\'{o}si-Gisin-Strunz equation and the corresponding exact master equation are derived for the model consisting of a coupled cavity array. The resulting QSD equation serves as a stochastic solution to a genuine $N$-partite continuous-variable (CV) system. Several non-Markovian effects are studied in two interesting examples -- two-cavity and three-cavity, under different boundary conditions. We have shown that the environment-memory can facilitate the cat-like state transfer from one cavity to another in the case of a strongly non-Markovian environment.

Unitary operation attack and the improvement on probabilistic quantum key distribution (pp0757-0762)
          Tzu-Han Lin, Chun-Wei Yang, and Tzonelih Hwang
This study points out that a malicious communicant in Hwang et al.\textquoteright{}s probabilistic quantum key distribution (PQKD) protocol can manipulate the secret key without being detected by using the unitary operation attack. Accordingly, the security requirements of a PQKD protocol,
i.e., unpredictability and fairness, cannot be satisfied in their protocol. A possible solution is also provided to solve the problem.

Quantum circuits for simple periodic functions (pp0763-0776)
          Omar Gamel and Daniel F.V. James
Periodic functions are of special importance in quantum computing, particularly in applications of Shor's algorithm. We explore methods of creating circuits for periodic functions to better understand their properties. We introduce a method for constructing the circuit for a simple monoperiodic function, that is one-to-one within a single period, of a given period $p$. We conjecture that to create a simple periodic function of period $p$, where $p$ is an $n$-bit number, one needs at most $n$ Toffoli gates.

Long distance entanglement generation through coherent directed transport of Neutral atoms in unmodulated optical lattices (pp0777-0789)
          Morteza Rafiee and Abolfazl Bayat
We introduce a fully coherent way for directed transport of localized atoms in optical lattices by regularly performing phase shifts on the lattice potential during the free evolution of the system. This paves the way for realizing a possible cold atom quantum computer in which entangling gates operate by bringing two individual atoms in the proximity of each other and letting them to interact. The speed of our protocol is determined by the tunneling amplitudes of the atoms and thus is much faster than the speed of the dynamics resulted from superexchange interaction in spin chains. Our scheme is robust against possible imperfections and perhaps its main advantage is its simplicity where all of its requirements have been already achieved in recent experiments.

Polynomial time quantum algorithms for certain bivariate hidden polynomial problems (pp0790-0806)
          Thomas Decker, Peter Hoyer, Gabor Ivanyos, and Miklos Santha
We present a new method for solving the hidden polynomial graph problem (HPGP) which is a special case of the hidden polynomial problem (HPP). The new approach yields an efficient quantum algorithm for the bivariate HPGP even when the input consists of several level set superpositions, a more difficult version of the problem than the one where the input is given by an oracle. For constant degree, the algorithm is polylogarithmic in the size of the base field. We also apply the results to give an efficient quantum algorithm for the oracle version of the HPP for an interesting family of bivariate hidden functions. This family includes diagonal quadratic forms and elliptic curves.

Performance and error analysis of Knill's postselection scheme in a two-dimensional architecture (pp0807-0822)
          Ching-Yi Lai, Gerardo Paz, Martin Suchara, and Todd A. Brun
Knill demonstrated a fault-tolerant quantum computation scheme based on concatenated error-detecting codes and postselection with a simulated error threshold of $3\%$ over the depolarizing channel. We show how to use Knill's postselection scheme in a practical two-dimensional quantum
architecture that we designed with the goal to optimize the error correction properties, while satisfying important architectural constraints. In our 2D architecture, one logical qubit is embedded in a tile consisting of $5\times 5$ physical qubits. The movement of these qubits is modeled as noisy SWAP gates and the only physical operations that are allowed are local one- and two-qubit gates. We evaluate the practical properties of our design, such as its error threshold, and compare it to the concatenated Bacon-Shor code and the concatenated Steane code. Assuming that all gates have the same error rates, we obtain a threshold of $3.06\times 10^{-4}$ in a local adversarial stochastic noise model, which is the highest known error threshold for concatenated codes in 2D. We also present a Monte Carlo simulation of the 2D architecture with depolarizing noise and we calculate a pseudo-threshold of about $0.1\%$. With memory error rates one-tenth of the worst gate error rates, the threshold for the adversarial noise model, and the pseudo-threshold over depolarizing noise, are $4.06\times 10^{-4}$ and $0.2\%$, respectively. In a hypothetical technology where memory error rates are negligible, these thresholds can be further increased by shrinking the tiles into a $4\times 4$ layout.

Unextendible mutually unbiased bases from Pauli C\classes (pp0823-0844)
          Prabha Mandayam, Somshubhro Bandyopadhyay, Markus Grassl, and William K. Wootters
We provide a construction of sets of $d/2+1$ mutually unbiased bases (MUBs) in dimensions $d=4,8$ using maximal commuting classes of Pauli operators. We show that these incomplete sets cannot be extended further using the operators of the Pauli group. Moreover, specific examples of sets of MUBs obtained using our construction are shown to be {\it strongly unextendible}; that is, there does not exist another vector that is unbiased with respect to the elements in the set. We conjecture the existence of such unextendible sets in higher dimensions $d=2^{n} (n>3) $ as well.} {Furthermore, we note an interesting connection between these unextendible sets and state-independent proofs of the Kochen-Specker Theorem for two-qubit systems. Our construction also leads to a proof of the tightness of a $H_{2}$ entropic uncertainty relation for any set of three MUBs constructed from Pauli classes in $d=4$.

Quantum key distribution: defeating collective noise without reducing efficiency (pp0845-0856)
          Song Lin, Gong-De Guo, Fei Gao, and Xiao-Fen Liu
Decoherence-free subspace (DFS) is a valid solution to realize quantum communication over a collective noise channel, and has been widely studied. Generally speaking, replacing a qubit with a DFS state will cause the reduction of communication efficiency. However, in this letter, it is shown that some kinds of noises may not lower the transmission rate of quantum key distribution. To illustrate it, we propose two quantum key distribution protocols based on Bell states. Here, two nonorthogonal and unbiased sets in a DFS are constructed by linear combination of particles at different positions. Since $n-1$ classical bits are distributed by using $2n$ qubits in our protocols, the transmission rate is close to that of noiseless BB84 protocol. Furthermore, when considering the cost of transmitting classical bits, the efficiencies of these protocols are even higher than that of BB84 protocol.

On the spectral dependence of separable and classical correlations in small quantum systems (pp0857-0887)
          Gary McConnell and David Jennings
We study the correlation structure of separable and classical states in $2\times2$-~and~$2\times3$-dimensional quantum systems with fixed spectra. Even for such simple systems the maximal correlation - as measured by mutual information - over the set of unitarily accessible separable states is highly non-trivial to compute; however for the $2\times2$ case a particular class of spectra admits full analysis and allows us to contrast classical states with more general separable states. We analyse a particular entropic binary relation on the set of spectra and prove for the qubit-qutrit case that this relation alone picks out a unique classical maximum state for mutual information. Moreover the $2\times3$ case is the largest system with such a property.

A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2n) (pp0888-0900)
          Martin Rotteler and Rainer Steinwandt
Improving over an earlier construction by Kaye and Zalka \cite{KaZa04}, in \cite{MMCP09b} Maslov et al. describe an implementation of Shor's algorithm, which can solve the discrete logarithm problem on ordinary binary elliptic curves in quadratic depth $\bigO(n^2)$. In this paper we show that discrete logarithms on such curves can be found with a quantum circuit of depth $\bigO(\log^2n)$. As technical tools we introduce quantum circuits for ${\mathbb F}_{2^n}$-multiplication in depth $\bigO(\log n)$ and for ${\mathbb F}_{2^n}$-inversion in depth $\bigO(\log^2 n)$.