Counterexamples to Kalai's conjecture C (pp0001-0008)
          Steven T. Flammia and Aram W. Harrow
We provide two simple counterexamples to Kalai's Conjecture C and discuss our perspective on the implications for the prospect of large-scale fault-tolerant quantum computation.

Fidelity as a figure of merit in quantum error correction (pp0009-0020)
          Jonas Aamlof and Gunnar Bjork
We discuss the fidelity as a figure of merit in quantum error correction schemes. We show that when identifiable but uncorrectable errors occur as a result of the action of the channel, a common strategy that improves the fidelity actually decreases the transmitted mutual information. The conclusion is that while the fidelity is simple to calculate and therefore often used, it is perhaps not always a recommendable figure of merit for quantum error correction. The reason is that while it roughly speaking encourages optimisation of the ``mean probability of success'', it gives no incentive for a protocol to indicate exactly where the errors lurk. For small error probabilities, the latter information is more important for the integrity of the information than optimising the mean probability of success.

Hermitian dual containing BCH codes and Construction of new quantum codes (pp0021-0035)
          Ruihu Li, Fei Zou, Yang Liu, and Zongben Xu
Let $q\geq 3$ be a prime power. Maximal designed distances of primitive Hermitian dual containing $q^{2}$-ary BCH codes (narrow-sense or non-narrow-sense) are determined by a careful analysis of properties of cyclotomic cosets. Non-narrow-sense BCH codes which achieve these maximal designed distances are presented, and a sequence of nested non-narrow-sense BCH codes that contain these BCH codes with maximal designed distances are constructed and their parameters are computed. Consequently, new nonbinary quantum BCH codes are derived from these non-narrow-sense BCH codes. The nonbinary quantum BCH codes presented here have better parameters than those quantum BCH codes available in the literature.

Multiqubit entanglement of a general input state (pp0036-0053)
          Elizabeth C. Behrman and James E. Steck
Measurement of entanglement remains an important problem for quantum information. We present the design and simulation of an experimental method for an entanglement indicator for a general multiqubit state. The system can be in a pure or a mixed state, and it need not be ``close'' to any particular state. The system contains information about its own entanglement; we use dynamic learning methods to map this information onto a single experimental measurement which is our entanglement indicator. Our method does not require prior state reconstruction or lengthy optimization. An entanglement witness emerges from the learning process, beginning with two-qubit systems, and extrapolating this to three, four, and five qubit systems where the entanglement is not well understood. Our independently learned measures for three-qubit systems compare favorably with known entanglement measures. As the size of the system grows the amount of additional training necessary diminishes, raising hopes for applicability to large computational systems.

Commuting quantum circuits: efficiently classical simulations versus hardness results (pp0054-0072)
          Xiaotong Ni and Maarten van den Nest
The study of quantum circuits composed of commuting gates is particularly useful to understand the delicate boundary between quantum and classical computation. Indeed, while being a restricted class, commuting circuits exhibit genuine quantum effects such as entanglement. In this paper we show that the computational power of commuting circuits exhibits a surprisingly rich structure. First we show that every 2-local commuting circuit acting on $d$-level systems and followed by single-qudit measurements can be efficiently simulated classically with high accuracy. In contrast, we prove that such strong simulations are hard for 3-local circuits. Using sampling methods we further show that all commuting circuits composed of exponentiated Pauli operators $e^{i\theta P}$ can be simulated efficiently classically when followed by single-qubit measurements. Finally, we show that commuting circuits can efficiently simulate certain non-commutative processes, related in particular to constant-depth quantum circuits. This gives evidence that the power of commuting circuits goes beyond classical computation.

A linearized stabilizer formalism for systems of finite dimension (pp0073-0115)
          Niel de Beaudrap
The stabilizer formalism is a scheme, generalizing well-known techniques developed by Gottesman~\cite{GottPhD} in the case of qubits, to efficiently simulate a class of transformations (\emph{stabilizer circuits}, which include the quantum Fourier transform and highly entangling operations) on standard basis states of $d$-dimensional qudits. To determine the state of a simulated system, existing treatments involve the computation of cumulative phase factors which involve quadratic dependencies. We present a simple formalism in which Pauli operators are represented using displacement operators in discrete phase space, expressing the evolution of the state via linear transformations modulo $D \le 2d$. We thus obtain a simple proof that simulating stabilizer circuits on $n$ qudits, involving any constant number of measurement rounds, is complete for the complexity class \coMod[d]\Log\ and may be simulated by $O(\log(n)^2)$-depth circuits for any constant $d \ge 2$.

Correspondence:

Cryptanalysis of a secret sharing scheme (pp0178-0180)
          Subhamoy Maitra and Kaushik Nandi
In this correspondence, we point out a major security problem in the secret sharing scheme proposed in QIC 12(3-4), 0253-0261, 2012.