*
Research Articles:*

**Estimating Jones polynomials
is a complete problem for one clean qubit**
(pp0681-0714)

P.W.
Shor and S.P. Jordan

It is known that evaluating a certain approximation to the Jones
polynomial for the plat closure of a braid is a BQP-complete problem.
That is, this problem exactly captures the power of the quantum circuit
model. The one clean qubit model is a model of quantum computation in
which all but one qubit starts in the maximally mixed state. One clean
qubit computers are believed to be strictly weaker than standard quantum
computers, but still capable of solving some classically intractable
problems. Here we show that evaluating a certain approximation to the
Jones polynomial at a fifth root of unity for the trace closure of a
braid is a complete problem for the one clean qubit complexity class.
That is, a one clean qubit computer can approximate these Jones
polynomials in time polynomial in both the number of strands and number
of crossings, and the problem of simulating a one clean qubit computer
is reducible to approximating the Jones polynomial of the trace closure
of a braid.

**Quantum expanders from any classical
Cayley graph expander**
(pp0715-0721)

A.W.
Harrow

We give a simple recipe for translating walks on Cayley graphs of a
group *G* into a quantum operation on any irrep of *G*. Most
properties of the classical walk carry over to the quantum operation:
degree becomes the number of Kraus operators, the spectral gap becomes
the gap of the quantum operation (viewed as a linear map on density
matrices), and the quantum operation is efficient whenever the classical
walk and the quantum Fourier transform on *G* are efficient. This
means that using classical constant-degree constant-gap families of
Cayley expander graphs on e.g. the symmetric group, we can construct
efficient families of quantum expanders.

**Quantum margulis expanders**
(pp0722-0733)

D.
Gross and J. Eisert

We present a simple way to quantize the well-known Margulis expander
map. The result is a quantum expander which acts on discrete Wigner
functions in the same way the classical Margulis expander acts on
probability distributions. The quantum version shares all essential
properties of the classical counterpart, e.g., it has the same degree
and spectrum. Unlike previous constructions of quantum expanders, our
method does not rely on non-Abelian harmonic analysis. Analogues for
continuous variable systems are mentioned. Indeed, the construction
seems one of the few instances where applications based on discrete and
continuous phase space methods can be developed in complete analogy.

**Efficient 2-designs from bases exist**
(pp0734-0740)

G.
McConnell and D. Gross

We show that in a complex $d$-dimensional vector space, one can find *
O(d)* bases whose elements form a 2-design. Such vector sets
generalize the notion of a maximal collection of mutually unbiased bases
(MUBs). MUBs have many applications in quantum information theory (e.g.\
in state tomography, cloning, or cryptography) -- however it is
suspected that maximal sets exist only in prime-power dimensions. Our
construction offers an efficient alternative for general dimensions. The
findings are based on a framework recently established, which reduces
the construction of such bases to the combinatorial problem of finding
certain highly nonlinear functions between abelian groups.

**Measuring 4-local qubit observables
could probabilistically solve PSPACE**
(pp0741-0755)

P.
Wocjan, D. Janzing, and T. Decker

We consider a hypothetical apparatus that implements measurements for
arbitrary 4-local quantum observables *A* on *n* qubits. The
apparatus implements the ``measurement algorithm'' after receiving a
classical description of *A*. We show that a few precise
measurements applied to a basis state would provide a probabilistic
solution of PSPACE problems. The error probability decreases
exponentially with the number of runs, if the measurement accuracy is of
the order of the spectral gaps of the operator *A*. Moreover,
every decision problem that can be solved by a deterministic quantum
algorithm in *T* time steps can be encoded into a 4-local
observable such that the solution requires only measurements of accuracy
*O(1/T)*. Provided that BQP$\neq$PSPACE, our result shows that
efficient algorithms for precise measurements of general 4-local
observables cannot exist. We conjecture that the class of physically
existing interactions is large enough to allow the conclusion that
precise energy measurements for general many-particle systems require
control algorithms with high complexity.

**Improved one-way rates for BB84 and
6-state protocols**
(pp0756-0772)

O.
Kern and J.M. Renes

We study the advantages to be gained in quantum key distribution (QKD)
protocols by combining the techniques of local randomization, or noisy
preprocessing, and structured (nonrandom) block codes. Extending the
results of [Smith, Renes, and Smolin, {\em Physical Review Letters},
100:170502] pertaining to BB84, we improve the best-known lower bound on
the error rate for the 6-state protocol from 14.11% for local
randomization alone to at least 14.59%. Additionally, we also
study the effects of iterating the combined preprocessing scheme and
find further improvements to the BB84 protocol already at small block
lengths.

**Separability criterion for
multipartite quantum states based on the Bloch representation of density
matrices**
(pp0773-0790)

A.S.M.
Hassan and P.S. Joag

We give a new separability criterion, a necessary condition for
separability of *N*-partite quantum states. The criterion is based
on the Bloch representation of a *N*-partite quantum state and
makes use of multilinear algebra, in particular, the matrization of
tensors. Our criterion applies to *arbitrary* *N*-partite
quantum states in $\mathcal{H}=\mathcal{H}^{d_1}\otimes \mathcal{H}^{d_2}
\otimes \cdots \otimes \mathcal{H}^{d_N}.$ The criterion can test
whether a *N*-partite state is entangled and can be applied to
different partitions of the $N$-partite system. We provide examples that
show the ability of this criterion to detect entanglement. We show that
this criterion can detect bound entangled states. We prove a sufficiency
condition for separability of a 3-partite state, straightforwardly
generalizable to the case *N > 3*, under certain condition. We also
give a necessary and sufficient condition for separability of a class of
*N*-qubit states which includes *N*-qubit PPT states.

**Construction of entanglement
witnesses based on concurrence for multi-qubit states**
(pp0791-0796)

H.
Heydari

We establish a relation between concurrence and entanglement witnesses.
In particular, we construct entanglement witnesses for three-qubit W and
GHZ states in terms of concurrence. We also generalize our construction
for multi-qubit states. This result gives the finest entanglement
witnesses for a given class of state without any optimization.

**Approximate joint measurements of
qubit observables**
(pp0797-0818)

P.
Busch and T. Heinosaari

Joint measurements of qubit observables have recently been studied in
conjunction with quantum information processing tasks such as cloning.
Considerations of such joint measurements have until now been restricted
to a certain class of observables that can be characterized by a form of
covariance. Here we investigate conditions for the joint measurability
of arbitrary pairs of qubit observables. For pairs of noncommuting sharp
qubit observables, a notion of approximate joint measurement is
introduced. Optimal approximate joint measurements are shown to lie in
the class of covariant joint measurements. The marginal observables
found to be optimal approximators are generally not among the coarse-grainings
of the observables to be approximated. This yields scope for the
improvement of existing joint measurement schemes. Both the quality of
the approximations and the intrinsic unsharpness of the approximators
are shown to be subject to Heisenberg-type uncertainty relations.

**Distinguishing quantum operations
having few Kraus operators**
(pp0819-0833)

J.
Watrous

Entanglement is sometimes helpful in distinguishing between quantum
operations, as differences between quantum operations can become
magnified when their inputs are entangled with auxiliary systems. Bounds
on the dimension of the auxiliary system needed to

optimally distinguish quantum operations are known in several
situations. For instance, the dimension of the auxiliary space never
needs to exceed the dimension of the input space of the operations for
optimal distinguishability, while no auxiliary system whatsoever is
needed to optimally distinguish unitary operations. Another bound, which
follows from work of R. Timoney , is that optimal distinguishability is
always possible when the dimension of the auxiliary system is twice the
number of operators needed to express the difference between the quantum
operations in Kraus form. This paper provides an alternate proof of this
fact that is based on concepts and tools that are familiar to quantum
information theorists.

**A panoply of quantum algorithms**
(pp0834-0859)

B.
Furrow

This paper's aim is to explore improvements to, and applications of, a
fundamental quantum algorithm invented by Grover\cite{grover}. Grover's
algorithm is a basic tool that can be applied to a large number of
problems in computer science, creating quantum algorithms that are
polynomially faster than fastest known and fastest possible classical
algorithms that solve the same problems. Our goal in this paper is to
make these techniques readily accessible to those without a strong
background in quantum physics: we achieve this by providing a set of
tools, each of which makes use of Grover's algorithm or similar
techniques, which can be used as subroutines in many quantum
algorithms.}{The tools we provide are carefully constructed: they are
easy to use, and in many cases they are asymptotically faster than the
best tools previously available. The tools we build on include
algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt
and Zalka and Durr and Hoyer.}{After creating our tools, we create
several new quantum algorithms, each of which is faster than the fastest
known deterministic classical algorithm that accomplishes the same aim,
and some of which are faster than the fastest possible deterministic
classical algorithm. These algorithms solve problems from the fields of
graph theory and computational geometry, and some employ dynamic
programming techniques. We discuss a breadth-first search that is faster
than $\Theta(\text{edges})$ (the classical limit) in a dense graph,
maximum-points-on-a-line in $O(N^{3/2}\lg N)$ (faster than the fastest
classical algorithm known), as well as several other algorithms that are
similarly illustrative of solutions in some class of problem. Through
these new algorithms we illustrate the use of our tools, working to
encourage their use and the study of quantum algorithms in general.

*Book review:*

**On Geometry of quantum states:
an introduction to quantum entanglement (by I. Bengtsson and K.
Zyczkowski)**
(pp0860-0860) PDF

G.
Milburn

**back to QIC online Front page**