A new relativistic orthogonal states quantum key distribution protocol (pp1081-1088)
          Jordan S. Cotler and Peter W. Shor
We introduce a new relativistic orthogonal states quantum key distribution protocol which leverages the properties of both quantum mechanics and special relativity to securely encode multiple bits onto the spatio-temporal modes of a single photon. If the protocol is implemented using a single photon source, it can have a key generation rate faster than the repetition rate of the source, enabling faster secure communication than is possible with existing protocols. Further, we provide a proof that the protocol is secure and give a method of implementing the protocol using line-of-sight and fiber optic channels.

A quantum lower bound for distinguishing random functions from random permutations (pp1089-1097)
          Henry Yuen
The problem of distinguishing between a random function and a random permutation on a domain of size $N$ is important in theoretical cryptography, where the security of many primitives depend on the problem's hardness. We study the quantum query complexity of this problem, and show that any quantum algorithm that solves this problem with bounded error must make $\Omega(N^{1/5}/\polylog N)$ queries to the input function. Our lower bound proof uses a combination of the Collision Problem lower bound and Ambainis's adversary theorem.

Small sets of locally indistinguishable orthogonal maximally entangled states (pp1098-1106)
          Alessandro Cosentino and Vincent Russo
We study the problem of distinguishing quantum states using local operations and classical communication (LOCC). A question of fundamental interest is whether there exist sets of $k \leq d$ orthogonal maximally entangled states in $\complex^{d}\otimes\complex^{d}$ that are not perfectly distinguishable by LOCC. A recent result by Yu, Duan, and Ying [Phys. Rev. Lett. 109 020506 (2012)] gives an affirmative answer for the case $k = d$. We give, for the first time, a proof that such sets of states indeed exist even in the case $k < d$. Our result is constructive and holds for an even wider class of operations known as positive-partial-transpose measurements (PPT). The proof uses the characterization of the PPT-distinguishability problem as a semidefinite program.

Entanglement-assisted quantum codes achieving the quantum singleton bound but violating the quantum hamming bound (pp1107-1116)
          Ruihu Li, Luobin Guo, and Zongben Xu
We give an infinite family of degenerate entanglement-assisted quantum error-correcting codes (EAQECCs) which violate the EA-quantum Hamming bound for non-degenerate EAQECCs and achieve the EA-quantum Singleton bound, thereby proving that the EA-quantum Hamming bound does not asymptotically hold for degenerate EAQECCs. Unlike the previously known quantum error-correcting codes that violate the quantum Hamming bound by exploiting maximally entangled pairs of qubits, our codes do not require local unitary operations on the entangled auxiliary qubits during encoding. The degenerate EAQECCs we present are constructed from classical error-correcting codes with poor minimum distances, which implies that, unlike the majority of known EAQECCs with large minimum distances, our EAQECCs take more advantage of degeneracy and rely less on the error correction capabilities of classical codes.

Study on error reconciliation in quantum key distribution (pp1117-1135)
          Qiong Li, Dan Le, Haokun Mao, Xiamu Niu, Tian Liu, and Hong Guo
As one of the most important procedure in quantum key distribution system, the error reconciliation algorithm has drew many attentions. However, studies on the error reconciliation algorithm mainly focuses on the reconciliation efficiency. Since the ultimate goal of study on the error reconciliation is to find the most suitable algorithm for a quantum key distribution system and maximize the throughput rate of the whole system, the indicator of reconciliation efficiency is not full-scale enough to evaluate an error reconciliation algorithm. In this paper we propose a new evaluation scheme, including four direct indicators and one composite indicator to solve the problem. Following the new scheme, seven representative error reconciliation algorithms are simulated and compared thoroughly, i.e. BBBSS, the original Cascade and two improved Cascade algorithms, Winnow, and two LDPC based algorithms. Our works are very beneficial to the evaluation, comparison, selection and optimization of error reconciliation algorithms for a practical quantum key distribution system.

Quasiparticle localisation via frequent measurements (pp1136-1148)
          David A. Herrera-Marti, Ying Li, and Leong Chuan Kwek
Topological quantum memories in two dimensions are not thermally stable, since once a quasiparticle excitation is created, it will delocalise at no energy cost. This places an upper bound on the lifetime of quantum information stored in them. We address this issue for a topological subsystem code introduced in [Bravyi S.{\em et al.}, Quant.~Inf.~Comp.~13(11):0963]. By frequently measuring the gauge operators of the code, a technique known as Operator Quantum Zeno Effect [Li Y. {\em et al.}, preprint arXiv:1305.2464], the dynamics responsible for quasiparticle motion is suppressed, and can eventually be ``frozen" in the large frequency limit. A feature of this method is that the density operator of the code does not commute with the measurement operators, so the density matrix will be randomised after a few measurements. However the logical operators commute with the measurement operators and are thus protected.

Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates (pp1149-1164)
          Yasuhiro Takahashi, Takeshi Yamazaki, and Kazuyuki Tanaka
We study the classical simulatability of constant-depth polynomial-size quantum circuits followed by only one single-qubit measurement, where the circuits consist of universal gates on at most two qubits and additional gates on an unbounded number of qubits. First, we consider unbounded Toffoli gates as additional gates and deal with the weak simulation, i.e., sampling the output probability distribution. We show that there exists a constant-depth quantum circuit with only one unbounded Toffoli gate that is not weakly simulatable, unless $\bqp \subseteq \postbpp \cap \am$. Then, we consider unbounded fan-out gates as additional gates and deal with the strong simulation, i.e., computing the output probability. We show that there exists a constant-depth quantum circuit with only two unbounded fan-out gates that is not strongly simulatable, unless $\p = \pp$. These results are in contrast to the fact that any constant-depth quantum circuit without additional gates on an unbounded number of qubits is strongly and weakly simulatable.

One-dimensional quantum walks via generating function and the CGMV method (pp1165-1186)
          Norio Konno and Etsuo Segawa
We treat quantum walk (QW) on the line whose quantum coin at each vertex tends to the identity as the distance goes to infinity.  We obtain a limit theorem that this QW exhibits localization with not an exponential but a ``power-law" decay around the origin and a ``strongly" ballistic spreading called bottom localization in this paper. This limit theorem implies the weak convergence with linear scaling whose density has two delta measures at $x=0$ (the origin) and $x=1$ (the bottom) without continuous parts.

Decoding in hyperbolic spaces: quantum LDPC codes with linear rate and efficient error correction (pp1187-1202)
          Matthew B. Hastings
We analyze the four dimensional toric code in a hyperbolic space and show that it has a classical error correction procedure which runs in almost linear time and can be parallelized to almost constant time, giving an example of a quantum LDPC code with linear rate and efficient error correction.

Multiplicativity of superoperator norms for some entanglement breaking channels (pp1203-1212)
          Christopher King
It is known that the minimal output entropy is additive for any product of entanglement breaking (EB) channels. The same is true for the Renyi entropy, where additivity is equivalent to multiplicativity of the \norm{1}{q} norm for all $q \ge 1$. In this paper we consider the related question of multiplicativity of the \norm{2}{q} norm for $q > 2$ for entanglement breaking channels. We prove that multiplicativity holds in this case for certain classes of EB channels, including both the CQ and QC channels.

Stability of point spectrum for three-state quantum walks on a line (pp1213-1226)
          Martin Štefaňák, Iva Bezděková, Igor Jex, and Stephen M. Barnett
Evolution operators of certain quantum walks possess, apart from the continuous part, also a point spectrum. The existence of eigenvalues and the corresponding stationary states lead to partial trapping of the walker in the vicinity of the origin. We analyze the stability of this feature for three-state quantum walks on a line subject to homogenous coin deformations. We find two classes of coin operators that preserve the point spectrum. These new classes of coins are generalizations of coins found previously by different methods and shed light on the rich spectrum of coins that can drive discrete-time quantum walks.

Relevance of rank for a mixed state quantum teleportation resource (pp1227-1237)
          K.G. Paulson and S.V.M. Satyanarayana
Mixed entangled states are generic resource for quantum teleportation. Optimal teleportation fidelity measures the success of quantum teleportation. The relevance of rank in the teleportation process is investigated by constructing three new maximally entangled mixed states (MEMS) of different ranks. Linear entropy, concurrence, optimal teleportation fidelity and Bell function are obtained for each of these states analytically. It is found that mixed states with higher rank are better resource for teleportation. In order to achieve a fixed value of optimal teleportation fidelity, we find that low rank states must have high concurrence. Further, for each of ranks 2, 3 and 4, we numerically generate 30000 maximally entangled mixed states. The analysis of these states reveals the existence of a rank dependent upper bound on optimal teleportation fidelity for a fixed purity. In order to achieve a fixed optimal teleportation fidelity, we find MEMS exhibit a rank dependent lower bound on concurrence. MEMS are classified in terms of their degree of nonlocality. The results are found to be same with logarithmic negativity used as a measure of entanglement.

Quantum network exploration with a faulty sense of direction (pp1238-1250)
          Jaroslaw A. Miszczak and Przemyslaw Sadowski
We develop a model which can be used to analyse the scenario of exploring quantum network with a distracted sense of direction. Using this model we analyse the behaviour of quantum mobile agents operating with non-adaptive and adaptive strategies which can be employed in this scenario. We introduce the notion of node visiting suitable for analysing quantum superpositions of states by distinguishing between visiting and attaining a position. We show that without a proper model of adaptiveness, it is not possible for the party representing the distraction in the sense of direction, to obtain the results analogous to the classical case. Moreover, with additional control resources the total number of attained positions is maintained and the number of visited positions is strictly limited.

CTC assisted PR box type correlation can lead to signaling (pp1251-1260)
          Indranil Chakrabarty, Tanumoy Pramanik, Arun K Pati, and Pankaj Agrawal
It is known that there exist non-local correlations that respect no-signaling criterion, but violate Bell-type inequalities more than quantum-mechanical correlations. Such super quantum correlations were introduced as the Popescu-Rohrlich (PR) box. We consider such non-local boxes with two/three inputs and two/three outputs. We show that these super quantum correlations can lead to signaling when at least one of the input bit has access to a word line along a closed time-like curve.