Author name cluster

Nathan Wiebe

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.

5 papers

2 author rows

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

SODA Conference 2019 Conference Paper

Optimizing quantum optimization algorithms via faster quantum gradient computation

András Gilyén
Srinivasan Arunachalam
Nathan Wiebe

We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate realvalued function f: ℝ d → ℝ by evaluating it at only a logarithmic number of times in superposition. Our algorithm is an improved version of Jordan's gradient computation algorithm [28], providing an approximation of the gradient ▽ f with quadratically better dependence on the evaluation accuracy of f, for an important class of smooth functions. Furthermore, we show that objective functions arising from variational quantum circuits usually satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension d. One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function f. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).

Details

STOC Conference 2019 Conference Paper

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

András Gilyén
Yuan Su
Guang Hao Low
Nathan Wiebe

An n -qubit quantum circuit performs a unitary operation on an exponentially large, 2 n -dimensional, Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular value transformation” algorithm that can directly harness the advantages of exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator. The transformations are realized by quantum circuits with a very simple structure - typically using only a constant number of ancilla qubits - leading to optimal algorithms with appealing constant factors. We show that our framework allows describing many quantum algorithms on a high level, and enables remarkably concise proofs for many prominent quantum algorithms, ranging from optimal Hamiltonian simulation to various quantum machine learning applications. We also devise a new singular vector transformation algorithm, describe how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum, and show how to efficiently implement principal component regression. Finally, we also prove a quantum lower bound on spectral transformations.

Details

NeurIPS Conference 2016 Conference Paper

Quantum Perceptron Models

Ashish Kapoor
Nathan Wiebe
Krysta Svore

We demonstrate how quantum computation can provide non-trivial improvements in the computational and statistical complexity of the perceptron model. We develop two quantum algorithms for perceptron learning. The first algorithm exploits quantum information processing to determine a separating hyperplane using a number of steps sublinear in the number of data points $N$, namely $O(\sqrt{N})$. The second algorithm illustrates how the classical mistake bound of $O(\frac{1}{\gamma^2})$ can be further improved to $O(\frac{1}{\sqrt{\gamma}})$ through quantum means, where $\gamma$ denotes the margin. Such improvements are achieved through the application of quantum amplitude amplification to the version space interpretation of the perceptron model.

PDF Details

IROS Conference 2007 Conference Paper

A local approach to developing grounded spatial references in multi-robot systems

Nathan Wiebe
John Anderson

For a mobile robot to be able to communicate usefully with others, the symbols it uses to communicate must be grounded to entities in the environment, and those groundings made consistent among agents. While it is common practice to hand-construct such groundings, this does not scale to large problems. In particular, when communicating about useful spatial references, there are a large number of potentially relevant groundings, even for a basic task such as navigation. This paper describes the development and evaluation of an approach that allows a group of robotic agents to develop consistent shared groundings for locations in an environment over time. This approach is based on local communication and interaction, and does not rely on the ability to broadcast references to all agents, and so is suitable for domains in which communication may be sporadic, such as robotic rescue. The evaluation of this approach, which compares several different grounding techniques, shows that shared groundings can be developed effectively over time, and that these improve the effectiveness of communication in a multi-robot setting.

Details