QIC Abstracts

 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