Research Articles:
Designing an ion trap
for quantum simulation
(pp0361-0375)
I.M.
Buluta and S. Hasegawa
Planar Coulomb crystals have been recently proposed for the
implementation of quantum simulation and computation. In order to put
this idea into practice we designed a specialized RF ion trap system.
The design is based on extensive numerical simulations of planar Coulomb
crystals in RF traps and the estimation of the error in quantum
simulation and computation. Our trap would have reduced heating rates
and large axial confinement frequencies would be available. Moreover, it
provides very good optical access and it is easy to construct and
operate.
Quantum direct communication with mutual authentication
(pp0376-0394)
C.-A.
Yen, S.-J. Horng, H.-S. Goan, T.-W. Kao, and Y.-H. Chou
In this paper, we first point out that some recently proposed quantum
direct communication (QDC) protocols with authentication are vulnerable
under some specific attacks, and the secrete message will leak out to
the authenticator who is introduced to authenticate users participating
in the communication. We then propose a new protocol that is capable of
achieving secure QDC with authentication as long as the authenticator
would do the authentication job faithfully. Our quantum protocol
introduces a mutual authentication procedure, uses the quantum Bell
states, and applies unitary transformations in the authentication
process. Then it exploits and utilizes the entanglement swapping and
local unitary operations in the communication processes. Thus, after the
authentication process, the client users are left alone to communicate
with each other, and the authenticator has no access to the secrete
message. In addition, our protocol does not require a direct quantum
link between any two users, who want to communicate with each other.
This may also be an appealing advantage in the implementation of a
practical quantum communication network.
The
regime of good control
(pp0395-0405)
J. Li and K. Jacobs
We derive the equations of motion describing the feedback control of
quantum systems in the regime of ``good control", in which the control
is sufficient to keep the system close to the desired state. One can
view this regime as the quantum equivalent of the ``linearized" regime
for feedback control of classical nonlinear systems. Strikingly, while
the dynamics of a single qubit in this regime is indeed linear, that of
all larger systems remains nonlinear, in contrast to the classical case.
As a first application of these equations, we determine the steady-state
performance of feedback protocols for a single qubit that use unbiased
measurements.
Mixing doubly stochastic quantum channels with the completely
depolarizing channel
(pp0406-0413)
J. Watrous
It is proved that every doubly stochastic quantum channel that is
properly averaged with the completely depolarizing channel can be
written as a convex combination of unitary channels. It follows that
within the space of doubly stochastic quantum channels, there is a ball
with positive radius around the completely depolarizing channel within
which all channels are convex combinations of unitary channels.
Quantum wavelet transforms of any order
(pp0414-0422)
F. Arguello
Many classical algorithms are known to efficiently compute the wavelet
transforms. However, those classical algorithms cannot be directly
translated to quantum algorithms. Recently, efficient and complete
quantum algorithms for two representative wavelet transforms (quantum
Haar and quantum Daubechies of fourth order) have been proposed. In this
paper, we generalize these algorithms in order to they can be applied to
Daubechies wavelet kernels of any order. Specifically, we develop a
method that efficiently factorize those kernels. The factorization is
compatible with the existing pyramidal and packet quantum wavelet
algorithms. All steps of the algorithm are unitary and easily
implementable on a quantum computer.
Synthesis of quantum circuits for $d$-level systems by
using cosine-sine
(pp0423-0443)
Y. Nakajima, Y.
Kawano, H. Sekigawa, M. Nakanishi, S. Yamashita, and Y. Nakashima
We study the problem of designing minimal quantum circuits for any
operations on $n$ qudits by means of the cosine-sine decomposition. Our
method is based on a divide-and-conquer strategy. In that strategy, the
size of the produced quantum circuit depends on whether the partitioning
is balanced. We provide a new cosine-sine decomposition based on a
balanced partitioning for $d$-level systems. The produced circuit is not
asymptotically optimal except when $d$ is a power of two, but, when the
number of qudits $n$ is small, our method can produce the smallest
quantum circuit compared to the circuits produced by other synthesis
methods. For example, when $d=3$ (three-level systems) and $n=2$ (two
qudits), then the number of two-qudit operations called CINC, which is a
generalized versions of CNOT, is 36 whereas the previous method needs
156 CINC gates. Moreover, we show that our method is useful for
designing a polynomial-size quantum circuit for the radix-$d$ quantum
Fourier transform.
Quantum communication complexity of block-composed functions
(pp0444-0460)
Y.-Y.
Shi and Y.-F. Zhu
A major open problem in communication complexity is whether or not
quantum protocols can be exponentially more efficient than classical
ones for computing a {\em total} Boolean function in the two-party
interactive model. Razborov's result ({\em Izvestiya: Mathematics},
67(1):145--159, 2002) implies the conjectured negative answer for
functions $F$ of the following form: $F(x, y)=f_n(x_1\cdot y_1, x_2\cdot
y_2, ..., x_n\cdot y_n)$, where $f_n$ is a {\em symmetric} Boolean
function on $n$ Boolean inputs, and $x_i$, $y_i$ are the $i$'th bit of
$x$ and $y$, respectively. His proof critically depends on the symmetry
of $f_n$. We develop a lower-bound method that does not require symmetry
and prove the conjecture for a broader class of functions. Each of those
functions $F$ is the ``block-composition'' of a ``building block'' $g_k
: \{0, 1\}^k \times \{0, 1\}^k \rightarrow \{0, 1\}$, and an $f_n : \{0,
1\}^n \rightarrow \{0, 1\}$, such that $F(x, y) = f_n( g_k(x_1, y_1),
g_k(x_2, y_2), ..., g_k(x_n, y_n) )$, where $x_i$ and $y_i$ are the $i$'th
$k$-bit block of $x, y\in\{0, 1\}^{nk}$, respectively. We show that as
long as g_k itself is "hard'' enough, its block-composition with an
arbitrary f_n has polynomially related quantum and classical
communication complexities. For example, when g_k is the Inner Product
function with k=\Omega(\log n), the deterministic
communication complexity of its block-composition with any f_n is
asymptotically at most the quantum complexity to the power of 7.
On
the CNOT -cost of TOFFOLI gates
(pp0461-0486)
V.V.
Shende and I.L. Markov
The three-input \TOFFOLI\ gate is the workhorse of circuit synthesis for
classical logic operations on quantum data,
e.g., reversible arithmetic circuits. In physical implementations,
however, \TOFFOLI\ gates are decomposed into six \CNOT\ gates and
several one-qubit gates. Though this decomposition has been known for at
least 10 years, we provide here the first demonstration of its \CNOT-optimality.
We study three-qubit circuits which contain less than six \CNOT\ gates
and implement a block-diagonal operator, then show that they implicitly
describe the cosine-sine decomposition of a related operator. Leveraging
the canonical nature of such decompositions to limit one-qubit gates
appearing in respective circuits, we prove that the $n$-qubit analogue
of the \TOFFOLI\ requires at least $2n$ \CNOT\ gates. Additionally, our
results offer a complete classification of three-qubit diagonal
operators by their \CNOT -cost, which holds even if ancilla qubits are
available.
Locality bounds on Hamiltonians for stabilizer codes
(pp0487-0499)
S.S.
Bullock and D.P. O'Leary
In this paper, we study the complexity of Hamiltonians whose groundstate
is a stabilizer code. We introduce various notions of $k$-locality of a
stabilizer code, inherited from the associated stabilizer group. A
choice of generators leads to a Hamiltonian with the code in its
groundspace. We establish bounds on the locality of any other
Hamiltonian whose groundspace contains such a code, whether or not its
Pauli tensor summands commute. Our results provide insight into the cost
of creating an energy gap for passive error correction and for adiabatic
quantum computing. The results simplify in the cases of XZ-split codes
such as Calderbank-Shor-Steane stabilizer codes and
topologically-ordered stabilizer codes arising from surface cellulations.
Quantum algorithms for shifted subset problems
(pp0500-0512)
A.
Montanaro
We consider a recently proposed generalisation of the abelian hidden
subgroup problem: the {\em shifted subset problem}. The problem is to
determine a subset $S$ of some abelian group, given access to quantum
states of the form $\ket{S+x}$, for some unknown shift $x$. We give
quantum algorithms to find Hamming spheres and other subsets of the
boolean cube $\{0,1\}^n$. The algorithms have time complexity polynomial
in $n$ and give rise to exponential separations from classical
computation.
On
parallel composition of zero-knowledge proofs with
black-box quantum
(pp0513-05532)
R.
Jain, A. Kolla, G. Midrijanis, and B.W. Reichardt
Let $L$ be a language decided by a constant-round quantum Arthur-Merlin
($\QAM$) protocol with negligible soundness error and all but possibly
the last message being classical. We prove that if this protocol is zero
knowledge with a black-box, quantum simulator $\cS$, then $L \in \BQP$.
Our result also applies to any language having a three-round quantum
interactive proof ($\QIP$), with all but possibly the last message being
classical, with negligible soundness error and a black-box quantum
simulator. These results in particular make it unlikely that certain
protocols can be composed in parallel in order to reduce soundness
error, while maintaining zero knowledge with a black-box quantum
simulator. They generalize analogous classical results of Goldreich and
Krawczyk (1990). Our proof goes via a reduction to quantum black-box
search. We show that the existence of a black-box quantum simulator for
such protocols when $L \notin \BQP$ would imply an impossibly-good
quantum search algorithm.
Exact quantum lower bound for Grover's problem
(pp0533-0540)
C. Dohotaru and P. Hoyer
One of the most important quantum algorithms ever discovered is Grover's
algorithm for searching an unordered set. We give a new lower bound in
the query model which proves that Grover's algorithm is exactly optimal.
Similar to existing methods for proving lower bounds, we bound the
amount of information we can gain from a single oracle query, but we
bound this information in terms of angles. This allows our proof to be
simple, self-contained, based on only elementary mathematics, capturing
our intuition, while obtaining at the same time an exact bound.
