*
***
**Research Articles:

**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.