1. k-Boson Quantum Walks Do Not Distinguish Arbitrary Graphs
Jamie Smith
http://arxiv.org/abs/1004.0206
In this paper, we define k-equivalence, a relation on graphs that relies on their associated cellular algebras. We show that a k-Boson quantum walk cannot distinguish pairs of graphs that are k- equivalent. The existence of pairs of k-equivalent graphs has been shown by Ponomarenko et al. [2, 6]. This gives a negative answer to a question posed by Gamble et al. [7].
2. A Full Characterization of Quantum Advice
Scott Aaronson, Andrew Drucker
http://arxiv.org/abs/1004.0377
We prove the following surprising result: given any quantum state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate rho on all quantum circuits of fixed polynomial size. In terms of complexity classes, this implies that BQP/qpoly is contained in QMA/poly, which supersedes the previous result of Aaronson that BQP/qpoly is contained in PP/poly. Indeed, we can exactly characterize quantum advice, as equivalent in power to untrusted quantum advice combined with trusted classical advice. Proving our main result requires combining a large number of previous tools -- including a result of Alon et al. on learning of real-valued concept classes, a result of Aaronson on the learnability of quantum states, and a result of Aharonov and Regev on "QMA+ super-verifiers" -- and also creating some new ones. The main new tool is a so-called majority-certificates lemma, which is closely related to boosting in machine learning, and which seems likely to find independent applications. In its simplest version, this lemma says the following. Given any set S of Boolean functions on n variables, any function f in S can be expressed as the pointwise majority of m=O(n) functions f1,...,fm in S, such that each fi is the unique function in S compatible with O(log|S|) input/output constraints.
3. Limit theorem for a time-dependent coined quantum walk on the line
Takuya Machida, Norio Konno
F. Peper et al. (Eds.): IWNC 2009, Proceedings in Information and Communications Technology, Vol.2, pp.226-235, 2010
http://arxiv.org/abs/1004.0425
We study time-dependent discrete-time quantum walks on the one-dimensional lattice. We compute the limit distribution of a two-period quantum walk defined by two orthogonal matrices. For the symmetric case, the distribution is determined by one of two matrices. Moreover, limit theorems for two special cases are presented.
4. Limit theorems for quantum walks with memory
Norio Konno, Takuya Machida
http://arxiv.org/abs/1004.0443
Recently Mc Gettrick [1] introduced and studied a discrete-time 2-state quantum walk (QW) with a memory in one dimension. He gave an expression for the amplitude of the QW by path counting method. Moreover he showed that the return probability of the walk is more than 1/2 for any even time. In this paper, we compute the stationary distribution by considering the walk as a 4-state QW without memory. Our result is consistent with his claim. In addition, we obtain the weak limit theorem of the rescaled QW. This behavior is striking different from the corresponding classical random walk and the usual 2-state QW without memory as his numerical simulations suggested.
5. Graph Approach to Quantum Systems
Mladen Pavicic, Brendan D. McKay, Norman D. Megill, Kresimir Fresl
Journal of Mathematical Physics, 51, 102103-1-31 (2010)
http://arxiv.org/abs/1004.0776
Using a graph approach to quantum systems, we prove that descriptions of 3-dim Kochen-Specker (KS) setups as well as descriptions of 3-dim spin systems by means of Greechie lattices that we find in the literature are wrong. Correct lattices generated by McKay-Megill-Pavicic (MMP) hypergraphs and Hilbert subspace equations are given. To enable exhaustive generations of 3-dim KS setups by means of recently found "stripping technique," bipartite graph generation is used to provide us with lattices with equal numbers of elements and blocks (orthogonal triples of elements) - up to 41 of them. We obtain several new results on such lattices and hypergraphs, in particular on properties such as superposition and orthoraguesian equations. Since a bipartite graph approach has recently been applied to CSS (Calderbank-Shor-Steane) and graph states on the one hand, and span programs, quantum walks, and quantum search on the other, our results also enable the study of these quantum information fields by means of hypergraphs and lattices.
6. Tailoring discrete quantum walk dynamics via extended initial conditions: Towards homogeneous probability distributions
Germ��n J. de Valc��rcel, Eugenio Rold��n, Alejandro Romanelli
New J. Phys 12, 123022 (2010)
http://arxiv.org/abs/1004.0976
We study the evolution of initially extended distributions in the coined quantum walk on the line by analyzing the dispersion relation of the process and its associated wave equations. This allows us, in particular, to devise an initially extended condition leading to a uniform probability distribution whose width increases linearly with time, with increasing homogeneity.
7. Distribution of chirality in the quantum walk: Markov process and entanglement
Alejandro Romanelli
http://arxiv.org/abs/1004.1134
The asymptotic behavior of the quantum walk on the line is investigated focusing on the probability distribution of chirality independently of position. The long-time limit of this distribution is shown to exist and to depend on the initial conditions, and it also determines the asymptotic value of the entanglement between the coin and the position. It is shown that for given asymptotic values of both the entanglement and the chirality distribution it is possible to find the corresponding initial conditions within a particular class of spatially extended Gaussian distributions. Moreover it is shown that the entanglement also measures the degree of Markovian randomness of the distribution of chirality.
8. Characterization of universal two-qubit Hamiltonians
Andrew M. Childs, Debbie Leung, Laura Man?inska, Maris Ozols
Quantum Information and Computation 11, 19-39 (2011)
http://arxiv.org/abs/1004.1645
Suppose we can apply a given 2-qubit Hamiltonian H to any (ordered) pair of qubits. We say H is n-universal if it can be used to approximate any unitary operation on n qubits. While it is well known that almost any 2-qubit Hamiltonian is 2-universal (Deutsch, Barenco, Ekert 1995; Lloyd 1995), an explicit characterization of the set of non-universal 2-qubit Hamiltonians has been elusive. Our main result is a complete characterization of 2-non-universal 2-qubit Hamiltonians. In particular, there are three ways that a 2-qubit Hamiltonian H can fail to be universal: (1) H shares an eigenvector with the gate that swaps two qubits, (2) H acts on the two qubits independently (in any of a certain family of bases), or (3) H has zero trace. A 2-non-universal 2-qubit Hamiltonian can still be n-universal for some n >= 3. We give some partial results on 3-universality. Finally, we also show how our characterization of 2-universal Hamiltonians implies the well-known result that almost any 2-qubit unitary is universal.
9. On the adiabatic condition and the quantum hitting time of Markov chains
Hari Krovi, Maris Ozols, J��r��mie Roland
Physical Review A, 82(2):022333, 2010
http://arxiv.org/abs/1004.2721
We present an adiabatic quantum algorithm for the abstract problem of searching marked vertices in a graph, or spatial search. Given a random walk (or Markov chain) $P$ on a graph with a set of unknown marked vertices, one can define a related absorbing walk $P'$ where outgoing transitions from marked vertices are replaced by self-loops. We build a Hamiltonian $H(s)$ from the interpolated Markov chain $P(s)=(1-s)P+sP'$ and use it in an adiabatic quantum algorithm to drive an initial superposition over all vertices to a superposition over marked vertices. The adiabatic condition implies that for any reversible Markov chain and any set of marked vertices, the running time of the adiabatic algorithm is given by the square root of the classical hitting time. This algorithm therefore demonstrates a novel connection between the adiabatic condition and the classical notion of hitting time of a random walk. It also significantly extends the scope of previous quantum algorithms for this problem, which could only obtain a full quadratic speed-up for state-transitive reversible Markov chains with a unique marked vertex.
10. Quantum Snake Walk on Graphs
Ansis Rosmanis
http://arxiv.org/abs/1004.4054
I introduce a new type of continuous-time quantum walk on graphs called the quantum snake walk, the basis states of which are fixed-length paths (snakes) in the underlying graph. First I analyze the quantum snake walk on the line, and I show that, even though most states stay localized throughout the evolution, there are specific states which most likely move on the line as wave packets with momentum inversely proportional to the length of the snake. Next I discuss how an algorithm based on the quantum snake walk might potentially be able to solve an extended version of the glued trees problem which asks to find a path connecting both roots of the glued trees graph. No efficient quantum algorithm solving this problem is known yet.
11. Tunneling effects in a one-dimensional quantum walk
Mostafa Annabestani, Seyed Javad Akhtarshenas, Mohamad Reza Abolhassani
http://arxiv.org/abs/1004.4352
In this article we investigate the effects of shifting position decoherence, arisen from the tunneling effect in the experimental realization of the quantum walk, on the one-dimensional discreet time quantum walk. We show that in the regime of this type of noise the quantum behavior of the walker does not fade, in contrary to the coin decoherence for which the walker undergos the quantum-to-classical transition even for weak noise. Particularly, we show that the quadratic dependency of the variance on the time and also the coin-position entanglement, i.e. two important quantum aspects of the coherent quantum walk, are preserved in the presence of tunneling decoherence. Furthermore, we present an explicit expression for the probability distribution of decoherent one-dimensional quantum walk in terms of the corresponding coherent probabilities, and show that this type of decoherence smooths the probability distribution.
12. P��lya number of continuous-time quantum walks
Z. Dar��zs, T. Kiss
Phys. Rev. A 81, 062319 (2010)
http://arxiv.org/abs/1004.5286
We propose a definition for the P\'olya number of continuous-time quantum walks to characterize their recurrence properties. The definition involves a series of measurements on the system, each carried out on a different member from an ensemble in order to minimize the disturbance caused by it. We examine various graphs, including the ring, the line, higher dimensional integer lattices and a number of other graphs and calculate their P\'olya number. For the timing of the measurements a Poisson process as well as regular timing are discussed. We find that the speed of decay for the probability at the origin is the key for recurrence.
13. Localization and Fractality in Inhomogeneous Quantum Walks with Self-Duality
Yutaka Shikano, Hosho Katsura
Phys. Rev. E 82, 031122 (2010)
http://arxiv.org/abs/1004.5394
We introduce and study a class of discrete-time quantum walks on a one-dimensional lattice. In contrast to the standard homogeneous quantum walks, coin operators are inhomogeneous and depend on their positions in this class of models. The models are shown to be self-dual with respect to the Fourier transform, which is analogous to the Aubry-Andr\'e model describing the one-dimensional tight-binding model with a quasi-periodic potential. When the period of coin operators is incommensurate to the lattice spacing, we rigorously show that the limit distribution of the quantum walk is localized at the origin. We also numerically study the eigenvalues of the one-step time evolution operator and find the Hofstadter butterfly spectrum which indicates the fractal nature of this class of quantum walks.
14. Ambegaokar-Baratoff relations of Josephson critical current in heterojunctions with multi-gap superconductors
Yukihiro Ota, Noriyuki Nakai, Hiroki Nakamura, Masahiko Machida, Daisuke Inotani, Yoji Ohashi, Tomio Koyama, Hideki Matsumoto
Phys. Rev. B 81, 214511 (2010)
http://arxiv.org/abs/1004.0044
An extension of the Ambegaokar-Baratoff relation to a superconductor-insulator-superconductor (SIS) Josephson junction with multiple tunneling channels is derived. Appling the resultant relation to a SIS Josephson junction formed by an iron-based (five-band) and a single-band Bardeen-Cooper-Schrieffer (BCS) type superconductors, a theoretical bound of the Josephson critical current ($I_{\rm c}$) multiplied by the resistance of the junction ($R_{\rm n}$) is given. We reveal that such a bound is useful for identifying the pairing symmetry of iron-pnictide superconductors. One finds that if a measured value of $I_{\rm c}R_{\rm n}$ is smaller than the bound then the symmetry is $\pm s$-wave, and otherwise $s$-wave without any sign changes. In addition, we stress that temperature dependence of $I_{\rm c}R_{\rm n}$ is sensitive to the difference of the gap functions from the BCS type gap formula in the above heterojunction.
15. Bounds for mixing time of quantum walks on finite graphs
Vladislav Kargin
J. Phys. A: Math. Theor. 43 (2010) 335302
http://arxiv.org/abs/1004.0188
Several inequalities are proved for the mixing time of discrete-time quantum walks on finite graphs. The mixing time is defined differently than in Aharonov, Ambainis, Kempe and Vazirani (2001) and it is found that for particular examples of walks on a cycle, a hypercube and a complete graph, quantum walks provide no speed-up in mixing over the classical counterparts. In addition, non-unitary quantum walks (i.e., walks with decoherence) are considered and a criterion for their convergence to the unique stationary distribution is derived.