QIC Abstracts

 Vol.9 No.7&8 July 1, 2009

Research Articles: 

A comparative code study for quantum fault tolerance (pp0541-0572)
A.W. Cross, D.P. DiVincenzo, B.M. Terhal
We study a comprehensive list of quantum codes as candidates for codes used at the physical level in a fault-tolerant code architecture. Using the Aliferis-Gottesman-Preskill (AGP) ex-Rec method we calculate the pseudo-threshold for these codes against depolarizing noise at various levels of overhead. We estimate the logical noise rate as a function of overhead at a physical error rate of $p_0=1 \times 10^{-4}$. The Bacon-Shor codes and the Golay code are the best performers in our study.

Quantum multiplexing with optical coherent states (pp0573-0593)
J.C. Garcia-Escartin and P. Chamorro-Posada
In this paper, we propose a novel quantum multiple access technique based on optical coherent states. The information of several coherent state optical qubits is combined into a single qudit, which is the superposition of almost orthogonal coherent states. The original information is encoded into a new Hilbert space with the help of a quantum multiplexer (QMUX) and then recovered at the other end with a quantum demultiplexer (QDEMUX). We introduce the optical tools that complete the coherence state quantum computation model and give the desired circuits. The proposed system can admit a number of users above the optimal limit at the cost of a degradation of the transmitted data. In this and some other aspects, it can be regarded as a quantum analogue of classical Code Division Multiple Access techniques.

The decreasing property of relative entropy and the strong superadditivity of quantum channels (pp0594-0609)
G.G. Amosov and S. Mancini
We argue that a fundamental (conjectured) property of memoryless quantum channels, namely the strong superadditivity, is intimately related to the decreasing property of the quantum relative entropy. Using the latter we first give, for a wide class of input states, an estimation of the output entropy for phase damping channels and some Weyl quantum channels. Then we prove, without any input restriction, the strong superadditivity for several quantum channels, including depolarizing quantum channels, quantum-classical channels and quantum erasure channels.

An O(m^2)-depth quantum algorithm for the elliptic curve discrete logarithm problem over GF(2^m) (pp0610-0621)
D. Maslov, J. Mathew, D. Cheung, and D.K. Pradhan
We consider a quantum polynomial-time algorithm which solves the discrete logarithm problem for points on elliptic curves over $GF(2^m)$. We improve over earlier algorithms by constructing an efficient circuit for multiplying elements of binary finite fields and by representing elliptic curve points using a technique based on projective coordinates. The depth of our proposed implementation, executable in the Linear Nearest Neighbor (LNN) architecture, is $O(m^2)$, which is an improvement over the previous bound of $O(m^3)$ derived assuming no architectural restrictions.

An entropy inequality (pp0622-0627)
M. Hellmund and A. Uhlmann
Let $S(\rho)=-\Tr (\rho\log\rho)$ be the von Neumann entropy of an $N$-dimensional quantum state $\rho$ and $e_2(\rho)$ the second elementary symmetric polynomial of the eigenvalues of $\rho$. We prove the inequality S(\rho) \;\le \; c(N) \; \sqrt{e_2(\rho)} where $c(N)=\log(N) \, \sqrt{\frac{2N}{N-1}}$. This generalizes an inequality given by Fuchs and Graaf~\cite{fuchsgraaf} for the case of one qubit, i.e., $N=2$. Equality is achieved if and only if $\rho$ is either a pure or the maximally mixed state. This inequality delivers new bounds for quantities of interest in quantum information theory, such as upper bounds for the minimum output entropy and the entanglement of formation as well as a lower bound for the Holevo channel capacity.

Quantum search of partially ordered sets (pp0628-0647)
A. Montanaro
We investigate the generalisation of quantum search of unstructured and totally ordered sets to search of partially ordered sets (posets). Two models for poset search are considered. In both models, we show that quantum algorithms can achieve at most a quadratic improvement in query complexity over classical algorithms, up to logarithmic factors; we also give quantum algorithms that almost achieve this optimal reduction in complexity. In one model, we give an improved quantum algorithm for searching forest-like posets; in the other, we give an optimal $O(\sqrt{m})$-query quantum algorithm for searching posets derived from $m \times m$ arrays sorted by rows and columns. This leads to a quantum algorithm that finds the intersection of two sorted lists of $n$ integers in $O(\sqrt{n})$ time, which is optimal.

Entanglement-resistant two-Prover interactive proof systems and non-adaptive PIRs (pp0648-0656)
R. Cleve, D. Gavinsky, and R. Jain
We show that every language in $\np$ is recognized by a two-prover interactive proof system with the following properties. The proof system is entanglement-resistant (i.e., its soundness is robust against provers who have prior shared entanglement), it has one round of interaction, the provers' answers are single bits, and the completeness-soundness gap is constant (formally, $\np\subseteq \xmips_{1-\varepsilon,1/2+\varepsilon}\mo[2]$, for any~$\varepsilon$ such that $0 < \varepsilon < 1/4$). Our result is based on the ``oracularizing" property of a particular private information retrieval scheme (PIR), and it suggests that investigating related properties of other PIRs might bear further fruit.

Correlation loss and multipartite entanglement across a black hole horizon (pp0657-0665)
G. Adesso and I. Fuentes-Schuller
We investigate the Hawking effect on entangled fields. By considering a scalar field which is in a two-mode squeezed state from the point of view of freely falling (Kruskal) observers crossing the horizon of a Schwarzschild black hole, we study the degradation of quantum and classical correlations in the state from the perspective of physical (Schwarzschild) observers confined outside the horizon. Due to monogamy constraints on the entanglement distribution, we show that the lost bipartite entanglement is recovered as multipartite entanglement among modes inside and outside the horizon. In the limit of a small-mass black hole, no bipartite entanglement is detected outside the horizon, while the genuine multipartite entanglement interlinking the inner and outer regions grows infinitely.

Latency in local, two-dimensional, fault-tolerant quantum computing (pp0666-0682)
F.M. Spedalieri and V.P. Roychowdhury
We analyze the latency of fault-tolerant quantum computing based on the 9-qubit Bacon-Shor code using a local, two-dimensional architecture. We embed the data qubits in a 7 by 7 array of physical qubits, where the extra qubits are used for ancilla preparation and qubit transportation by means of a SWAP chain. The latency is reduced with respect to a similar implementation using Steane's 7-qubit code~\cite{svore2007a}. Furthermore, the error threshold is also improved to $2.02 \times 10^{-5}$, when memory errors are taken to be one tenth of the gate error rates.

Practical random number generation protocol for entanglement-based quantum key distribution (pp0683-0692)
G.B. Xavier, T. Ferreira da Silva, G. Vilela de Faria, G.P. Temporao, and J.P. von der Weid
A simple protocol which takes advantage of the inherent random times of detections in single photon counting modules is presented for random active basis choices when using entanglement-based protocols for Quantum Key Distribution (QKD). It may also be applicable to the BB84 protocol in certain cases. The scheme presented uses the single photon detectors already present on a QKD setup, working on the same rate as the system is capable of detecting, and is, therefore, not limited by the output rates of quantum random number generators. This protocol only requires small hardware modifications making it an attractive solution. We perform a proof-of-principle experiment employing a spontaneous parametric down-conversion process in a $\chi^{(2)}$ non-linear crystal to demonstrate the feasibility of our scheme, and show that the generated sequence passes randomness tests.

Auto-adaptive interval selection for quantum key distribution (pp0693-0700)
J. Han and X. Qian
Key reconciliation plays an important role in quantum key distribution, as well as shared bit string distillation. To distill efficiently the final key a so-called Winnow protocol has been proposed. However, how to choose the interval length of the shared string to maximize the Winnow efficiency is difficult in practical program processing. Because the interval choice remains an open problem the key rate of the Winnow protocol is not as high as the one calculated in theory. Consequently, the Winnow protocol is difficult to efficiently employ in application. In this paper we first analytically investigate the dependence of the interval length on the error distribution and the code. Then an auto-adaptive interval selection algorithm is proposed. In addition, new characteristics of the protocol are investigated.

Classical approximation schemes for the ground-state energy of quantum and classical Ising spin Hamiltonians on planar graphs (pp0701-0720)
N. Bansal, S. Bravyi, and B.M. Terhal
We describe a classical approximation algorithm for evaluating the ground state energy of the classical Ising Hamiltonian with linear terms on an arbitrary planar graph. The running time of the algorithm grows linearly with the number of spins and exponentially with $1/\epsilon$, where $\epsilon$ is the worst-case relative error. This result contrasts the well known fact that exact computation of the ground state energy for the two-dimensional Ising spin glass model is NP-hard. We also present a classical approximation algorithm for the quantum Local Hamiltonian Problem or Quantum Ising Spin Glass problem on a planar graph {\em with bounded degree} which is known to be a QMA-complete problem. Using a different technique we find a classical approximation algorithm for the quantum Ising spin glass problem on the simplest planar graph with unbounded degree, the star graph.

back to QIC online Front page