UC Berkeley

The problem of unstructured search plays the central role in our current understanding of the computational power of quantum computers. Improvement in the efficiency of solving unstructured search problem has an immediate consequence in the improvement in solving NP-complete problems. We introduce the new framework of natural continuous time quantum search algorithms, that in contrast to the adiabatic quantum algorithms, require neither the ground state initialization nor the adiabatic change of the Hamiltonian parameters. We moreover provide the concrete examples of transliteration from the unique marked element unstructured search problem into the particular class of quantum Hamiltonians, that facilitate the search in quantum continuous constant time. Since it is not clear how to implement that class of Hamiltonians one can either consider this result as a step toward proving that NP is a subset of BQP or as an indication that, that class of Hamiltonians is NP-hard to implement.

Multiplicative weights update rule has been used in a few different fields as the underlying algorithmic structure. In its two different forms, vector and matrix, multiplicative update method provided a surprising simplicity and promised a small performance regret. We derive a slightly more general bound for the cumulative matrix multiplicative weights algorithm and introduce the iterative (streaming) matrix multiplicative weights algorithm with the same computational complexity and regret bound. In particular we also define the iterative Hadamard updates, matrix multiplicative updates algorithm, with the improved computational complexity for nonnegative games, from O(n³) to O(n²), and the same regret bound.

Furthermore, we address the following question:"What is the minimal size quantum circuit required to exactly implement a specified nqubit unitary operation U, without the use of ancilla qubits?" Nielsen proved that a lower bound on the minimal size circuit is provided by the length of the geodesic between the identity I and U, where the length is defined by a suitable Finsler metric on SU(2ⁿ). We prove that the minimum circuit size that simulates U is in linear relation with the geodesic length and simulation parameters, for the given Finsler structure F. As a corollary we prove the highest lower bound and the lowest upper bound for the standard simulation technique, that show that by standard simulation one can not expect a better then n² times improvement in the upper bound over the result from Nielsen, Dowling, Gu and Doherty. Moreover, our equivalence result can be applied to the arbitrary path on the manifold including the one that is generated adiabatically.

Finally we investigate the n-dimensional hypercube quantum random walk (QRW) as a particularly 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 a classical asymptotic mixing in this model and specify the conditions under which instantaneous mixing always exists. 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.