1. Quantum Speed-up for Approximating Partition Functions
Pawel Wocjan, Chen-Fu Chiang, Anura Abeyesinghe, Daniel Nagaj
Phys. Rev. A 80, 022340 (2009)
http://arxiv.org/abs/0811.0596
We achieve a quantum speed-up of fully polynomial randomized approximation schemes (FPRAS) for estimating partition functions that combine simulated annealing with the Monte-Carlo Markov Chain method and use non-adaptive cooling schedules. The improvement in time complexity is twofold: a quadratic reduction with respect to the spectral gap of the underlying Markov chains and a quadratic reduction with respect to the parameter characterizing the desired accuracy of the estimate output by the FPRAS. Both reductions are intimately related and cannot be achieved separately. First, we use Grover's fixed point search, quantum walks and phase estimation to efficiently prepare approximate coherent encodings of stationary distributions of the Markov chains. The speed-up we obtain in this way is due to the quadratic relation between the spectral and phase gaps of classical and quantum walks. Second, we generalize the method of quantum counting, showing how to estimate expected values of quantum observables. Using this method instead of classical sampling, we obtain the speed-up with respect to accuracy.
2. Solid State Implementation of Quantum Random Walks on General Graphs
K Manouchehri, J.B. Wang
http://arxiv.org/abs/0811.1795
Advances in recent years have made it possible to explore quantum dots as a viable technology for scalable quantum information processing. Charge qubits for example can be realized in the lowest bound states of coupled quantum dots and the precision control of the confinement potential allows for the realization of a full set of universal qubit gates, including arbitrary single-qubit rotations and two-qubit C-NOT gates. In this work we describe a novel scheme for implementing quantum random walks on arbitrarily complex graphs by extending these elementary operations to the control of a two-dimensional quantum dot grid. As single-qubit rotations constitute the essential building blocks of our implementation scheme, we also present numerical simulations of one such mechanism by directly solving the corresponding time-dependent Schrodinger equation.
3. The Detectability Lemma and Quantum Gap Amplification
Dorit Aharonov, Itai Arad, Zeph Landau, Umesh Vazirani
http://arxiv.org/abs/0811.3412
The quantum analogue of a constraint satisfaction problem is a sum of local Hamiltonians - each local Hamiltonian specifies a local constraint whose violation contributes to the energy of the given quantum state. Formalizing the intuitive connection between the ground (minimal) energy of the Hamiltonian and the minimum number of violated constraints is problematic, since the number of constraints being violated is not well defined when the terms in the Hamiltonian do not commute. The detectability lemma proved in this paper provides precisely such a quantitative connection. We apply the lemma to derive a quantum analogue of a basic primitive in classical complexity: amplification of probabilities by random walks on expander graphs. It holds under the restriction that the interaction graph of the local Hamiltonian is an expander. Our proofs are based on a novel structure imposed on the Hilbert space that we call the $XY$ decomposition, which enables a reduction from the quantum non-commuting case to the commuting case (where many classical arguments go through). The results may have several interesting implications. First, proving a quantum analogue to the PCP theorem is one of the most important challenges in quantum complexity theory. Our quantum gap amplification lemma may be viewed as the quantum analogue of the first of the three main steps in Dinur's PCP proof. Quantum gap amplification may also be related to spectral gap amplification, and in particular, to fault tolerance of adiabatic computation. Finally, the detectability lemma, and the $XY$ decomposition provide a handle on the structure of local Hamiltonians and their ground states.
4. Complete Characterization of Mixing Time for the Continuous Quantum Walk on the Hypercube with Markovian Decoherence Model
Milosh Drezgich, Andrew P. Hines, Mohan Sarovar, Shankar Sastry
Quantum Inf. & Comp., vol. 9, p. 856 (2009)
http://arxiv.org/abs/0811.4472
The n-dimensional hypercube quantum random walk (QRW) is a particularily appealing example of a quantum walk because it has a natural implementation on a register on $n$ qubits. However, any real implementation will encounter decoherence effects due to interactions with uncontrollable degrees of freedom. We present a complete characterization of the mixing properties of the hypercube QRW under a physically relevant Markovian decoherence model. In the local decoherence model considered the non-unitary dynamics are modeled as a sum of projections on individual qubits to an arbitrary direction on the Bloch sphere. We prove that there is always classical (asymptotic) mixing in this model and specify the conditions under which instantaneous mixing \textit{always} exists. And we show that the latter mixing property, as well as the classical mixing time, depend heavily on the exact environmental interaction and its strength. Therefore, algorithmic applications of the QRW on the hypercube, if they intend to employ mixing properties, need to consider both the walk dynamics and the precise decoherence model.