Author name cluster

Rolando D. Somma

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

FOCS Conference 2023 Conference Paper

Exponential quantum speedup in simulating coupled classical oscillators *

Ryan Babbush
Dominic W. Berry
Robin Kothari
Rolando D. Somma
Nathan Wiebe

We study the problem of simulating the time evolution of a system of 2 n classical coupled oscillators (e. g. , 2 n balls connected by springs) on a quantum computer. We map Newton’s equation for harmonic potentials to Schrödinger’s equation, such that the amplitudes of an $\mathcal{O}(n)$-qubit quantum state encode the momenta and displacements of the 2 n classical oscillators. Given oracle access to the masses and spring constants, we describe a quantum algorithm with query and time complexity poly (n) that solves this problem when certain parameters are polynomially bounded and the initial state is easy to prepare. As an example application, we apply our quantum algorithm to efficiently estimate the normalized kinetic energy of an oscillator at any time. We then show that any classical algorithm solving the same problem must make $2^{\Omega(n)}$ queries to the oracle and we also show that when the oracles are instantiated by poly (n)-size circuits, the problem is BQP-complete. Thus, our approach solves a potentially practical application with an exponential speedup over classical computers.

Details

STOC Conference 2014 Conference Paper

Exponential improvement in precision for simulating sparse Hamiltonians

Dominic W. Berry
Andrew M. Childs
Richard Cleve
Robin Kothari
Rolando D. Somma

We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a d -sparse Hamiltonian H on n qubits can be simulated for time t with precision ε using O ( τ log( τ / ε )/log log( τ/ε )) queries and O ( τn log 2 ( τ/ε )/log log( τ/ε )) additional 2-qubit gates, where τ=d 2 ||H|| max t . Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also significantly simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.

Details

STOC Conference 2009 Conference Paper

Efficient discrete-time simulations of continuous-time quantum query algorithms

Richard Cleve
Daniel Gottesman
Michele Mosca
Rolando D. Somma
David L. Yonge-Mallo

The continuous-time query model is a variant of the discrete query model in which queries can be interleaved with known operations (called "driving operations") continuously in time. We show that any quantum algorithm in this model whose total query time is T can be simulated by a quantum algorithm in the discrete-time query model that makes O(T log T / loglog T) subset O~(T) queries. This is the first such upper bound that is independent of the driving operations (i.e., it holds even if the norm of the driving Hamiltonian is very large). A corollary is that any lower bound of T queries for a problem in the discrete-time query model immediately carries over to a lower bound of Omega(T loglog T / log T) subset Omega~(T) in the continuous-time query model.

Details