QIC Abstracts

 Vol.10 No.7&8 July 1, 2010

Research Articles:

Universal quantum computation in a hidden basis (pp0541-0561)
L.M. Ioannou and M. Mosca
Let $\ketz$ and $\keto$ be two states that are promised to come from known subsets of orthogonal subspaces, but are otherwise unknown. Our paper probes the question of what can be achieved with respect to the basis $\{\ketz,\keto\}^{\otimes n}$ of $n$ logical qubits, given only a few copies of the unknown states $\ketz$ and $\keto$. A phase-invariant operator is one that is unchanged under the relative phase-shift $\keto \mapsto e^{i \theta}\keto$, for any $\theta$, of all of the $n$ qubits. We show that phase-invariant unitary operators can be implemented exactly with no copies and that phase-invariant states can be prepared exactly with at most $n$ copies each of $\ket{\0}$ and $\ket{\1}$; we give an explicit algorithm for state preparation that is efficient for some classes of states (e.g. symmetric states). We conjecture that certain non-phase-invariant operations are impossible to perform accurately without many copies. Motivated by optical implementations of quantum computers, we define ``quantum computation in a hidden basis'' to mean executing a quantum algorithm with respect to the phase-shifted hidden basis $\{\ketz, e^{i\theta}\keto\}$, for some potentially unknown $\theta$; we give an efficient approximation algorithm for this task, for which we introduce an analogue of a coherent state of light, which serves as a bounded quantum phase reference frame encoding $\theta$. Our motivation was quantum-public-key cryptography, however the techniques are general. We apply our results to quantum-public-key authentication protocols, by showing that a natural class of digital signature schemes for classical messages is insecure. We also give a protocol for identification that uses many of the ideas discussed and whose security relates to our conjecture (but we do not know if it is secure).

Nonlinear and linear entanglement witnesses for bipartite systems via exact convex optimization (pp0562-0579)
M. Jafarizadeh, A. Heshmati, and K. Aghayar
Linear and nonlinear entanglement witnesses for a given bipartite quantum systems are constructed. Using single particle feasible region, a way of constructing effective entanglement witnesses for bipartite systems is provided by exact convex optimization. Examples for some well known two qutrit quantum systems show these entanglement witnesses in most cases, provide necessary and sufficient conditions for separability of given bipartite system. Also this method is applied to a class of bipartite qudit quantum systems with details for d=3, 4 and 5.

Limitations of passive protection of quantum information (pp0580-0618)
F. Pastawski, A. Kay, N. Schuch, and I. Cirac 
The ability to protect quantum information from the effect of noise is one of the major goals of quantum information processing. In this article, we study limitations on the asymptotic stability of quantum information stored in passive $N$-qubit systems. We consider the effect of small imperfections in the implementation of the protecting Hamiltonian in the form of perturbations or weak coupling to a ground state environment. We thus depart from the usual Markovian approximation for a thermal bath by conce ntrating on models for which part of the evolution can be calculated exactly. We prove that, regardless of the protecting Hamiltonian, there exists a perturbed evolution that necessitates a final error correcting step for the state of the memory to be read. Such an error correction step is shown to require a finite error threshold, the lack thereof being exemplified by the 3D XZ-compass model \cite{bacon-2006}. We go on to present explicit weak Hamiltonian perturbations which destroy the logical information stored in the 2D toric code in a time $O(\log(N))$.

The semigroup sturucture of Gaussian channels (pp0619-0635)
T. Heinosaari, A.S. Holevo, and M.M. Wolf
We investigate the semigroup structure of bosonic Gaussian quantum channels. Particular focus lies on the sets of channels which are divisible, idempotent or Markovian (in the sense of either belonging to one-parameter semigroups or being infinitesimal divisible). We show that the non-compactness of the set of Gaussian channels allows for remarkable differences when comparing the semigroup structure with that of finite dimensional quantum channels. For instance, every irreversible Gaussian channel is shown to be divisible in spite of the existence of Gaussian channels which are not infinitesimal divisible. A simpler and known consequence of non-compactness is the lack of generators for certain reversible channels. Along the way we provide new representations for classes of Gaussian channels: as matrix semigroup, complex valued positive matrices or in terms of a simple form describing almost all one-parameter semigroups.

Quantum and randomized lower bounds for local search on vertex-transitive graphs (pp0636-0652)
H. Dinh and A. Russell
We study the problem of \emph{local search} on a graph. Given a real-valued black-box function $f$ on the graph's vertices, this is the problem of determining a local minimum of $f$---a vertex $v$ for which $f(v)$ is no more than $f$ evaluated at any of $v$'s neighbors. In 1983, Aldous gave the first strong lower bounds for the problem, showing that any randomized algorithm requires $\Omega(2^{n/2 - o(n)} )$ queries to determine a local minima on the $n$-dimensional hypercube. The next major step forward was not until 2004 when Aaronson, introducing a new method for query complexity bounds, both strengthened this lower bound to $\Omega(2^{n/2}/n^2)$ and gave an analogous lower bound on the quantum query complexity. While these bounds are very strong, they are known only for narrow families of graphs (hypercubes and grids). We show how to generalize Aaronson's techniques in order to give randomized (and quantum) lower bounds on the query complexity of local search for the family of vertex-transitive graphs. In particular, we show that for any vertex-transitive graph $G$ of $N$ vertices and diameter $d$, the randomized and quantum query complexities for local search on $G$ are $\Omega\left({\sqrt{N}}/{d\log N}\right)$ and $\Omega\left({\sqrt[4]{N}}/{\sqrt{d\log N}}\right)$, respectively.

Nuclear spin $3/2$ electric quadrupole relaxation as a quantum computation process (pp0653-0668)
A.M. Souza, A. Gavini-Viana, I.S. Oliveira, R.S. Sarthour, R. Auccaise, E.R. deAzevedo, and  T.J. Bonagamba
In this work we applied a quantum circuit treatment to describe the nuclear spin relaxation. From the Redfield theory, we obtain a description of the quadrupolar relaxation as a computational process in a spin 3/2 system, through a model in which the environment is comprised by five qubits and three different quantum noise channels. The interaction between the environment and the spin 3/2 nuclei is described by a quantum circuit fully compatible with the Redfield theory of relaxation. Theoretical predictions are compared to experimental data, a short review of quantum channels and relaxation in NMR qubits is also present.

Limitations on the simulation of non-sparse Hamiltonians (pp0669-0684)
A.M. Childs and R. Kothari
The problem of simulating sparse Hamiltonians on quantum computers is well studied. The evolution of a sparse $N \times N$ Hamiltonian $H$ for time $t$ can be simulated using $\O(\norm{Ht} \poly(\log N))$ operations, which is essentially optimal due to a no--fast-forwarding theorem. Here, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, ruling out generic simulations taking time $\o(\norm{Ht})$, even though $\norm{H}$ is not a unique measure of the size of a dense Hamiltonian $H$. We also present a stronger limitation ruling out the possibility of generic simulations taking time $\poly(\norm{Ht},\log N)$, showing that known simulations based on discrete-time quantum walk cannot be dramatically improved in general. On the positive side, we show that some non-sparse Hamiltonians can be simulated efficiently, such as those with graphs of small arboricity.

Extraspecial two-Groups, generalized Yang-Baxter equations and braiding quantum gates (pp0685-0702)
E.C. Rowell, Y. Zhang, Y.-S. Wu, and M.-L. Ge
In this paper we describe connections among extraspecial 2-groups, unitary representations of the braid group and multi-qubit braiding quantum gates. We first construct new representations of extraspecial 2-groups. Extending the latter by the symmetric group, we construct new unitary braid representations, which are solutions to generalized Yang-Baxter equations and use them to realize new braiding quantum gates. These gates generate the GHZ (Greenberger-Horne-Zeilinger) states, for an arbitrary (particularly an \emph{odd}) number of qubits, from the product basis. We also discuss the Yang-Baxterization of the new braid group representations, which describes unitary evolution of the GHZ states. Our study suggests that through their connection with braiding gates, extraspecial 2-groups and the GHZ states may play an important role in quantum error correction and topological quantum computing.

Bell inequalities from multilinear contractions (pp0703-0719)
A. Salles, D. Cavalcanti, A. Acin, D. Perez-Garcia, and M.M. Wolf
We provide a framework for Bell inequalities which is based on multilinear contractions. The derivation of the inequalities allows for an intuitive geometric depiction and their violation within quantum mechanics can be seen as a direct consequence of non-vanishing commutators. The approach is motivated by generalizing recent work on non-linear inequalities which was based on the moduli of complex numbers, quaternions and octonions. We extend results on Peres' conjecture about the validity of Bell inequalities for quantum states with positive partial transposes. Moreover, we show the possibility of obtaining unbounded quantum violations albeit we also prove that quantum mechanics can only violate the derived inequalities if three or more parties are involved.

back to QIC online Front page