Research Articles:
Quantum conditional
query complexity (pp0541-0566)
Imdad
S.B. Sardharwalla, Sergii Strelchuk, and Richard Jozsa
We define and study a new type
of quantum oracle, the quantum conditional oracle, which provides oracle
access to the conditional probabilities associated with an underlying
distribution. Amongst other
properties, we (a) obtain highly efficient quantum algorithms for
identity testing, equivalence testing and uniformity testing of
probability distributions; (b) study the power of these oracles for
testing properties of boolean functions, and obtain an algorithm for
checking whether an $n$-input
$m$-output
boolean function is balanced or
$\epsilon$-far from balanced; and
(c) give an algorithm, requiring $\tilde{O}(n/\epsilon)$
queries, for testing whether an $n$-dimensional
quantum state is maximally mixed or not.
Can small quantum
systems learn (pp0567-0594)
Nathan
Wiebe and Christopher Grandade
We examine the question of
whether quantum mechanics places limitations on the ability of small
quantum devices to learn. We specifically examine the question in
the context of Bayesian inference, wherein the prior and posterior
distributions are encoded in the quantum state vector. We conclude
based on lower bounds from Grover's search that an efficient blackbox
method for updating the distribution is impossible. We then
address this by providing a new adaptive form of approximate quantum
Bayesian inference that is polynomially faster than its classical anolog
and tractable if the quantum system is augmented with classical memory
or if the low--order moments of the distribution are protected through
redundant preparation. This work suggests that there may be a
connection between fault tolerance and the capacity of a quantum system
to learn from its surroundings.
Randomness in
nonlocal games between mistrustful players
(pp0595-0610)
Carl
A. Miller and Yaoyun Shi
If two quantum players at a nonlocal
game $G$
achieve a superclassical score, then
their measurement outcomes must be at least partially random from the
perspective of any third player. This is the basis for
device-independent quantum cryptography. In this paper we address
a related question: does a superclassical
score at
$G$
guarantee that one player has created randomness from the perspective of
the other player? We show that for complete-support games, the
answer is yes: even if the second player is given the first player's
input at the conclusion of the game, he cannot perfectly recover her
output. Thus some amount of \textit{local}
randomness (i.e., randomness possessed by only one player) is always
obtained when randomness is certified from
nonlocal games with quantum strategies.
This is in contrast to non-signaling game strategies, which may produce
global randomness without any local randomness. We discuss potential
implications for cryptographic protocols between mistrustful parties.
Super-additivity and
entanglement assistance in quantum reading
(pp0611-0622)
Cosmo
Lupo and Stefano Pirandola
Quantum information theory
determines the maximum rates at which information can be transmitted
through physical systems described by quantum mechanics. Here we
consider the communication protocol known as quantum reading. Quantum
reading is a protocol for retrieving the information stored in a digital
memory by using a quantum probe, e.g., shining quantum states of light
to read an optical memory. In a variety of situations using a quantum
probe enhances the performance of the reading protocol in terms of
fidelity, data density and energy efficiency. Here we review and
characterize the quantum reading capacity of a memory model, defined as
the maximum rate of reliable reading. We show that, like other
quantities in quantum information theory, the quantum reading capacity
is super-additive. Moreover, we determine conditions under which the use
of an entangled ancilla improves the performance of quantum reading.
Improved Hamiltonian
simulation via a truncated Taylor series and corrections
(pp0623-0635)
Leonardo
Novo and Dominic Berry
We describe an improved version
of the quantum algorithm for Hamiltonian simulation based on the
implementation of a truncated Taylor series of the evolution operator.
The idea is to add an extra step to the previously known algorithm which
implements an operator that corrects the weightings of the Taylor
series.This way, the desired accuracy is achieved with an
improvement in the overall complexity of the algorithm. This quantum
simulation method is applicable to a wide range of Hamiltonians of
interest, including to quantum chemistry problems.
The complexity of
antiferromagnetic interactions and 2D lattices
(pp0636-0672)
Stephen
Piddock and Ashley Montanaro
Estimation of the minimum
eigenvalue of a quantum Hamiltonian can be formalised as the Local
Hamiltonian problem. We study the natural special case of the Local
Hamiltonian problem where the same 2-local interaction, with differing
weights, is applied across each pair of qubits. First we consider
antiferromagnetic/ferromagnetic interactions, where the weights of the
terms in the Hamiltonian are restricted to all be of the same sign. We
show that for symmetric 2-local interactions with no 1-local part, the
problem is either QMA-complete or in StoqMA. In particular the
antiferromagnetic Heisenberg and antiferromagnetic XY interactions are
shown to be QMA-complete. We also prove StoqMA-completeness of the
antiferromagnetic transverse field Ising model. Second, we study the
Local Hamiltonian problem under the restriction that the interaction
terms can only be chosen to lie on a particular graph. We prove that
nearly all of the QMA-complete 2-local interactions remain QMA-complete
when restricted to a 2D square lattice. Finally we consider both
restrictions at the same time and discover that, with the exception of
the antiferromagnetic Heisenberg interaction, all of the interactions
which are QMA-complete with positive coefficients remain QMA-complete
when restricted to a 2D triangular lattice.
Factoring using
$2n+2$ qubits with Toffoli based modular multiplication (pp0673-0684)
Thomas
Haner, Martin Roetteler, and Krysta M. Svore