|
Vol.19 No.3&4, March
1, 2019
Research Articles:
Quantum fast-forwarding:
Markov chains and graph property testing
(pp0181-0213)
Simon
Apers and Alain Sarlette
We introduce a new tool for quantum
algorithms called quantum fast-forwarding (QFF).
The tool uses quantum walks as a means to
quadratically
fast-forward a reversible Markov chain. More specifically, with
$P$ the
Markov chain transition matrix and
$D = \sqrt{P\circ P^T}$ its
discriminant matrix ($D=P$
if $P$
is symmetric), we construct a quantum walk algorithm that for any
quantum state $\ket{v}$
and integer $t$
returns a quantum state $\epsilon$-close
to the state $D^t\ket{v}/\|D^t\ket{v}\|$.
The algorithm uses $O\Big(\|D^t\ket{v}\|^{-1}\sqrt{t\log(\epsilon\|D^t\ket{v}\|)^{-1}}\Big)$
expected quantum walk steps and
$O(\|D^t\ket{v}\|^{-1})$ expected
reflections around $\ket{v}$.
This shows that quantum walks can accelerate the transient dynamics of
Markov chains, complementing the line of results that proves the
acceleration of their limit behavior. We show that this tool leads to
speedups on random walk algorithms in a very natural way. Specifically
we consider random walk algorithms for testing the graph expansion and
clusterability, and show that we can
quadratically improve the dependency
of the classical property testers on the random walk
runtime.
Moreover, our quantum algorithm exponentially improves the space
complexity of the classical tester to logarithmic. As a subroutine of
independent interest, we use
QFF
for determining whether a given pair of nodes lies in the same cluster
or in separate clusters. This solves a robust version of
$s$-$t$
connectivity, relevant in a learning context for classifying objects
among a set of examples. The different algorithms crucially rely on the
quantum speedup of the transient behavior of random walks.
Impossibility of
perfectly-secure one-round
delegated quantum computing for
classical client
(pp0214-0221)
Tomoyuki
Morimae and Takeshi Koshiba
Blind quantum computing protocols
enable a client, who can generate or measure single-qubit
states, to delegate quantum computing to a remote quantum server
protecting the client's privacy (i.e., input, output, and program). With
current technologies, generations or measurements of single-qubit
states are not too much burden for the client. In other words, secure
delegated quantum computing is possible for ``almost classical" clients.
However, is it possible for a ``completely classical" client? Here we
consider a one-round perfectly-secure delegated quantum computing, and
show that the protocol cannot satisfy both the correctness (i.e., the
correct result is obtained when the server is honest) and the perfect
blindness (i.e., the client's privacy is completely protected)
simultaneously unless
BQP
is in NP. Since
BQP
is not believed to be in NP, the result suggests the impossibility of
the one-round perfectly-secure delegated quantum computing.
Quantum complexity
associated with tunneling
(pp0222-0236)
Ofir
Flom, Asher Yahalom, Haggai Zilberberg, L.P. Horwitz, and Jacob Levitan
We use a one dimensional model of a
square barrier embedded in an infinite potential well to demonstrate
that tunneling leads to a complex behavior of the wave function and that
the degree of complexity may be quantified by use of a locally defined
spatial entropy function defined by
$S=-\int |\Psi(x,t)|^2 \ln |\Psi(x,t)|^2 dx $.
We show that changing the square barrier by increasing the height or
width of the barrier not only decreases the tunneling but also slows
down the rapid rise of the entropy function, indicating that the locally
defined entropy growth is an essentially quantum effect.
Windowed Fourier transform
and general wavelet algorithms in quantum computation
(pp0237-0251)
Guangsheng
Ma, Hongbo Li, and Jiman Zhao
In this paper, we define the quantum
windowed Fourier transform and study some of its properties, then we
develop two useful operations called quantum convolution and `integral'.
Quantum `integral' allows us to implement the integral transforms
quantum-mechanically with a certain probability, including general
wavelet kernel transforms. Furthermore, we propose an improved wavelet
kernel transform for quantum computation.
Factoring on a quantum
annealing computer
(pp0252-0261)
Richard
H. Warren
This paper is about quantum factoring
all integers in an interval. Our goal is to be able to factor all
positive integers $N < 1,000$.
We reached this goal on a D-Wave 2000
qubit
processor by minimizing $(N - (p
\times q))^2$ by using one routine
that calls the interface software
dw.
We sized $p < 32$
and $q < 256$
as Boolean variables. We factored seven
semiprimes
that could not be factored by the method in a 2016 D-Wave report.
We did not use information about the factors for a specific N. The
inputs to our routine are $N$
and values for two parameters.
back to QIC online Front page
|
