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.
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.
back to QIC online Front page
|