Performance scaling of the quantum Fourier transform with defective rotation gates (pp0721-0736)
          Yun Seong Nam and Reinhold Blumel
Addressing Landauer's question concerning the influence of static gate defects on quantum information processor performance, we investigate analytically and numerically the case of the quantum Fourier transform (QFT) with defective controlled rotation (CROT) gates. Two types of defects are studied, separately and in combination: systematic and random. Analytical scaling laws of QFT performance are derived with respect to the number of qubits $n$, the size $\delta$ of systematic defects, and the size $\epsilon$ of random defects. The analytical results are in excellent agreement with numerical simulations. In addition, we present an unexpected result: The performance of the defective QFT does not deteriorate with increasing $n$, but approaches a constant that scales in $\epsilon$. We derive an analytical formula that accurately reproduces the $\epsilon$ scaling of the performance plateaus. Overall, we observe that the CROT gates may exhibit static and random defects of the order of 30\% and larger, and still result in satisfactory QFT performance. Thus we answer Landauer's question in the case of the QFT: far from being lethal, the QFT can tolerate tremendous static gate defects and still perform its function. The extraordinary robustness of the QFT with respect to static gate defects displayed in our numerical and analytical calculations should be a welcome boon for laboratory and industrial realizations of quantum circuitry.

Minimum guesswork discrimination between quantum states (pp0737-0758)
          Weien Chen, Yongzhi Cao, Hanpin Wang, and Yuan Feng
Error probability is a popular and well-studied optimization criterion in discriminating non-orthogonal quantum states. It captures the threat from an adversary who can only query the actual state once. However, when the adversary is able to use a brute-force strategy to query the state, discrimination measurement with minimum error probability does not necessarily minimize the number of queries to get the actual state. In light of this, we take Massey's guesswork as the underlying optimization criterion and study the problem of minimum guesswork discrimination. We show that this problem can be reduced to a semidefinite programming problem. Necessary and sufficient conditions when a measurement achieves minimum guesswork are presented. We also reveal the relation between minimum guesswork and minimum error probability. We show that the two criteria generally disagree with each other, except for the special case with two states. Both upper and lower information-theoretic bounds on minimum guesswork are given. For geometrically uniform quantum states, we provide sufficient conditions when a measurement achieves minimum guesswork. Moreover, we give the necessary and sufficient condition under which making no measurement at all would be the optimal strategy.

Tensor networks and graphical calculus for open quantum systems (pp0759-0811)
          Christopher J. Wood, Jacob D. Biamonte, and David G. Cory
We describe a graphical calculus for completely positive maps and in doing so review the theory of open quantum systems and other fundamental primitives of quantum information theory using the language of tensor networks. In particular we demonstrate the construction of tensor networks to pictographically represent the Liouville-superoperator, Choi-matrix, process-matrix, Kraus, and system-environment representations for the evolution of quantum states, review how these representations interrelate, and illustrate how graphical manipulations of the tensor networks may be used to concisely transform between them. To further demonstrate the utility of the presented graphical calculus we include several examples where we provide arguably simpler graphical proofs of several useful quantities in quantum information theory including the composition and contraction of multipartite channels, a condition for whether an arbitrary bipartite state may be used for ancilla assisted process tomography, and the derivation of expressions for the average gate fidelity and entanglement fidelity of a channel in terms of each of the different representations of the channel.

Does symmetry Imply PPT Property? (pp0812-0824)
          Daniel Cariello
Recently it was proved that many results that are true for density matrices which are positive under partial transposition (or simply PPT), also hold for another class of matrices with a certain symmetry in their Hermitian Schmidt decompositions. These matrices were called symmetric with positive coefficients (or simply SPC). A natural question appeared: What is the connection between SPC matrices and PPT matrices? Is every SPC matrix PPT? Here we show that every SPC matrix is PPT in $M_2\otimes M_2$. This theorem is a consequence of the fact that every density matrix in $M_2\otimes M_m$, with tensor rank smaller or equal to 3, is separable. Although, in $M_3\otimes M_3$, we present an example of SPC matrix with tensor rank 3 that is not PPT. We shall also provide a non trivial example of a family of matrices in $M_k\otimes M_k$, in which both, the SPC and PPT properties, are equivalent. Within this family, there exists a non trivial subfamily in which the SPC property is equivalent to separability.

Spin glass reflection of the decoding transition for quantum error correcting codes (pp0825-0852)
          Alexey A. Kovalev and Leonid P. Pryadko
We study the decoding transition for quantum error
correcting codes with the help of a mapping to random-bond Wegner spin models. Families of quantum low density parity-check (LDPC) codes with a finite decoding threshold lead to both known models (e.g., random bond Ising and random plaquette $\Z2$ gauge models) as well as unexplored earlier generally non-local disordered spin models with non-trivial phase diagrams. The decoding transition corresponds to a transition from the ordered phase by proliferation of ``post-topological'' extended defects which generalize the notion of domain walls to non-local spin models. In recently discovered quantum LDPC code families with finite rates the number of distinct classes of such extended defects is exponentially large, corresponding to extensive ground state entropy of these codes. Here, the transition can be driven by the entropy of the extended defects, a mechanism distinct from that in the local spin models where the number of defect types (domain walls) is always finite.

Optimising the information flow of one-way quantum computations (pp0853-0884)
          Einar Pius, Raphael Dias da Silva, and Elham Kashefi
In the one-way quantum computing model, the information processing is driven by measurements performed on an entangled state, called the resource state. In order to achieve parallelism, one aims to increase the number of simultaneous measurements, such that the effects of decoherence on the resource state are minimised due to the reduction of the time required to run the computation. At the heart of this question is the notion of quantum information flow, which specifies the dependency relations between the measurements in the computations. There exist two well-known techniques for reducing the time required to perform a one-way quantum computation without changing its semantics. The first one, called signal-shifting, transforms the flow of a graph (representing the resource state) within the measurement calculus formalism, whereas the second one, namely finding the maximally-delayed generalised flow, explores the geometry of the graph to increase the number of operations that can be performed simultaneously. In this paper, we show for the first time how these two techniques relate to each other. We prove that the application of the signal-shifting rules to a measurement pattern with flow results in a generalised flow for the pattern. Then, we prove that in the particular case when the input size equals the output size, the gflow obtained using signal-shifting has the lowest possible depth. As a side result, we construct an $O(n^3)$-algorithm for finding maximally delayed gflows on graphs with flow. For those graphs, our algorithm is more efficient than the best previously known algorithm for the same task, which takes $O(n^4)$ operations to complete.

Tensor network non-zero testing (pp0885-0899)
          Sevag Gharibian, Zeph Landau, Seung Woo Shin, and Guoming Wang
Tensor networks are an important tool in condensed matter physics. In this paper, we study the task of tensor network non-zero testing (\tnit): Given a tensor network $T$, does $T$ represent a non-zero vector? We show that \tnit~is not in the Polynomial-Time Hierarchy unless the hierarchy collapses. We next show (among other results) that the special cases of \tnit~on non-negative and injective tensor networks are in NP. Using this, we make a simple observation: The commuting variant of the MA-complete stoquastic $k$-SAT problem on $D$-dimensional qudits is in NP for $k\in O(\log n)$ and $D\in O(1)$. This reveals the first class of quantum Hamiltonians whose commuting variant is known to be in NP for all (1) logarithmic $k$, (2) constant $D$, and (3) for arbitrary interaction graphs.