Research Articles:
Efficient simulation
of sparse Markovian quantum dynamics
(pp0901-0947)
Andrew
M. Childs and Tongyang Li
Quantum algorithms for simulating
Hamiltonian dynamics have been extensively developed, but there has been
much less work on quantum algorithms for simulating the dynamics of open
quantum systems. We give the first efficient quantum algorithms for
simulating Markovian quantum dynamics generated by Lindbladians that are
not necessarily local. We introduce two approaches to simulating sparse
Lindbladians. First, we show how to simulate Lindbladians that act
within small invariant subspaces using a quantum algorithm to implement
sparse Stinespring isometries. Second, we develop a method for
simulating sparse Lindblad operators by concatenating a sequence of
short-time evolutions. We also show limitations on Lindbladian
simulation by proving a no--fast-forwarding theorem for simulating
sparse Lindbladians in black-box models.
Qudit homological product
codes
(pp0948-0958)
Mate
Farkas and Peter Vrana
In this note we show that the random
homological product code
construction of
Bravyi
and Hastings can be extended to
qudits
of dimension $D$
with $D$
an odd prime. While the result is not surprising, the proof does require
new ideas.
Merlinization of
complexity classes above BQP
(pp0959-0972)
Tomoyuki
Morimae and Harumichi Nishimura
We study how complexity classes above
BQP,
such as
postBQP,
${\rm postBQP}_{\rm FP}$,
and
SBQP, change if we ``Merlinize"
them, i.e., if we allow an extra input quantum state (or classical bit
string) given by Merlin as witness. Our main results are the following:
First, the
Merlinized
version of
postBQP
is equal to
PSPACE.
Second, if the
Merlinized
postBQP
is restricted in such a way that the
postselection
probability is equal for all witness states, then the class is equal to
PP. Finally, the
Merlinization
does not change the class
SBQP.
Superdiffusive
quantum stochastic walk definable on arbitrary directed graph
(pp0973-0986)
Krzysztof Domino,
Adam Glos and Mateusz Ostaszewski
In this paper we define a quantum
stochastic walk on arbitrary directed graph with super-diffusive
propagation on a line graph. Our model is based on global environment
interaction
QSW,
which is known to have ballistic propagation. However we discovered,
that in this case additional amplitude transitions occur, hence graph
topology is changed into moral graph. Because of that we call the
effect a spontaneous moralization. We propose a general correction
scheme, which is proved to remove unnecessary transition and thus to
preserve the graph topology. In the end we numerically show, that
super-diffusive propagation is preserved. Because of that our new model
may be applied as effective evolution on arbitrary directed graph.
Efficient quantum
algorithms for analyzing large sparse electrical networks
(pp0987-1026)
Guoming
Wang
Analyzing large sparse electrical
networks is a fundamental task in physics, electrical engineering and
computer science. We propose two classes of quantum algorithms for this
task. The first class is based on solving linear systems, and the second
class is based on using quantum walks. These algorithms compute various
electrical quantities, including voltages, currents, dissipated powers
and effective resistances, in time
$\operatorname{poly}(d, c, \operatorname{log}(N), 1/\lambda,
1/\epsilon)$, where
$N$
is the number of
vertices
in the network, $d$
is the maximum
unweighted
degree of the
vertices,
$c$
is the ratio of largest to smallest edge resistance,
$\lambda$
is the spectral gap of the normalized
Laplacian
of the network, and $\epsilon$
is the accuracy. Furthermore, we show that the polynomial dependence on
$1/\lambda$
is necessary. This implies that our algorithms are optimal up to
polynomial factors and cannot be significantly improved.
Magic coins are useful for
small-space quantum machines
(pp1027-1043)
A.C.
Cem Say and Abuzer Yakaryilmaz
Although polynomial-time probabilistic
Turing machines can utilize
uncomputable
transition probabilities to recognize
uncountably
many languages with bounded error when allowed to use double logarithmic
space, it is known that such ``magic coins'' give no additional
computational power to constant-space versions of those machines. We
show that adding a few quantum bits to the model changes the picture
dramatically. For every language
$L$, there exists such a two-way
quantum finite automaton (2qcfa)
that recognizes a language of the same Turing degree as
$L$
with bounded error in polynomial time. When used as
verifiers
in public-coin interactive proof systems, such
automata
can verify membership in all languages with bounded error, outperforming
their classical counterparts, which are known to fail for the
palindromes language. Corollaries demonstrate even faster machines when
one is allowed to use a counter as memory, and an alternative proof of
the
uncountability of stochastic
languages.