Program
Full Program | Thursday | Friday | Saturday | All Sessions | Posters | Talks
SESSION 4: Quantum algorithms and simulationChair: (David Meyer (University of California San Diego)) | |
| 3:15pm-3:45pm | Ryan Babbush, Google Low depth quantum simulation of electronic structure | Abstract. Quantum simulation of the electronic structure problem is one of the most researched applications of quantum computing. The majority of quantum algorithms for this problem encode the wavefunction using N Gaussian orbitals, leading to Hamiltonians with \(O(N^4)\) second-quantized terms. We avoid this overhead and extend methods to the condensed phase by utilizing a dual form of the plane wave basis which diagonalizes the potential operator, leading to a Hamiltonian representation with \(O(N^2)\) second-quantized terms. Using this representation we can implement single Trotter steps of the Hamiltonians with linear gate depth on a planar lattice. Properties of the basis allow us to deploy Trotter and Taylor series based simulations with respective circuit depths of \(O(N^{7/2})\) and \(O(N^{8/3})\) for fixed charge densities - both are large asymptotic improvements over all prior results. Variational algorithms also require significantly fewer measurements to find the mean energy in this basis, ameliorating a primary challenge of that approach. We conclude with a proposal to simulate the uniform electron gas (jellium) using a low depth variational ansatz realizable on near-term quantum devices. From these results we identify simulations of low density jellium as a promising first setting to explore quantum supremacy in electronic structure. |
| 3:45pm-4:15pm | Guang Hao Low, Microsoft Research Advances in optimal Hamiltonian simulation | Abstract. The exponential speedups promised by Hamiltonian simulation on a quantum computer depends crucially on structure in both the Hamiltonian \(\hat{H}\), and the quantum circuit \(\hat{U}\) that encodes its description. In the quest to better approximate time-evolution \(e^{-i\hat{H}t}\) with error \(\epsilon\), we motivate a systematic approach to understanding and exploiting structure, in a setting where Hamiltonians are encoded as measurement operators of unitary circuits \(\hat{U}\) for generalized measurement. This allows us to define a uniform spectral amplification problem on this framework for expanding the spectrum of encoded Hamiltonian with exponentially small distortion. We present general solutions to uniform spectral amplification in a hierarchy where factoring \(\hat{U}\) into \(n=1,2,3\) unitary oracles represents increasing structural knowledge of the encoding. Combined with structural knowledge of the Hamiltonian and recent 'quantum signal processing' and 'Qubitization' techniques, specializing these results allow us simulate time-evolution by \(d\)-sparse Hamiltonians using \(\mathcal{O}\left(t(d \|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2}\log{(t\|\hat{H}\|/\epsilon)}\right)\) queries given the norms \(\|\hat H\|\le \|\hat H\|_1\le d\|\hat H\|_{\text{max}}\). Up to logarithmic factors, this is a strict polynomial improvement upon prior art. |
| 4:15pm-4:45pm | Nathan Wiebe, Microsoft Research Optimizing quantum optimization algorithms via faster quantum gradient computation | Abstract. We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that calculates the gradient of a multi-variate real-valued function by evaluating it at only a logarithmic number of points in superposition. Our algorithm is an improved version of Jordan's gradient calculation algorithm, providing an approximation of the gradient of the function with quadratically better dependence on the evaluation accuracy of the function, for a class of smooth functions. Furthermore, we show that most functions arising from quantum optimization algorithms satisfy the necessary smoothness conditions; our new algorithm thereby provides a quadratic improvement in the complexity of their gradient calculation step. We also show that in a continuous phase query model, our gradient calculation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. One of the main technical challenges in applying our gradient calculation procedure for optimization algorithms is the necessity of interconversion between a probability oracle (which is common in quantum optimization procedures) and phase oracle (which is common in quantum query algorithms) of the objective function. We provide efficient subroutines to perform this delicate interconversion between the two type of oracles incurring only a logarithmic overhead, which might be of independent interest. |
- Home
- SQuInT
- Past SQuInT Meetings
- Lodging and Transportation
- Hotel Floor Maps (.pdf)
- Registration
- Submit Your Abstract
- Program
- Instructions for Presenters
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 Founder
Ivan Deutsch, Regents' Professor
ideutsch@unm.edu
