Vol.15 No.3&4, March
1, 2015
Research Articles:
Adiabatic optimization without
local minima (pp0181-0199)
Michael
Jarret and Stephen P. Jordan
Several previous works have investigated the circumstances under
which quantum adiabatic optimization algorithms can tunnel out of local
energy minima that trap simulated annealing or other classical local
search algorithms. Here we investigate the even more basic question of
whether adiabatic optimization algorithms always succeed in polynomial
time for trivial optimization problems in which there are no local
energy minima other than the global minimum. Surprisingly, we find a
counterexample in which the potential is a single basin on a graph, but
the eigenvalue gap is exponentially small as a function of the number of
vertices. In this counterexample, the ground state wavefunction consists
of two ``lobes'' separated by a region of exponentially small amplitude.
Conversely, we prove if the ground state wavefunction is single-peaked
then the eigenvalue gap scales at worst as one over the square of the
number of vertices.
Ground state blind quantum
computation on AKLT state
(pp0200-0234)
Tomoyuki
Morimae, Vedran Dunjko, and Elham Kashefi
The blind quantum computing protocols (BQC) enable a classical
client with limited quantum technology to delegate a computation to the
quantum server(s) in such a way that the privacy of the computation is
preserved. Here we present a new scheme for BQC that uses the concept of
the measurement based quantum computing with the novel resource state of
Affleck-Kennedy-Lieb-Tasaki (AKLT) chains leading to more robust
computation. AKLT states are physically motivated resource as they are
gapped ground states of a physically natural Hamiltonian in condensed
matter physics. Our BQC protocol can enjoy the advantages of AKLT
resource states (in a multiserver setup), such as the cooling
preparation of the resource state, the energy-gap protection of the
quantum computation. It also provides a simple and efficient preparation
of the resource state in linear optics with biphotons.
Quantum circuits and Spin(3n)
groups (pp0235-0259)
Alexander
Yu. Vlasov
All quantum gates with one and two qubits may be described by
elements of Spin groups due to isomorphisms Spin(3)\isomSU(2)
and Spin(6)\isomSU(4). However, the group of n-qubit gates
SU(2^n) for n>2 has bigger dimension than Spin(3n).
A quantum circuit with one- and two-qubit gates may be used for
construction of arbitrary unitary transformation SU(2^n).
Analogously, the `$Spin(3n)$ circuits' are introduced in this work as
products of elements associated with one- and two-qubit gates with
respect to the above-mentioned isomorphisms. The matrix tensor product
implementation of the Spin(3n) group together with relevant
models by usual quantum circuits with 2n qubits are investigated
in such a framework. A certain resemblance with well-known sets of
non-universal quantum gates (e.g., matchgates, noninteracting-fermion
quantum circuits) related with Spin(2n) may be found in presented
approach. Finally, a possibility of the classical simulation of such
circuits in polynomial time is discussed.
Limitations of single coset
states and quantum algorithms for code equivalence
(pp0260-0294)
Hang
Dinh, Cristopher Moore, and Alexander Russell
Quantum computers can break the RSA, El Gamal, and elliptic curve
public-key cryptosystems, as they can efficiently factor integers and
extract discrete logarithms. The power of such quantum attacks lies in \emph{quantum
Fourier sampling}, an algorithmic paradigm based on generating and
measuring coset states. %This motivates the investigation of the power
or limitations of quantum Fourier sampling, especially in attacking
candidates for ``post-quantum'' cryptosystems -- classical cryptosystems
that can be implemented with today's computers but will remain secure
even in the presence of quantum attacks. In this article we extend
previous negative results of quantum Fourier sampling for Graph
Isomorphism, which corresponds to hidden subgroups of order two (over
S_n, to several cases corresponding to larger hidden subgroups. For
one case, we strengthen some results of Kempe, Pyber, and Shalev on the
Hidden Subgroup Problem over the symmetric group. In another case, we
show the failure of quantum Fourier sampling on the Hidden Subgroup
Problem over the general linear group GL_2(\FF_q). The most
important case corresponds to Code Equivalence, the problem of
determining whether two given linear codes are equivalent to each other
up to a permutation of the coordinates. Our results suggest that for
many codes of interest---including generalized Reed Solomon codes,
alternant codes, and Reed-Muller codes---solving these instances of Code
Equivalence via Fourier sampling appears to be out of reach of current
families of quantum algorithms.
Rational approximations and
quantum algorithms with postselection
(pp0295-0307)
Urmila
Mahadev and Ronald de Wolf
We study the close connection between rational functions that
approximate a given Boolean function, and quantum algorithms that
compute the same function using postselection. We show that the minimal
degree of the former equals (up to a factor of 2) the minimal query
complexity of the latter. We give optimal (up to constant factors)
quantum algorithms with postselection for the Majority function,
slightly improving upon an earlier algorithm of Aaronson. Finally we
show how Newman's classic theorem about low-degree rational
approximation of the absolute-value function follows from these
algorithms.
Complementarity between
signaling and local indeterminacy
(pp0308-0315)
S.
Aravinda and R. Srikanth
The correlations that violate the CHSH inequality are known to have
complementary contributions from signaling and local indeterminacy. This
complementarity is shown to represent a strengthening of Bell's theorem,
and can be used to certify randomness in a device-independent way,
assuming neither the validity of quantum mechanics nor even
no-signaling. We obtain general nonlocal resources that can simulate the
statistics of the singlet state, encompassing existing results. We prove
a conjecture due to Hall (2010) and Kar et al. (2011) on the
complementarity for such resources.
Quantum algorithms for
nearest-neighbor methods for supervised and unsupervised learning
(pp0316-0356)
Nathan
Wiebe, Ashish Kapoor, and Krysta M. Svore
We present quantum algorithms for performing nearest-neighbor
learning and $k$--means clustering. At the core of our algorithms are
fast and coherent quantum methods for computing the Euclidean distance
both directly and via the inner product which we couple with methods for
performing amplitude estimation that do not require measurement. We
prove upper bounds on the number of queries to the input data required
to compute such distances and find the nearest vector to a given test
example. In the worst case, our quantum algorithms lead to polynomial
reductions in query complexity relative to Monte Carlo algorithms. We
also study the performance of our quantum nearest-neighbor algorithms on
several real-world binary classification tasks and find that the
classification accuracy is competitive with classical methods.
back to QIC online Front page
|