Vol.17
No.1&12,
February 1, 2017
Research Articles:
Scaling and efficient
classical simulation of the quantum Fourier transform
(pp0001-0014)
Kieran
J. Woolfe, Charles D. Hill, and Lloyd C. L. Hollenberg
We provide numerical evidence
that the quantum Fourier transform can be efficiently represented in a
matrix product operator with a size growing relatively slowly with the
number of
qubits.
Additionally, we numerically show that the tensors in the operator
converge to a common tensor as the number of
qubits
in the transform increases. Together these results imply that the
application of the quantum Fourier transform to a matrix product state
with $n$
qubits
of maximum Schmidt rank $\chi$
can be simulated in $O(n \left(\log
(n)\right)^2 \chi^2)$ time. We
perform such simulations and quantify the error involved in representing
the transform as a matrix product operator and simulating the quantum
Fourier transform of periodic states.
A fast exact quantum
algorithm for solitude verification
(pp0015-0040)
Seiichiro
Tani
Solitude verification is
arguably one of the simplest fundamental problems in distributed
computing, where the goal is to verify that there is a unique contender
in a network. This paper devises a quantum algorithm that exactly solves
the problem on an anonymous network, which is known as a network model
with minimal assumptions [Angluin,
STOC'80].
The algorithm runs in $O(N)$
rounds if every party initially has the common knowledge of an upper
bound $N$
on the number of parties. This implies that all solvable problems can be
solved in $O(N)$
rounds on average without error (i.e., with zero-sided error) on the
network. As a generalization, a quantum algorithm that works in
$O(N \log_2 (\max\set{k,2}))$
rounds is obtained for the problem of exactly computing any symmetric
Boolean function, over $n$
distributed input bits, which is constant over all the
$n$
bits whose sum is larger than $k$
for
$k\in \set{0,1,\dots, N-1}$.
All these algorithms work with the bit complexities bounded by a
polynomial in $N$.
Quantum algorithms for
Gibbs sampling and hitting-time estimation
(pp0041-0064)
Anirban
Narayan Chowdhury and Rolando D. Somma
We present quantum algorithms
for solving two problems regarding stochastic processes. The first
algorithm prepares the thermal Gibbs state of a quantum system and runs
in time almost linear in $\sqrt{N
\beta/{\cal Z}}$ and polynomial in
$\log(1/\epsilon)$,
where $N$
is the Hilbert space dimension,
$\beta$ is the inverse temperature,
${\cal Z}$
is the partition function, and
$\epsilon$ is the desired precision
of the output state. Our quantum algorithm exponentially improves the
complexity dependence on
$1/\epsilon$ and
polynomially
improves the dependence on $\beta$
of known quantum algorithms for this problem. The second algorithm
estimates the hitting time of a Markov chain. For a sparse stochastic
matrix $P$,
it runs in time almost linear in
$1/(\epsilon \Delta^{3/2})$, where
$\epsilon$
is the absolute precision in the estimation and
$\Delta$
is a parameter determined by $P$,
and whose inverse is an upper bound of the hitting time. Our quantum
algorithm
quadratically
improves the complexity dependence on
$1/\epsilon$
and $1/\Delta$
of the analog classical algorithm for
hitting-time estimation. Both algorithms use tools recently
developed in the context of Hamiltonian simulation, spectral gap
amplification, and solving linear systems of equations.
Using Simon's algorithm to
attack symmetric-key cryptographic primitives
(pp0065-0078)
Thomas
Santoli and Christian Schaffner
We present new connections
between quantum information and the field of classical cryptography. In
particular, we provide examples where
Simon's
algorithm can be used to show insecurity of commonly used
cryptographic
symmetric-key primitives. Specifically, these examples consist of a
quantum distinguisher
for the 3-round
Feistel
network and a forgery attack on CBC-MAC which forges a tag
for a chosen-prefix message querying only other messages (of
the same length). We assume that an adversary has
quantum-oracle access to the respective classical primitives. Similar
results have been achieved recently in independent work by
Kaplan
\emph{et
al.}~\cite{C:KLLN16}.
Our findings shed new light on the post-quantum security of
cryptographic
schemes and underline that classical security proofs of
cryptographic
constructions need to be revisited in light of quantum attackers.
Open quantum random walks
and the mean hitting time formula
(pp0079-0105)
Carlos
F. Lardizabal
We make use of the Open Quantum
Random Walk setting due to S.
Attal,
F.
Petruccione, C. Sabot and I.
Sinayskiy
in order to discuss hitting times and a quantum version of the Mean
Hitting Time Formula from classical probability theory. We study
an open quantum notion of hitting probability on a finite collection of
sites and with this we are able to describe the problem in terms of
linear maps and its matrix representations. After setting an open
quantum version of the fundamental matrix for
ergodic
Markov chains we are able to prove our main result and as consequence a
version of the Random Target Lemma. We also study a mean hitting time
formula in terms of the minimal polynomial associated to the matrix
representation of the quantum walk. We discuss applications of the
results to open quantum dynamics on graphs together with open questions.
Orthogonal rank and
impossibility of quantum round elimination
(pp0106-0116)
Jop
Briet and Jeroen Zuiddam
After Bob sends Alice a bit, she
responds with a lengthy reply. At the cost of a factor of two in the
total communication, Alice could just as well have given Bob her two
possible replies at once without listening to him at all, and have him
select which one applies. Motivated by a conjecture stating that this
form of ``round elimination'' is impossible in exact quantum
communication complexity, we study the orthogonal rank and a symmetric
variant thereof for a certain family of
Cayley
graphs. The orthogonal rank of a graph is the smallest number
$d$ for
which one can label each vertex with a nonzero
$d$-dimensional
complex vector such that adjacent
vertices receive orthogonal vectors.
We show an $\exp(n)$
lower bound on the orthogonal rank of the graph on~$\{0,1\}^n$
in which two strings are adjacent if they have Hamming distance at
least~$n/2$.
In combination with previous work, this implies an affirmative answer to
the above conjecture.
Electrical control of strong spin-phonon coupling in a carbon nanotube
(pp0117-0124)
Fang-Yu
Hong, Jing-Li Fu, Yan Wu, and Zhi-Yan Zhu
We describe an approach to
electrically control the strong interaction between a single electron
spin and the
vibrational
motion of a suspended carbon
nanotube
resonator. The strength of the deflection-induced spin-phonon
coupling is dependent on the
wavefunction
of the electron confined in a lateral carbon
nanotube
quantum dot. An electrical field along the
nanotube
shifts the effective center of the quantum dot, leading to the
corresponding modification of the spin-phonon
strength. Numerical simulations with experimentally reachable
parameters show that high fidelity quantum state transfer between
mechanical and spin
qubits
driven by electrical pulses is feasible. Our results form the basis for
the fully electrical control of the coherent
interconvertion
between light and spin
qubits
and for manufacturing electrically driven quantum information processing
systems.
Quantum invariants of
3-manifolds and NP vs #P
(pp0125-0146)
Gorjan
Alagic and Catharine Lo
The computational complexity
class $\#\P$
captures the difficulty of counting the satisfying assignments to a
boolean formula. In this work, we use basic tools from quantum
computation to give a proof that the
$SO(3)$
Witten-Reshetikhin-Turaev (WRT)
invariant of 3-manifolds is $\#\P$-hard
to calculate. We then apply this result to a question about the
combinatorics of Heegaard
splittings, motivated by analogous work on link diagrams by M. Freedman.
We show that, if $\#\P \not\subseteq
\FP^\NP$, then there exist
infinitely many Heegaard splittings
which cannot be made logarithmically thin by local WRT-preserving moves,
except perhaps via a superpolynomial number of steps. We also outline
two extensions of the above results. First, adapting a result of
Kuperberg, we show that any presentation-independent approximation of
WRT is also
$\#\P$-hard.
Second, we sketch out how all of our results can be translated to the
setting of triangulations and
Turaev-Viro invariants.
back to QIC online Front page
|