1. Open system approach to the internal dynamics of a model multilevel molecule
Filippo Giraldi, Francesco Petruccione
Open Syst. Inf. Dyn. 19, 1250011 (2012)
http://arxiv.org/abs/1011.1238
A model multilevel molecule described by two sets of rotational internal energy levels of different parity and degenerate ground states, coupled by a constant interaction, is considered, by assuming that the random collisions in a gas of identical molecules, provoke transitions between adjacent energy levels of the same parity. The prescriptions of the continuous time quantum random walk are applied to the single molecule, interpreted as an open quantum system, and the master equation driving its internal dynamics is built for a general distribution of the waiting times between two consecutive collisions. The coherence terms and the populations of the energy levels relax to the asymptotics with inverse power laws for relevant classes of non-Poissonian distributions of the collision times. The stable asymptotic equilibrium configuration is independent of the distribution. The long time dynamics may be hindered by increasing the tail of the distribution density. This effect may be interpreted as the appearance of the quantum Zeno effect over long time scales.
2. Quantum query complexity of minor-closed graph properties
Andrew M. Childs, Robin Kothari
Proc. 28th Symposium on Theoretical Aspects of Computer Science (STACS 2011), Leibniz International Proceedings in Informatics 9, pp. 661-672
http://arxiv.org/abs/1011.1443
We study the quantum query complexity of minor-closed graph properties, which include such problems as determining whether an $n$-vertex graph is planar, is a forest, or does not contain a path of a given length. We show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity \Theta(n^{3/2}). To establish this, we prove an adversary lower bound using a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. On the other hand, we show that minor-closed properties (and more generally, sparse graph properties) that can be characterized by finitely many forbidden subgraphs can be solved strictly faster, in o(n^{3/2}) queries. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems.
3. Full-revivals in 2-D Quantum Walks
M. Stefanak, B. Kollar, T. Kiss, I. Jex
Phys. Scr. T140, 014035 (2010)
http://arxiv.org/abs/1011.2066
Recurrence of a random walk is described by the Polya number. For quantum walks, recurrence is understood as the return of the walker to the origin, rather than the full-revival of its quantum state. Localization for two dimensional quantum walks is known to exist in the sense of non-vanishing probability distribution in the asymptotic limit. We show on the example of the 2-D Grover walk that one can exploit the effect of localization to construct stationary solutions. Moreover, we find full-revivals of a quantum state with a period of two steps. We prove that there cannot be longer cycles for a four-state quantum walk. Stationary states and revivals result from interference which has no counterpart in classical random walks.
4. The Computational Complexity of Linear Optics
Scott Aaronson, Alex Arkhipov
http://arxiv.org/abs/1011.3245
We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum computation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions. Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then P^#P=BPP^NP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation. Our main result suggests that even an approximate or noisy classical simulation would already imply a collapse of the polynomial hierarchy. For this, we need two unproven conjectures: the "Permanent-of-Gaussians Conjecture", which says that it is #P-hard to approximate the permanent of a matrix A of independent N(0,1) Gaussian entries, with high probability over A; and the "Permanent Anti-Concentration Conjecture", which says that |Per(A)|>=sqrt(n!)/poly(n) with high probability over A. We present evidence for these conjectures, both of which seem interesting even apart from our application. This paper does not assume knowledge of quantum optics. Indeed, part of its goal is to develop the beautiful theory of noninteracting bosons underlying our model, and its connection to the permanent function, in a self-contained way accessible to theoretical computer scientists.
5. Verifying Genuine High-Order Entanglement
Che-Ming Li, Kai Chen, Andreas Reingruber, Yueh-Nan Chen, Jian-Wei Pan
Phys. Rev. Lett. 105, 210504 (2010)
http://arxiv.org/abs/1011.5012
High-order entanglement embedded in multipartite multilevel quantum systems (qudits) with many degrees of freedom (DOFs) plays an important role in quantum foundation and quantum engineering. Verifying high-order entanglement without the restriction of system complexity is a critical need in any experiments on general entanglement. Here, we introduce a scheme to efficiently detect genuine high-order entanglement, such as states close to genuine qudit Bell, Greenberger-Horne-Zeilinger, and cluster states as well as multilevel multi-DOF hyperentanglement. All of them can be identified with two local measurement settings per DOF regardless of the qudit or DOF number. The proposed verifications together with further utilities such as fidelity estimation could pave the way for experiments by reducing dramatically the measurement overhead.
6. Maximal entanglement from quantum random walks
B. Alles, S. Gunduc, Y. Gunduc
Quantum Information Processing: Volume 11, Issue 1 (2012), Page 211-227
http://arxiv.org/abs/1011.6023
The conditions under which entanglement becomes maximal are sought in the general one--dimensional quantum random walk with two walkers. Moreover, a one--dimensional shift operator for the two walkers is introduced and its performance in generating entanglement is analyzed as a function of several free parameters, some of them coming from the shift operator itself and some others from the coin operator. To simplify the investigation an averaged entanglement is defined.
7. Quantum Walks on Regular Graphs and Eigenvalues
Chris Godsil, Krystal Guo
http://arxiv.org/abs/1011.5460
We study the transition matrix of a quantum walk on strongly regular graphs. It is proposed by Emms, Hancock, Severini and Wilson in 2006, that the spectrum of $S^+(U^3)$, a matrix based on the amplitudes of walks in the quantum walk, distinguishes strongly regular graphs. We find the eigenvalues of $S^+(U)$ and $S^+(U^2)$ for regular graphs.