SESSION 4: Quantum algorithms and simulation

Chair: (David Meyer (University of California San Diego))
3:15pm-3:45pmRyan 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:15pmGuang 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:45pmNathan 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.

SQuInT Chief Organizer
Akimasa Miyake, Assistant Professor

SQuInT Co-Organizer
Mark M. Wilde, Assistant Professor LSU

SQuInT Administrator
Gloria Cordova
505 277-1850

SQuInT Founder
Ivan Deutsch, Regents' Professor

Tweet About SQuInT 2018!