QIC Abstracts

 Vol.8 No.5 May 1, 2008

Research Articles: 
The complexity of stoquastic local Hamiltonian problems (pp0361-0385)
S. Bravyi, D.P. DiVincenzo, R. Oliveira, and B.M. Terhal
We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys the condition that all off-diagonal matrix elements in the standard basis are real and non-positive. We will call such Hamiltonians, which are common in the natural world, stoquastic. An equivalent characterization of stoquastic Hamiltonians is that they have an entry-wise non-negative Gibbs density matrix for any temperature. We prove that LH-MIN for stoquastic Hamiltonians belongs to the complexity class \AM{}--- a probabilistic version of \NP{} with two rounds of communication between the prover and the verifier. We also show that $2$-local stoquastic LH-MIN is hard for the class \MA. With the additional promise of having a polynomial spectral gap, we show that stoquastic LH-MIN belongs to the class \POSTBPP=\BPPpath --- a generalization of \BPP{} in which a post-selective readout is allowed. This last result also shows that any problem solved by adiabatic quantum computation using stoquastic Hamiltonians is in PostBPP.

Generation and detection of photonic qutrit states by linear optics (pp0386-0398)
Y.-T. Chen and G. Bjork
We address the problem of generation and detection of the four mutually unbiased biphoton polarization-qutrit bases by linear optics. First, the generation of the bases is studied. Our numeric results show that the linear optics method can be used to generate the 4 mutually unbiased basis qutrit states probabilistically with high fidelity. Second, we investigate whether or not linear polarization-optics components are sufficient to realize the simultaneous detection of the qutrit states forming a complete basis. Analytical results show that every state in two of the bases, namely only half of the 4 mutually unbiased bases qutrit states can be identified.

Trade-off between the tolerance of located and unlocated errors in nondegenrate quantum (pp0399-0410)
H.L. Haselgrove and P.P. Rohde
In a recent study [Rohde et al., quant-ph/0603130 (2006)] of several quantum error correcting protocols designed for tolerance against qubit loss, it was shown that these protocols have the undesirable effect of magnifying the effects of depolarization noise. This raises the question of which general properties of quantum error-correcting codes might explain such an apparent trade-off between tolerance to located and unlocated error types. We extend the counting argument behind the well-known quantum Hamming bound to derive a bound on the weights of combinations of located and unlocated errors which are correctable by nondegenerate quantum codes. Numerical results show that the bound gives an excellent prediction to which combinations of unlocated and located errors can be corrected {\em with high probability} by certain large degenerate codes. The numerical results are explained partly by showing that the generalized bound, like the original, is closely connected to the information-theoretic quantity the {\em quantum coherent information}. However, we also show that as a measure of the exact performance of quantum codes, our generalized Hamming bound is provably far from tight.

Constructions for quantum computing with symmetrized gates (pp0411-0429)
G. Ivanyos, A.B. Nagy, and L. Ronyai 
We investigate constructions for simulating quantum computers with a polynomial slowdown on ensembles composed of qubits on which symmetrized versions of one- and two-qubit gates can be performed. The simulation is based on taking Lie commutators of symmetrized Hamiltonians to extract Hamiltonians at desired local positions. During the simulation, only a part of the qubits can be used for storing information, the others are left unchanged by the commutators. We propose constructions for various symmetry groups where a pretty large fraction of the qubits can be used. As a few of the other qubits need to be set to one, our construction requires individual initialization of some of the qubits.

An extremal result for geometries in the one-way measurement model (pp0430-0437)
N. de Beaudrap and M. Pei
We present an extremal result for the class of graphs $G$ which (together with some specified sets of input and output vertices, $I$ and $O$) have a certain ``flow'' property introduced by Danos and Kashefi for the one-way measurement model of quantum computation. The existence of a flow for a triple $(G,I,O)$ allows a unitary embedding to be derived from any choice of measurement bases allowed in the one-way measurement model. We prove an upper bound on the number of edges that a graph $G$ may have, in order for a triple $(G,I,O)$ to have a flow for some $I, O \subseteq V(G)$, in terms of the number of vertices in $G$ and $O$. This implies that finding a flow for a triple $(G,I,O)$ when $\lvert I \rvert = \lvert O \rvert = k$ (corresponding to unitary transformations in the measurement model) and $\lvert V(G) \rvert = n$ can be performed in time $O(k^2 n)$, improving the earlier known bound of $O(km)$ given in \cite{B06a}, where $m = \lvert E(G) \rvert$.

How a Clebsch-Gordan transform helps to solve the Heisenberg hidden subgroup problem (pp0438-0467)
D. Bacon
It has recently been shown that quantum computers can efficiently solve the Heisenberg hidden subgroup problem, a problem whose classical query complexity is exponential. This quantum algorithm was discovered within the framework of using pretty good measurements for obtaining optimal measurements in the hidden subgroup problem. Here we show how to solve the Heisenberg hidden subgroup problem using arguments based instead on the symmetry of certain hidden subgroup states. The symmetry we consider leads naturally to a unitary transform known as the Clebsch-Gordan transform over the Heisenberg group. This gives a new representation theoretic explanation for the pretty good measurement derived algorithm for efficiently solving the Heisenberg hidden subgroup problem and provides evidence that Clebsch-Gordan transforms over finite groups are a new primitive in quantum algorithm design.

A quantum repeater based on decoherence free subspaces (pp0468-0488)
U. Dorner, A. Klein, and D. Jaksch
We study a quantum repeater which is based on decoherence free quantum gates recently proposed by Klein {\it et al.} [Phys. Rev. A, {\bf 73}, 012332 (2006)]. A number of operations on the decoherence free subspace in this scheme makes use of an ancilla qubit, which undergoes dephasing and thus introduces decoherence to the system. We examine how this decoherence affects entanglement swapping and purification as well as the performance of a quantum repeater. We compare the decoherence free quantum repeater with a quantum repeater based on qubits that are subject to decoherence and show that it outperforms the latter when decoherence due to long waiting times of conventional qubits becomes significant. Thus, a quantum repeater based on decoherence free subspaces is a possibility to greatly improve quantum communication over long or even intercontinental distances.

Efficient quantum circuits for approximating the Jones polynomial (pp0489-0500)
Y. Nakajima, Y. Kawano, and H. Sekigawa
Freedman, Kitaev, and Wang proved the equivalence between quantum field theory and quantum computation, and consequently showed that the problem of approximating the Jones polynomial (a knot invariant) at the fifth root of unity is BQP-complete. Recently, Aharonov, Jones, and Landau proposed a concrete quantum algorithm, called the AJL algorithm, that approximates the Jones polynomial at the $k$th root of unity in polynomial time. In this paper, we propose a new method for implementing the AJL algorithm, which improves the performance from $O(mn\log^2k)$ to $O(mn)$. Here, $n$ is the number of strands, $m$ is the number of the crossings in a braid. Since, in the AJL algorithm, $m$ and $k$ are assumed to be given as polynomials in $n$, the difference in the performance between the original implementation and our design is significant if $k$ is a large-degree polynomial.

Book Review:
On “xxxxx (authored by )” (pp0359-0360)
G.J. Milburn

back to QIC online Front page