QIC Abstracts

 Vol.13 No.1&2, January 1, 2013

Research Articles:

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

Quantum binary field inversion: improved circuit depth via choice of basis representation  (pp0116-0134)
Brittanney Amento, Martin Rotteler, and Rainer Steinwandt

Finite fields of the form ${\mathbb F}_{2^m}$ play an important role in coding theory and cryptography. We show that the choice of how to represent the elements of these fields can have a significant impact on the resource requirements for quantum arithmetic. In particular, we show how the use of Gaussian normal basis representations and of `ghost-bit basis' representations can be used to implement inverters with a quantum circuit of depth $\bigO(m\log(m))$. To the best of our knowledge, this is the first construction with subquadratic depth reported in the literature. Our quantum circuit for the computation of multiplicative inverses is based on the Itoh-Tsujii algorithm which exploits that in normal basis representation squaring corresponds to a permutation of the coefficients. We give resource estimates for the resulting quantum circuit for inversion over binary fields ${\mathbb F}_{2^m}$ based on an elementary gate set that is useful for fault-tolerant implementation.

QMA variants with polynomially many provers (pp0135-0157)
Sevag Gharibian, Jamie Sikora, and Sarvagya Upadhyay

We study three variants of multi-prover quantum Merlin-Arthur proof systems. We first show that the class of problems that can be efficiently verified using polynomially many quantum proofs, each of logarithmic-size, is exactly \class{MQA} (also known as QCMA), the class of problems which can be efficiently verified via a classical proof and a quantum verifier. We then study the class $\class{BellQMA}(\poly)$, characterized by a verifier who first applies unentangled, nonadaptive measurements to each of the polynomially many proofs, followed by an arbitrary but efficient quantum verification circuit on the resulting measurement outcomes. We show that if the number of outcomes per nonadaptive measurement is a polynomially-bounded function, then the expressive power of the proof system is exactly \class{QMA}. Finally, we study a class equivalent to \class{QMA}($m$), denoted $\class{SepQMA}(m)$, where the verifier's measurement operator corresponding to outcome {\it accept} is a fully separable operator across the $m$ quantum proofs. Using cone programming duality, we give an alternate proof of a result of Harrow and Montanaro [FOCS, pp. 633--642 (2010)] that shows a perfect parallel repetition theorem for $\class{SepQMA}(m)$ for any $m$.

Lower bounds for quantum oblivious transfer (pp0158-0177)
Andre Chailloux, Iordanis Kerenidis, and Jamie Sikora
Oblivious transfer is a fundamental primitive in cryptography. While perfect information theoretic security is impossible, quantum oblivious transfer protocols can limit the dishonest player's cheating. Finding the optimal security parameters in such protocols is an important open question.  In this paper we show that every 1-out-of-2 oblivious transfer protocol allows a dishonest party to cheat with probability bounded below by a constant strictly larger than $1/2$. Alice's cheating is defined as her probability of guessing Bob's index, and Bob's cheating is defined as his probability of guessing both input bits of Alice. In our proof, we relate these cheating probabilities to the cheating probabilities of a bit commitment protocol and conclude by using lower bounds on quantum bit commitment. Then, we present an oblivious transfer protocol with two messages and cheating probabilities at most $3/4$. Last, we extend Kitaev's semidefinite programming formulation to more general primitives, where the security is against a dishonest player trying to force the outcome of the other player, and prove optimal lower and upper bounds for them.


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.

back to QIC online Front page