QIC Abstracts

 Vol.4 No.3 May 30, 2004
Research and Review Articles:
Scalable trapped ion quantum computation with a probabilistic ion-photon mapping (pp165-173)
        L.-M. Duan, B.B. Blinov, D.L. Moehring and C. Monroe
We propose a method for scaling trapped ions for large-scale quantum computation and communication based on a probabilistic ion-photon mapping. Deterministic quantum gates between remotely located trapped ions can be achieved through detection of spontaneously-emitted photons, accompanied by the local Coulomb interaction between neighboring ions. We discuss gate speeds and tolerance to experimental noise for different probabilistic entanglement schemes.

An exact effective two-qubit gate in a chain of three spins (pp174-185)
        M.-H. Yung, D.W. Leung and S. Bose
We show that an effective two-qubit gate can be obtained from the free evolution of three spins in a chain with nearest neighbor XY coupling, without local manipulations. This gate acts on the two remote spins and leaves the mediating spin unchanged. It can be used to perfectly transfer an arbitrary quantum state from the first spin to the last spin or to simultaneously communicate one classical bit in each direction. One ebit can be generated in half of the time for state transfer. For longer spin chains, we present methods to create or transfer entanglement between the two end spins in half of the time required for quantum state transfer, given tunable coupling strength and local magnetic field. We also examine imperfect state transfer through a homogeneous XY chain.

Quantum logical networks for probabilistic teleportation of many particle state of general form (pp186-195)
        T. Gao, F.-L. Yan and Z.-X. Wang
The scheme for probabilistic teleportation of an $N$-particle state of general form is proposed. As the special cases we construct efficient quantum logic networks for implementing probabilistic teleportation of a two-particle state, a three-particle state and a four-particle state of general form, built from single qubit gates, two-qubit controlled-not gates, Von Neumann measurement and classically controlled operations.

Entanglement concentration of individual photon pairs via linear optical logic (pp196-200)
        C.-W. Zhang
We propose a scheme for concentrating nonmaximally pure and mixed
polarization-entangled state of individual photon pairs. The scheme uses only simple linear optical elements and may be feasible within current optical technology.

How significant are the known collision and element distinctness quantum algorithms? (pp201-206)
        L. Grover and T. Rudolph
Quantum search is a technique for searching $N$ possibilities for a desired target in $O(\sqrt{N})$ steps. It has been applied in the design of quantum algorithms for several structured problems. Many of these algorithms require significant amount of quantum hardware. In this paper we propose the criterion that an algorithm which requires $O(S)$ hardware should be considered significant if it produces a speedup of better than $O\left(\sqrt{S}\right)$ over a simple quantum search algorithm. This is because a speedup of $O\left(\sqrt{S}\right)$ can be trivially obtained by dividing the search space into $S$ separate parts and handing the problem to $S$ independent processors that do a quantum search (in this paper we drop all logarithmic factors when discussing time/space complexity). Known algorithms for collision and element distinctness exactly saturate the criterion.

Simplifying Schmidt number witnesses via higher-dimensional embeddings (pp207-221)
        F. Hulpke, D. Bruss, M. Levenstein and A. Sanpera
We apply the generalised concept of witness operators to arbitrary convex sets, and review the criteria for the optimisation of these general witnesses. We then define an embedding of state vectors and operators into a higher-dimensional Hilbert space. This embedding leads to a connection between any Schmidt number witness in the original Hilbert space and a witness for Schmidt number two (i.e. the most general entanglement witness) in the appropriate enlarged Hilbert space. Using this relation we arrive at a conceptually simple method for the construction of Schmidt number witnesses in bipartite systems.

An upper bound on the threshold quantum decoherence rate (pp222-228)
        A.A. Razborov
Let $\eta_0$ be the supremum of those $\eta$ for which every poly-size quantum circuit can be simulated by another poly-size quantum circuit with gates of fan-in $\leq 2$ that tolerates random noise independently occurring on all wires at the constant rate $\eta$. Recent fundamental results showing the principal fact $\eta_0>0$ give estimates like $\eta_0\geq 10^{-6}\mbox{--}10^{-4}$, whereas the only upper bound known before is $\eta_0\leq 0.74$.}{In this note we improve the latter bound to $\eta_0\leq 1/2$, under the assumption ${\bf QP}\not\subseteq {\bf QNC^1}$. More generally, we show that if the decoherence rate $\eta$ is greater than 1/2, then we can not even store a single qubit for more than logarithmic time. Our bound also generalizes to the simulating circuits allowing gates of any (constant) fan-in $k$, in which case we have $\eta_0\leq 1-\frac 1k$.

Quantum solution to the hidden subgroup problem for Poly-Near-Hamiltonian groups (pp229-235)
        D. Gavinsky
The Hidden Subgroup Problem (HSP) has been widely studied in the context of quantum computing and is known to be efficiently solvable for Abelian groups, yet appears to be difficult for many non-Abelian ones. An efficient algorithm for the HSP over a group \f G\ runs in time polynomial in \f{n\deq\log|G|.} For any subgroup \f H\ of \f G, let \f{N(H)} denote the normalizer of \f H. Let \MG\ denote the intersection of all normalizers in \f G (i.e., \f{\MG=\cap_{H\leq G}N(H)}). \MG\ is always a subgroup of \f G and the index \f{[G:\MG]} can be taken as a measure of ``how non-Abelian'' \f G is (\f{[G:\MG] = 1} for Abelian groups). This measure was considered by Grigni, Schulman, Vazirani and Vazirani, who showed that whenever \f{[G:\MG]\in\exp(O(\log^{1/2}n))} the corresponding HSP can be solved efficiently (under certain assumptions). We show that whenever \f{[G:\MG]\in\poly(n)} the corresponding HSP can be solved efficiently, under the same assumptions (actually, we solve a slightly more general case of the HSP and also show that some assumptions may be relaxed).

back to QIC online Front page