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
|