QIC Abstracts

 Vol.17 No.11&12, September 1, 2017

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.

back to QIC online Front page