Vol.10
No.9&10 September 1, 2010
Research Articles:
Fast equivalence -- checking for quantum circuits
(pp0721-0734)
Shigeru
Yamashita and Igor L. Markov
We perform formal verification of quantum circuits by integrating
several techniques specialized to particular classes of circuits. Our
verification methodology is based on the new notion of a reversible
miter that allows one to leverage existing techniques for
simplification of quantum circuits. For reversible circuits which
arise as runtime bottlenecks of key quantum algorithms, we develop
several verification techniques and empirically compare them. We also
combine existing quantum verification tools with the use of SAT-solvers.
Experiments with circuits for Shor's number-factoring algorithm,
containing thousands of gates, show improvements in efficiency by four
orders of magnitude.
Computational distinguishability of degradable and antidegradable
channels
(pp0735-0746)
Bill
Rosgen
A channel is degradable if there exists a second channel that maps the
output state of the channel to the environment state. These channels
satisfy the property that the output state contains more information
about the input than the environment does. A complementary class of
channels is the antidegradable channels, which admit channels that map
the environment state to the output state of the channel. In this paper
we show that the computational problem of distinguishing two channels
remains -complete when restricted to these classes of channels. This is
shown using a construction of Cubitt, Ruskai, and Smith that embeds any
channel into a degradable channel, and a related construction for the
case of antidegradable channels.
Languages recognized by nondeterministic quantum finite automata
(pp0747-0770)
Abuzer
Yakaryilmaz and A.C. Cem Say
The nondeterministic quantum finite automaton (NQFA) is the only known
case where a one-way quantum finite automaton (QFA) model has been shown
to be strictly superior in terms of language recognition power to its
probabilistic counterpart. We give a characterization of the class of
languages recognized by NQFAs, demonstrating that it is equal to the
class of exclusive stochastic languages. We also characterize the class
of languages that are recognized necessarily by two-sided error by QFAs.
It is shown that these classes remain the same when the QFAs used in
their definitions are replaced by several different model variants that
have appeared in the literature. We prove several closure properties of
the related classes. The ramifications of these results about classical
and quantum sublogarithmic space complexity classes are examined.
Security of practical phase-coding quantum key distribution
(pp0771-0779)
Hong-Wei
Li, Zheng-Qiang Yin, Zheng-Fu Han, Wan-Su Bao, and Guang-Can Guo
Security proof of practical quantum key distribution (QKD) has attracted
a lot of attentions in recent years. Most of real-life QKD
implementations are based on phase-coding BB84 protocol, which usually
use Unbalanced Mach-Zehnder Interferometer (UMZI) as the information
encoder and decoder. However, the long arm and short arm of UMZI will
introduce different loss in practical experimental realizations, the
state emitted by Alice's side is nolonger perfect BB84 states
correspondingly. In this paper, we will give the security analysis in
this situation. Counterintuitively, active compensation for this
different loss will only lower the secret key bit rate.
Graphical algorithms and threshold error rates for the 2d color code
(pp0780-0802)
David
S. Wang, Austin G. Fowler, Charles D. Hill, and Lloyd C.L. Hollenberg
Recent work on fault-tolerant quantum computation making use of
topological error correction shows great potential, with the 2d surface
code possessing a threshold error rate approaching 1\%. However, the 2d
surface code requires the use of a complex state distillation procedure
to achieve universal quantum computation. The color code of is a related
scheme partially solving the problem, providing a means to perform all
Clifford group gates transversally. We review the color code and its
error correcting methodology, discussing one approximate technique based
on graph matching. We derive an analytic lower bound to the threshold
error rate of 6.25\% under error-free syndrome extraction, while
numerical simulations indicate it may be as high as 13.3\%. Inclusion of
faulty syndrome extraction circuits drops the threshold to approximately
0.10 \pm 0.01\%.
All mutually unbiased bases in dimensions two to five
(pp0803-0820)
Stephen
Brierley, Stefan Weigert, and Ingemar Bengtsson
All complex Hadamard matrices in dimensions two to five are known. We
use this fact to derive all inequivalent sets of mutually unbiased (MU)
bases in low dimensions. We find a three-parameter family of triples of
MU bases in dimension four and two inequivalent classes of MU triples in
dimension five. We confirm that the complete sets of (d+1) MU bases are
unique (up to equivalence) in dimensions below six, using only
elementary arguments for d less than five.
Controlled implementation of two-photon controlled phase gate within a
network
(pp0821-0828)
Yan
Xia, Jie Song, Zhen-Biao Yang, and Shi-Biao Zheng
We propose a protocol to controlled implement the two-photon controlled
phase gate within a network by using interference of polarized photons.
The realization of this protocol is appealing due to the fact that the
quantum state of light is robust against the decoherence, and photons
are ideal carriers for transmitting quantum information over long
distances. The proposed setup involves simple linear optical elements
and the conventional photon detectors that only distinguish the vacuum
and nonvacuum Fock number states. This can greatly simplify the
experimental realization of a linear optical quantum computer.
Criterion for k-separability in mixed multipartite states
(pp0829-0836)
Andreas
Gabriel, Beatrix C. Hiesmayr, and Marcus Huber
Using a recently introduced framework, we derive criteria for quantum
k-separability, which are easily computed. In the case k=2, our criteria
are equally strong to the best methods known so far, while in all other
cases there are currently no comparable criteria known. We also show how
the criteria can be implemented experimentally.
Quantum guessing via Deutsch-Jozsa
(pp0837-0847)
Michael
Nathanson
We examine the "Guessing Secrets" problem arising in internet routing,
in which the goal is to discover the identity of two objects from a
known finite set $\Omega$ by asking yes/no questions. The best known
classical algorithm requires $O(\log N)$ questions and $O(\log^2 N)$
steps to process the answers, where $N = \vert \Omega \vert$. We apply
the Deutsch-Jozsa algorithm and show that the number of necessary calls
to the oracle is independent of the size of the domain and that the
output from each run of the algorithm has immediate meaning. In doing
so, we extend the types of questions that the quantum algorithms can be
used to solve.
Limits on entropic uncertainty relations
(pp0848-0858)
Andris
Ambainis
We consider entropic uncertainty relations for outcomes of the
measurements of a quantum state in 3 or more mutually unbiased bases (MUBs),
chosen from the standard construction of MUBs in prime dimension. We
show that, for any choice of 3 MUBs and at least one choice of a larger
number of MUBs, the best possible entropic uncertainty relation can be
only marginally better than the one that trivially follows from the
relation by Maassen and Uffink for 2 bases.
Hardy's non-locality and generalized non-local theory
(pp0859-0871)
Sujit
K. Choudhary, Sibasish Ghosh, Guruprasad Kar, Samir Kunkri, Ramij
Rahaman, and Anirban Roy Hardy's
non-locality theorem for multiple two-level systems is explored in the
context of generalized non-local theory. We find non-local but
non-signaling probabilities satisfying Hardy's argument for two
two-level and three two-level systems. Maximum probability of success of
Hardy's argument is obtained for three two-level systems in quantum
theory as well as in a more generalized theory. Interestingly, the
maximum in the generalized non-local theory for both the two two-level
systems and three two-level systems turns out to be the same.
Quantum addition circuits and unbounded fan-out
(pp0872-0890)
Yasuhiro
Takahashi, Seiichiro Tani, and Noboru Kunihiro
We first show how to construct an $O(n)$-depth $O(n)$-size quantum
circuit for addition of two $n$-bit binary numbers with no ancillary
qubits. The exact size is $7n-6$, which is smaller than that of any
other quantum circuit ever constructed for addition with no ancillary
qubits. Using the circuit, we then propose a method for constructing an
$O(d(n))$-depth $O(n)$-size quantum circuit for addition with $O(n/d(n))$
ancillary qubits for any $d(n) = \Omega(\log n)$. If we are allowed to
use unbounded fan-out gates with length $O(n^{\varepsilon})$ for an
arbitrary small positive constant $\varepsilon$, we can modify the
method and construct an $O(e(n))$-depth $O(n)$-size circuit with $o(n)$
ancillary qubits for any $e(n) = \Omega(\log^* n)$. In particular, these
methods yield efficient circuits with depth $O(\log n)$ and with depth
$O(\log^* n)$, respectively. We apply our circuits to constructing
efficient quantum circuits for Shor's discrete logarithm algorithm.
back to QIC online Front page
|