|
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
|
