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