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.