Vol.10 No.3&4 March 1, 2010

Research Articles:

The quantum query complexity of certification (pp0181-0189)
          A. Ambainis, A.M. Childs, F. Le Gall, and S. Tani
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced \nand formula. We show that the query complexity is $\tilde\Theta(d^{(k+1)/2})$ for 0-certificates, and $\tilde\Theta(d^{k/2})$ for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is $\tilde O(d^{(k+1)/2})$. Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.

A quantum coupler and the harmonic oscillator interacting with a reservoir: Defining the relative phase gate (pp0190-0200)
          P.C. Garcia Quijas and L.M. Arevalo Aguilar
In order to be able to study dissipation, the interaction between a single system and their environment was introduced in quantum mechanics. Master and quantum Langeving equations was derived. Moreover, decoherence has been studied using this approach. One of the most commonly used model in this research field is a single harmonic oscillator interacting with a reservoir. In this work we analytically solve this model, in the resonance case, using the evolution operator method. Then, we use this result to study a quantum coupler, which is a particular case where there are a finite number of harmonic oscillators interacting with the single one. After that, we focuses in the analisis of the conditional quantum dynamics of the quantum coupler (using the computational basis of two qubits) by choosing a proper interaction time. This conditional dynamics provides a realization of a new quantum phase gate, which we call the relative phase gate. To the best of our knowledge, this phase gate has not been previously defined or proposed.

Quantum information processing with quantum zeno many-body dynamics (pp0201-0222)
          A. Monras and O. Romero-Isart
We show how the quantum Zeno effect can be exploited to control quantum many-body dynamics for quantum information and computation purposes. In particular, we consider a one dimensional array of three level systems interacting via a nearest-neighbour interaction. By encoding the qubit on two levels and using simple projective frequent measurements yielding the quantum Zeno effect, we demonstrate how to implement a well defined quantum register, quantum state transfer on demand, universal two-qubit gates and two-qubit parity measurements. Thus, we argue that the main ingredients for universal quantum computation can be achieved in a spin chain with an {\em always-on} and {\em constant} many-body Hamiltonian. We also show some possible modifications of the initially assumed dynamics in order to create maximally entangled qubit pairs and single qubit gates.

Computable constraints on entanglement-sharing of multipartite quantum states (pp0223-0233)
          Y.-C. Ou and M.S. Byrd
Negativity is regarded as an important measure of entanglement in quantum information theory. In contrast to other measures of entanglement, it is easily computable for bipartite states in arbitrary dimensions. In this paper, based on the negativity and realignment, we provide a set of entanglement-sharing constraints for multipartite states, where the entanglement is not necessarily limited to bipartite and pure states, thus aiding in the quantification of constraints for entanglement-sharing. These may find applications in studying many-body systems.

A promiseBQP-complete string rewriting problem (pp0234-0257)
          D. Janzing and P. Wocjan
We consider the following combinatorial problem. We are given three strings s, t, and t' of length L over some fixed finite alphabet and an integer $m$ that is polylogarithmic in L. We have a symmetric relation on substrings of constant length that specifies which substrings are allowed to be replaced with each other. Let $\Delta (n)$ denote the difference between the numbers of possibilities to obtain $t$ from $s$ and $t'$ from $s$ after $n \in\N$  replacements. The problem is to determine the sign of $\Delta(m)$. As promises we have a gap condition and a growth condition. The former states that $|\Delta (m)| \geq \epsilon\,c^m$ where $\epsilon$ is inverse polylogarithmic in $L$ and $c>0$ is a constant. The latter is given by $\Delta (n) \leq c^n$ for all $n$.  We show that this problem is PromiseBQP-complete, i.e., it represents the class of problems that can be solved efficiently on a quantum computer.

Classical simulation of quantum computation, the gottesman-Knill theorem, and slightly beyond (pp0258-0271)
          M. Van den Nest
We study classical simulation of quantum computation, taking the Gottesman-Knill theorem as a starting point. We show how each Clifford circuit can be reduced to an equivalent, manifestly simulatable circuit (normal form). This provides a simple proof of the Gottesman-Knill theorem without resorting to stabilizer techniques. The normal form highlights why Clifford circuits have such limited computational power in spite of their high entangling power. At the same time, the normal form shows how the classical simulation of Clifford circuits fits into the standard way of embedding classical computation into the quantum circuit model. This leads to simple extensions of Clifford circuits which are classically simulatable. These circuits can be efficiently simulated by classical sampling (``weak simulation'') even though the problem of exactly computing the outcomes of measurements for these circuits (``strong simulation'') is proved to be $\#\mathbf{P}$-complete---thus showing that there is a separation between weak and strong classical simulation of quantum computation.

Single-photon entanglement concentration for long-distance quantum communication (pp0272-0281)
          Y.-B. Sheng, F.-G. Deng, and H.-Y. Zhou
We present a single-photon entanglement concentration protocol for long-distance quantum communication with quantum nondemolition detector. It is the first concentration protocol for single-photon entangled states and it dose not require the two parties of quantum communication to know the accurate information about the coefficient $\alpha$ and $\beta$ of the less entangled states. Also, it does not resort to sophisticated single-photon detectors, which makes this protocol more feasible in current experiments. Moreover, it can be iterated to get a higher efficiency and yield. All these advantages maybe make this protocol have more practical applications in long-distance quantum communication and quantum internet.

Finding conjugate stabilizer subgroups in $\PSL$ and related groups (pp0282-0291)
          DA. Denney, C. Moore, and A. Russell
We reduce a case of the hidden subgroup problem (HSP) in $\SL$, $\PSL$, and $\PGL$, three related families of finite groups of Lie type, to efficiently solvable HSPs in the affine group $\AGL$. These groups act on projective space in an ``almost'' 3-transitive way, and we use this fact in each group to distinguish conjugates of its Borel (upper triangular) subgroup, which is also the stabilizer subgroup of an element of projective space. Our observation is mainly group-theoretic, and as such breaks little new ground in quantum algorithms. Nonetheless, these appear to be the first positive results on the HSP in finite simple groups such as $\PSL$.

Simplifying quantum double Hamiltonians using perturbative gadgets (pp0292-0324)
          R. Konig
Perturbative gadgets were originally introduced to generate effective $k$-local interactions in the low-energy sector of a $2$-local Hamiltonian. Extending this idea, we present gadgets which are specifically suited for realizing Hamiltonians exhibiting non-abelian anyonic excitations. At the core of our construction is a perturbative analysis of a widely used hopping-term Hamiltonian. We show that in the low-energy limit, this Hamiltonian can be approximated by a certain ordered product of operators. In particular, this provides a simplified realization of Kitaev's quantum double Hamiltonians.

Perfect state transfer, integral circulants, and join of graphs (pp0325-0342)
          R.-J. Angeles-Canul, R.M. Norton, M.C. Opperman, C.C. Paribello, M.C. Russell, and C. Tamon
We propose new families of graphs which exhibit quantum perfect state transfer. Our constructions are based on the join operator on graphs, its circulant generalizations, and the Cartesian product of graphs. We build upon the results of  Ba\v{s}i\'{c} and Petkovi\'{c} ({\em Applied Mathematics Letters} {\bf 22}(10):1609-1615, 2009) and construct new integral circulants and regular graphs with perfect state transfer. More specifically, we show that the integral circulant $\textsc{ICG}_{n}(\{2,n/2^{b}\} \cup Q)$ has perfect state transfer, where $b \in \{1,2\}$, $n$ is a multiple of $16$ and $Q$ is a subset of the odd divisors of $n$. Using the standard join of graphs, we also show a family of double-cone graphs which are non-periodic but exhibit perfect state transfer. This class of graphs is constructed by simply taking the join of the empty two-vertex graph with a specific class of regular graphs. This answers a question posed by Godsil (arxiv.org math/08062074).

Strong NP-hardness of the quantum separability problem (pp0343-0360)
          S. Gharibian
Given the density matrix $\rho$ of a bipartite quantum state, the quantum separability problem asks whether $\rho$ is entangled or separable. In 2003, Gurvits showed that this problem is NP-hard if $\rho$ is located within an inverse exponential (with respect to dimension) distance from the border of the set of separable quantum states. In this paper, we extend this NP-hardness to an inverse polynomial distance from the separable set. The result follows from a simple combination of works by Gurvits, Ioannou, and Liu. We apply our result to show (1) an immediate lower bound on the maximum distance between a bound entangled state and the separable set (assuming $\rm{P}\neq\rm{ NP}$), and (2) NP-hardness for the problem of determining whether a completely positive trace-preserving linear map is entanglement-breaking.

back to QIC online Front page