QIC Abstracts

 Vol.8 No.10 November 1, 2008

Research Articles: 
The geometry of quantum computation (pp861-0899)
M.R. Dowling and M.A. Nielsen
Whether the class Quantum Merlin Arthur is equal to QMA_1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a quantum oracle relative to which QMA\neqQMA_1. As a byproduct, we find that there are facts about quantum complexity classes that are classically relativizing but not quantumly relativizing, among them such trivial containments as BQP\subseteq{ZQEXP}.

The complexity of quantum spin systems on a two-dimensional square lattice (pp0900-0924)
R. Oliveira and B.M. Terhal
The problem 2-LOCAL HAMILTONIAN has been shown to be complete for the quantum computational class QMA. In this paper we show that this important problem remains QMA-complete when the interactions of the 2-local Hamiltonian are between qubits on a two-dimensional (2-D) square lattice. Our results are partially derived with novel perturbation gadgets that employ mediator qubits which allow us to manipulate k-local interactions. As a side result, we obtain that quantum adiabatic computation using 2-local interactions restricted to a 2-D square lattice is equivalent to the circuit model of quantum computation. Our perturbation method also shows how any stabilizer space associated with a k-local stabilizer (for constant k) can be generated as an approximate ground-space of a 2-local Hamiltonian.

Three-qubit Groverian measure (pp0925-0942)
.-L. Jung, M.-R. Hwang,  D. Park, L. Tamaryan, and S. Tamaryan
The Groverian measures are analytically computed in various types of three-qubit states. The final results are also expressed in terms of local-unitary invariant quantities in each type. This fact reflects the manifest local-unitary invariance of the Groverian measure. It is also shown that the analytical expressions for various types have correct limits to other types. For some types (type 4 and type 5) we failed to compute the analytical expression of the Groverian measure in this paper. However, from the consideration of local-unitary invariants we have shown that the Groverian measure in type 4 should be independent of the phase factor $\varphi$, which appear in the three-qubit state $|\psi \rangle$. This fact with geometric interpretation on the Groverian measure may enable us to derive the analytical expressions for general arbitrary three-qubit states in near future.

A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions (pp0943-0950)
R. de Wolf
The degrees of polynomials representing or approximating Boolean functions are a prominent tool in various branches of complexity theory. Sherstov recently characterized the minimal degree $deg_{\eps}(f)$ among all polynomials (over $\mathbb{R}$) that approximate a symmetric function $f:\01^n\rightarrow\01$ up to worst-case error $\eps$: $ deg_{\eps}(f)=\widetilde{\Theta}\left(deg_{1/3}(f) + \sqrt{n\log(1/\eps)}\right).$ In this note we show how a tighter version (without the log-factors hidden in the $\widetilde{\Theta}$-notation), can be derived quite easily using the close connection between polynomials and quantum algorithms.

On impact of a priori classical knowledge of discriminated states on the optimal unambiguous discrimination (pp0951-0964)
M. Zhang, Z.-T. Zhou, H.-Y. Dai, D.-W. Hu
Due to the fundamental limitations related to the Heisenberg uncertainty principle and the non-cloning theorem, it is impossible, even in principle, to determine the quantum state of a single system without a priori knowledge of it. To discriminate nonorthogonal quantum states in some optimal way, a priori knowledge of the discriminated states has to be relied upon. In this paper, we thoroughly investigate some impact of a priori classical knowledge of two quantum states on the optimal unambiguous discrimination. It is exemplified that a priori classical knowledge of the discriminated states, incomplete or complete, can be utilized to improve the optimal success probabilities, whereas the lack of a prior classical knowledge can not be compensated even by more resources.

Entanglement of formation from optimal decomposition (pp0965-0976)
L. Chen and Y.-X. Chen
We present a new method of constructing sets of states with known entanglement of formation. The method realizes the optimal decomposition families of states. We also derive the additivity of the entanglement of formation and thus calculate the entanglement cost. These results are used to find out the undistillable entanglement of some states. We illustrate our method by investigating the two-qubit state, the separable state, the maximally correlated state, the isotropic state and the Werner state. We also discuss the realization of Werner state in experiment.

Universal quantum computation with quantum-dot cellular automata in decoherence-free subspace (pp0977-0985)
Z.-Y. Xu, M. Feng, and W.-M. Zhang
We investigate the possibility to have electron-pairs in decoherence-free subspace (DFS), by means of the quantum-dot cellular automata (QCA) and single-spin rotations, to deterministically carry out a universal quantum computation with high-fidelity. We show that our QCA device with electrons tunneling in two dimensions is very suitable for DFS encoding, and argue that our design favors a scalable quantum computation robust to collective dephasing errors.

On the iterative decoding of sparse quantum codes (pp0986-1000)
D. Poulin and Y. Chung
We address the problem of decoding sparse quantum error correction codes. For Pauli channels, this task can be accomplished by a version of the belief propagation algorithm used for decoding sparse classical codes. Quantum codes pose two new challenges however. Firstly, their Tanner graph unavoidably contain small loops which typically undermines the performance of belief propagation. Secondly, sparse quantum codes are by definition highly degenerate. The standard belief propagation algorithm does not exploit this feature, but rather it is impaired by it. We propose heuristic methods to improve belief propagation decoding, specifically targeted at these two problems. While our results exhibit a clear improvement due to the proposed heuristic methods, they also indicate that the main source of errors in the quantum coding scheme remains in the decoding.

back to QIC online Front page