Vol.17 No.3&4, March 1, 2017

Research Articles:

Local decoders for the 2D and 4D toric code (pp0181-0208)
          Nikolas P. Breuckmann, Kasper Duivenvoorden, Dominik Michels, and Barbara M. Terhal
We analyze the performance of decoders for the 2D and 4D toric code which are local by construction. The 2D decoder is a cellular automaton decoder formulated by Harrington \cite{thesis:harrington} which explicitly has a finite speed of communication and computation. For a model of independent $X$ and $Z$ errors and faulty syndrome measurements with identical probability, we report a threshold of $0.133\%$ for this Harrington decoder. We implement a decoder for the 4D toric code which is based on a decoder by Hastings \cite{hastings}. Incorporating a method for handling faulty syndromes we estimate a threshold of $1.59\%$ for the same noise model as in the 2D case. We compare the performance of this decoder with a decoder based on a 4D version of Toom's cellular automaton rule as well as the decoding method suggested by Dennis {\em et al.} \cite{DKLP}.

Quantum key distribution with mismatched measurements over arbitrary channels (pp0209-0241)
          Walter O. Krawec
In this paper, we derive key-rate expressions for different quantum key distribution protocols.  Our key-rate equations utilize multiple channel statistics, including those gathered from mismatched measurement bases - i.e., when Alice and Bob choose incompatible bases.  In particular, we will consider an Extended B92 and a two-way semi-quantum protocol.  For both these protocols, we demonstrate that their tolerance to noise is higher than previously thought - in fact, we will show the semi-quantum protocol can actually tolerate the same noise level as the fully quantum BB84 protocol.  Along the way, we will also consider an optimal QKD protocol for various quantum channels.  Finally, all the key-rate expressions which we derive in this paper are applicable to any arbitrary, not necessarily symmetric, quantum channel.

Modified group non-membership is in promise-AWPP relative to group oracles (pp0242-0250)
          Tomoyuki Morimae, Harumichi Nishimura, and Francois Le Gall
It is known that the group non-membership problem is in QMA relative to any group oracle and in ${\rm SPP}\cap{\rm BQP}$ for solvable groups. We consider a modified version of the group non-membership problem where the order of the group is also given as an additional input. We show that  the problem is in (the promise version of)  AWPP relative to any group oracle. To show the result, we use the idea of postselected quantum computing.

Optimizing the number of gates in quantum search (pp0251-0261)
          Srinivasan Arunachalam and Ronald de Wolf
In its usual form, Grover's quantum search algorithm uses $O(\sqrt{N})$ queries and $O(\sqrt{N} \log N)$ other elementary gates to find a solution in an $N$-bit database.  Grover in 2002 showed how to reduce the number of other gates to $O(\sqrt{N}\log\log N)$ for the special case where the database has a unique solution, without significantly increasing the number of queries.  We show how to reduce this further to $O(\sqrt{N}\log^{(r)} N)$ gates for every constant~$r$, and sufficiently large~$N$.  This means that, on average, the circuits between two queries barely touch more than a constant number of the $\log N$ qubits on which the algorithm acts. For a very large $N$ that is a power of~2, we can choose~$r$ such that the algorithm uses essentially the minimal number $\frac{\pi}{4}\sqrt{N}$ of queries, and only $O(\sqrt{N}\log(\log^{\star} N))$ other gates.

Further extensions of Clifford circuits and their classical simulation complexities (pp0262-0282)
          Dax E. Koh
Extended Clifford circuits straddle the boundary between classical and quantum computational power. Whether such circuits are efficiently classically simulable seems to depend delicately on the ingredients of the circuits. While some combinations of ingredients lead to efficiently classically simulable circuits, other combinations, which might just be slightly different, lead to circuits which are likely not. We extend the results of Jozsa and Van den Nest [Quant. Info. Comput. 14, 633 (2014)] by studying two further extensions of Clifford circuits. First, we consider how the classical simulation complexity changes when we allow for more general measurements. Second, we investigate different notions of what it means to `classically simulate' a quantum circuit. These further extensions give us 24 new combinations of ingredients compared to Jozsa and Van den Nest, and we give a complete classification of their classical simulation complexities. Our results provide more examples where seemingly modest changes to the ingredients of Clifford circuits lead to ``large" changes in the classical simulation complexities of the circuits, and also include new examples of extended Clifford circuits that exhibit ``quantum supremacy", in the sense that it is not possible to efficiently classically sample from the output distributions of such circuits, unless the polynomial hierarchy collapses.

On quantum additive Gaussian noise channels (pp0283-0302)
          Martin Idel and Robert Konig
We give necessary and sufficient conditions for a  Gaussian quantum channel to have a dilation involving a passive, i.e., number-preserving unitary. We then establish a normal form of such channels: any passively dilatable channel is the result of applying passive unitaries to the input and output of a Gaussian additive channel. The latter combine the state of the system with that of the environment by means of a  multi-mode beamsplitter.

Perfect state transfer on graphs with a potential (pp0303-0327)
          Mark Kempton, Gabor Lippner, and Shing-Tung Yau
In this paper we study quantum state transfer (also called quantum tunneling) on graphs when there is a potential function on the vertex set. We present two main results.  First, we show that for paths of length greater than three, there is no potential on the vertices of the path for which perfect state transfer between the endpoints can occur.  In particular, this answers a question raised by Godsil in Section 20 of~\cite{godsil}.  Second, we show that if a graph has two vertices that share a common neighborhood, then there is a potential on the vertex set for which perfect state transfer will occur between those two vertices.  This gives numerous examples where perfect state transfer does not occur without the potential, but adding a potential makes perfect state transfer possible.  In addition, we investigate perfect state transfer on graph products, which gives further examples where perfect state transfer can occur.

back to QIC online Front page