**
****Metrics on unitary matrices and their application to
quantifying the degree of non-commutativity between unitary matrices**
(pp0721-0740)

H.F.
Chau

By studying the minimum resources required to perform a unitary
transformation, families of metrics and pseudo-metrics on unitary
matrices that are closely related to a recently reported quantum speed
limit by the author are found. Interestingly, this family of metrics can
be naturally converted into useful indicators of the degree of non-commutativity
between two unitary matrices.

**
****Crossovers induced by discrete-time quantum walks
**
(pp0741-0760)

Kota Chisaki,
Norio Konno, Etsuo Segawa, and Yutaka Shikano

We consider crossovers with respect to the weak convergence theorems
from a discrete-time quantum walk (DTQW). We show that a continuous-time
quantum walk (CTQW) and discrete- and continuous-time random walks can
be expressed as DTQWs in some limits. At first we generalize our
previous study [Phys. Rev. A \textbf{81}, 062129 (2010)] on the DTQW
with position measurements. We show that the position measurements per
each step with probability $p \sim 1/n^\beta$ can be evaluated, where
$n$ is the final time and $0<\beta<1$. We also give a corresponding
continuous-time case. As a consequence, crossovers from the diffusive
spreading (random walk) to the ballistic spreading (quantum walk) can be
seen as the parameter $\beta$ shifts from 0 to 1 in both discrete- and
continuous-time cases of the weak convergence theorems. Secondly, we
introduce a new class of the DTQW, in which the absolute value of the
diagonal parts of the quantum coin is proportional to a power of the
inverse of the final time $n$. This is called a final-time-dependent
DTQW (FTD-DTQW). The CTQW is obtained in a limit of the FTD-DTQW. We
also obtain the weak convergence theorem for the FTD-DTQW which shows a
variety of spreading properties. Finally, we consider the FTD-DTQW with
periodic position measurements. This weak convergence theorem gives a
phase diagram which maps sufficiently long-time behaviors of the
discrete- and continuous-time quantum and random walks.

**
****Return probability of quantum walks with final-time
dependence**
(pp0761-0773)

Yusuke
Ide, Norio Konno, Takuya Machida, and Etsuo Segawa

We analyze final-time dependent discrete-time quantum walks in one
dimension. We compute asymptotics of the return probability of the
quantum walk by a path counting approach. Moreover, we discuss a
relation between the quantum walk and the corresponding final-time
dependent classical random walk.

**
****Private quantum channels, conditional expectations,
and trace vectors**
(pp0774-0783)

Amber Church,
David W. Kribs, Rajesh Pereira, and Sarah Plosker

Private quantum channels are the quantum analogue of the classical
one-time pad. Conditional expectations and trace vectors are notions
that have been part of operator algebra theory for several decades. We
show that the theory of conditional expectations and trace vectors is
intimately related to that of private quantum channels. Specifically we
give a new geometric characterization of single qubit private quantum
channels that relies on trace vectors. We further show that trace
vectors completely describe the private states for quantum channels that
are themselves conditional expectations. We also discuss several
examples.

**
****Simulating quantum computers with probabilistic
methods**
(pp0784-0812)

Maarten Van den
Nest

We investigate the boundary between classical and quantum computational
power. This work consists of two parts. First we develop new classical
simulation algorithms that are centered on sampling methods. Using these
techniques we generate new classes of classically simulatable quantum
circuits where standard techniques relying on the exact computation of
measurement probabilities fail to provide efficient simulations. For
example, we show how various concatenations of matchgate, Toffoli,
Clifford, bounded-depth, Fourier transform and other circuits are
classically simulatable. We also prove that sparse quantum circuits as
well as circuits composed of CNOT and $\exp[{i\theta X}]$ gates can be
simulated classically. In a second part, we apply our results to the
simulation of quantum algorithms. It is shown that a recent quantum
algorithm, concerned with the estimation of Potts model partition
functions, can be simulated efficiently classically. Finally, we show
that the exponential speed-ups of Simon's and Shor's algorithms
crucially depend on the very last stage in these algorithms, dealing
with the classical postprocessing of the measurement outcomes.
Specifically, we prove that both algorithms would be classically
simulatable if the function classically computed in this step had a
sufficiently peaked Fourier spectrum.

**
****Deciding unitary equivalence between matrix
polynomials and sets of bipartite quantum states**
(pp0813-0819)

Eric Chitambar,
Carl Miller, and Yaoyun. Shi

In this brief report, we consider the equivalence between two sets
of $m+1$ bipartite quantum states under local unitary transformations.
For pure states, this problem corresponds to the matrix algebra question
of whether two degree $m$ matrix polynomials are unitarily equivalent;
i.e. $UA_iV^\dagger=B_i$ for $0\leq i\leq m$ where $U$ and $V$ are
unitary and $(A_i, B_i)$ are arbitrary pairs of rectangular matrices. We
present a randomized polynomial-time algorithm that solves this problem
with an arbitrarily high success probability and outputs transforming
matrices $U$ and $V$.

**
****On the experimental violation of Mermin's inequality
with imperfect measurements**
(pp0820-0839)

Ruffin Evans and
Olivier Pfister

We investigate theoretically the feasibility of an experimental test
of the Bell-type inequality derived by Mermin for correlated spins
larger than ${1}/{2}$. Using the Schwinger representation, we link the
output fields of two two-mode squeezers in order to create correlated
effective spins between two observers. Spin measurements will be
performed by photon-number-resolved photodetection, which has recently
come of age. We examine the effect of nonideal detection quantum
efficiency -and any other optical loss - on the violation margin of
Mermin's inequality. We find that experimental violation is well
accessible for spins larger than 1, for quantum efficiencies compatible
with the current state of the art.

**
****Unstructured randomness, small gaps and localization
**
(pp0840-0854)

Edward Farhi,
Jeffrey Goldstone, David Gosset, Sam Gutmann, and Peter Shor

We study the Hamiltonian associated with the quantum adiabatic algorithm
with a random cost function. Because the cost function lacks structure
we can prove results about the ground state. We find the ground state
energy as the number of bits goes to infinity, show that the minimum gap
goes to zero exponentially quickly, and we see a localization
transition. We prove that there are no levels approaching the ground
state near the end of the evolution. We do not know which features of
this model are shared by a quantum adiabatic algorithm applied to random
instances of satisfiability since despite being random they do have bit
structure.

**
****Entanglement for quantum walks on the line**
(pp0855-0866)

Yusuke Ide, Norio
Konno, and Takuya Machida

The discrete-time quantum
walk is a quantum counterpart of the random walk. It is expected that
the model plays important roles in the quantum field. In the quantum
information theory, entanglement is a key resource. We use the von
Neumann entropy to measure the entanglement between the coin and the
particle's position of the quantum walks. Also we deal with the Shannon
entropy which is an important quantity in the information theory. In
this paper, we show limits of the von Neumann entropy and the Shannon
entropy of the quantum walks on the one dimensional lattice starting
from the origin defined by arbitrary coin and initial state. In order to
derive these limits, we use the path counting method which is a
combinatorial method for computing probability amplitude.

**Constructing arbitrary Steane code single logical
qubit fault-tolerant gates** (pp0867-0873)

Austin G.
Fowler

We present a simple method for constructing optimal fault-tolerant
approximations of arbitrary unitary gates using an arbitrary discrete
universal gate set. The method presented is numerical and

scales exponentially with the number of gates used in the approximation.
However, for the specific case of arbitrary single-qubit gates and the
fault-tolerant gates permitted by the concatenated 7-qubit Steane code,
we find gate sequences sufficiently long and accurate to permit the
fault-tolerant

factoring of numbers thousands of bits long. A general scaling law of
how rapidly these fault-tolerant approximations converge to arbitrary
single-qubit gates is also determined.