Events Calendar
A Circuit-based Quantum Search Algorithm Driving by Transverse Fields
Wednesday October 19, 2016
4:00 pm
Tweet |
Presenter: | Zhang Jiang, QuAIL, NASA Ames Research Center; and Stinger GhaffarianTechnologies, Inc. |
---|---|---|
Series: | CQuIC Seminars | |
Abstract: | We designed a quantum search algorithm, giving the same quadratic speedup achieved by Grover's original algorithm; we replace Grover's diffusion operator (hard to implement) with a product diffusion operator generated by transverse fields (easy to implement). In our algorithm, the problem Hamiltonian (oracle) and the transverse fields are applied to the system alternatively. We construct such a sequence that the corresponding unitary generates a closed transition between the initial state (even superposition of all states) and a modified target state, which has a high degree of overlap with the original target state. Let N = 2^n be the size of the search space. The transition rate is of order O(1/sqrt N), and the overlap is of order O(1/sqrt n), yielding a O(sqrt N) algorithm up to log(N) factors. Our algorithm belongs to a class of algorithms proposed by Farhi et al. [1-3], namely the Quantum Approximate Optimization Algorithm (QAOA). | |
Location: | PAIS-2540, PAIS | |