QIC Abstracts

 Vol.8 No.8/9 September 1, 2008

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