Program
Full Program | Thursday | Friday | Saturday | All Sessions | Posters | Talks
LSU SQuInT Event Map
SESSION 9c: Quantum algorithms and compiling (JC Miller Hall, Rm 232)Chair: (Zhihui Wang (NASA Ames)) | |
| 3:45pm - 4:15pm | Zhang Jiang, NASA Ames A circuit-based quantum search algorithm driven by transverse fields | 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 two states; one has a big overlap with the initial state (even superposition of all states), and the other has a big overlap with the target state. Let N = 2n be the size of the search space. The transition rate is of order O(N-1/2), yielding a O(N1/2) algorithm. Our algorithm belongs to a class of algorithms recently proposed by Farhi et al., namely the Quantum Approximate Optimization Algorithm (QAOA). |
| 4:15pm - 4:45pm | Ciaran Ryan-Anderson, CQuIC New Mexico, Sandia Investigating the quantum approximate optimization algorithm's advantage over classical algorithms | Abstract. The Quantum Approximate Optimization Algorithm (QAOA) is designed to find approximate solutions to combinatorial optimization problems. The approximation quality of QAOA is a function of the parameters to the algorithm, one of which corresponds to the depth of a quantum circuit realizing QAOA. Recently, in [1], it has been shown that even when QAOA is used in its lowest-depth form, it can produce distributions that are hard to sample from classically. This indicates that QAOA can demonstrate some level of ``Quantum Supremacy," at least for the task of sampling from a distribution. However, QAOA is foremost an optimization algorithm, and QAOA's complexity as an optimization algorithm is largely open. In this work we investigate QAOA's advantage over classical algorithms from an optimization perspective. This work was supported by the Laboratory Directed Research and Development (LDRD) program at Sandia National Laboratories. Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy's National Nuclear Security Administration under contract DE-AC04-94AL85000. [1] E. Farhi and A. W. Harrow, Quantum supremacy through the quantum approximate optimization algorithm, (2016), arXiv:1602.07674. |
| 4:45pm - 5:15pm | Lucas Brady, UC Santa Barbara Necessary adiabatic run times in quantum optimization | Abstract. Quantum annealing is guaranteed to find the ground state of optimization problems in the adiabatic limit. Recent work [Phys. Rev. X 6, 031010 (2016)] has found that for some barrier tunneling problems, quantum annealing can be run much faster than is adiabatically required. Specifically, an n-qubit optimization problem was presented for which a non-adiabatic, or diabatic, annealing algorithm requires only constant runtime, while an adiabatic annealing algorithm requires a runtime polynomial in n. Here we show that this non-adiabatic speed-up is a direct result of a specific symmetry in the studied problems. In the more general case, no such non-adiabatic speed-up occurs. We furthermore show why the special case achieves this speed-up compared to the general case. We conclude with the observation that the adiabatic annealing algorithm has a necessary and sufficient runtime that is quadratically better than the standard quantum adiabatic condition suggests. |
| 5:15pm - 5:45pm | Sergey Knysh, NASA Ames Squeezed state ansatz for quantum Sherrington-Kirkpatrick model and its applications to quantum annealing | Abstract. A question of fundamental importance in the physics of quantum annealing is its scalability. Recent work predicts a crossover from polynomial to exponential complexity for quantum annealing of spin glasses and relates the problem size at which this occurs to the "density" of spin glass bottlenecks [1]. An exact solution has been obtained for a toy problem, but rigorous analysis has remained elusive for realistic spin glass models where naive mean field fails. The present work takes a step in that direction by investigating thermodynamics of quantum Sherrington-Kirkpatrick model without resorting to replicas. The approach uses hard-core boson representation of a spin-1/2 model, with "modes" corresponding to delocalized eigenvectors of the interaction matrix. Hard-core nature of bosons is taken into account by appropriate renormalization factors. In this formulation, the ground state of paramagnetic phase is approximated by applying mode-dependent amount of squeezing/anti-squeezing to a vacuum, and the low-energy excitations correspond to Bogolyubov quasiparticles. Spin-glass phase is characterized by macroscopic occupation of a finite fraction of modes. Theoretical predictions are compared with known numerical results. [1] S. Knysh, "Zero-temperature quantum annealing bottlenecks in the spin-glass phase", Nature Communications 7, 12370 (2016). |
| 5:45pm - 6:15pm | Martin Roetteler, Microsoft Factoring using 2n+2 qubits with Toffoli based modular multiplication | Abstract. We describe an implementation of Shor's quantum algorithm to factor n-bit integers using only 2n+2 qubits. In contrast to previous space-optimized implementations, ours features a purely Toffoli based modular multiplication circuit. The circuit depth and the overall gate count are in O(n^3) and O(n^3 log(n)), respectively. We thus achieve the same space and time costs as Takahashi et al., while using a purely classical modular multiplication circuit. As a consequence, our approach evades most of the cost overheads originating from rotation synthesis and enables testing and localization of faults in both, the logical level circuit and an actual quantum hardware implementation. We implemented and simulated a Toffoli network for the entire controlled modular multiplication piece of Shor's algorithm in LIQUi|>, for real-world bit-sizes of up to 8,192. Asymptotically, our new (in-place) constant-adder, which is used to construct the modular multiplication circuit, uses only dirty ancilla qubits and features a circuit size and depth in O(n log(n)) and O(n), respectively. Our resource estimates determine also the constants for the scaling of the circuit size. |
SQuInT Chief Organizer
Akimasa Miyake, Assistant Professor
amiyake@unm.edu
SQuInT Co-Organizer
Mark M. Wilde, Assistant Professor LSU
mwilde@phys.lsu.edu
SQuInT Administrator
Gloria Cordova
gjcordo1@unm.edu
505 277-1850
SQuInT Event Coordinator
Karen Jones, LSU
kjones@cct.lsu.edu
SQuInT Founder
Ivan Deutsch, Regents' Professor
ideutsch@unm.edu
