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)
E.-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.
