Quantum computing is powerful because unitary operators describing the time-evolution of a quantum system have exponential size in terms of the number of qubits present in the system. We develop a new \"Singular value transformation\" algorithm capable of harnessing this exponential advantage, that can apply polynomial transformations to the singular values of a block of a unitary, generalizing the optimal Hamiltonian simulation results of Low and Chuang. The proposed quantum circuits have a very simple structure, often give rise to optimal algorithms and have appealing constant factors, while usually only use a constant number of ancilla qubits. We show that singular value transformation leads to novel algorithms. We give an efficient solution to a certain \"non-commutative\" measurement problem and propose a new method for singular value estimation. We also show how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum. Finally, as a quantum machine learning application we show how to efficiently implement principal component regression. \"Singular value transformation\" is conceptually simple and efficient, and leads to a unified framework of quantum algorithms incorporating a variety of quantum speed-ups. We illustrate this by showing how it generalizes a number of prominent quantum algorithms, including: optimal Hamiltonian simulation, implementing the Moore-Penrose pseudoinverse with exponential precision, fixed-point amplitude amplification, robust oblivious amplitude amplification, fast QMA amplification, fast quantum OR lemma, certain quantum walk results and several quantum machine learning algorithms. In order to exploit the strengths of the presented method it is useful to know its limitations too, therefore we also prove a lower bound on the efficiency of singular value transformation, which often gives optimal bounds.

}, url = {https://arxiv.org/abs/1806.01838}, author = {Andras Gilyen and Yuan Su and Guang Hao Low and Nathan Wiebe} } @article {1812, title = {Hamiltonian Simulation with Optimal Sample Complexity}, journal = {npj Quantum Information}, volume = {13}, year = {2017}, month = {2017/03/31}, abstract = {We investigate the sample complexity of Hamiltonian simulation: how many copies of an unknown quantum state are required to simulate a Hamiltonian encoded by the density matrix of that state? We show that the procedure proposed by Lloyd, Mohseni, and Rebentrost [Nat. Phys., 10(9):631--633, 2014] is optimal for this task. We further extend their method to the case of multiple input states, showing how to simulate any Hermitian polynomial of the states provided. As applications, we derive optimal algorithms for commutator simulation and orthogonality testing, and we give a protocol for creating a coherent superposition of pure states, when given sample access to those states. We also show that this sample-based Hamiltonian simulation can be used as the basis of a universal model of quantum computation that requires only partial swap operations and simple single-qubit states.

\

},
doi = {10.1038/s41534-017-0013-7},
url = {https://www.nature.com/articles/s41534-017-0013-7},
author = {Shelby Kimmel and Cedric Yen-Yu Lin and Guang Hao Low and Maris Ozols and Theodore J. Yoder}
}
@article {1513,
title = {Robust Single-Qubit Process Calibration via Robust Phase Estimation},
journal = {Physical Review A},
volume = {92},
year = {2015},
month = {2015/12/08},
pages = {062315},
abstract = { An important step in building a quantum computer is calibrating
experimentally implemented quantum gates to produce operations that are close
to ideal unitaries. The calibration step involves estimating the error in gates
and then using controls to correct the implementation. Quantum process
tomography is a standard technique for estimating these errors, but is both
time consuming, (when one only wants to learn a few key parameters), and
requires resources, like perfect state preparation and measurement, that might
not be available. With the goal of efficiently estimating specific errors using
minimal resources, we develop a parameter estimation technique, which can gauge
two key parameters (amplitude and off-resonance errors) in a single-qubit gate
with provable robustness and efficiency. In particular, our estimates achieve
the optimal efficiency, Heisenberg scaling. Our main theorem making this
possible is a robust version of the phase estimation procedure of Higgins et
al. [B. L. Higgins, New J. Phys. 11, 073023 (2009)].
},
doi = {10.1103/PhysRevA.92.062315},
url = {http://arxiv.org/abs/1502.02677},
author = {Shelby Kimmel and Guang Hao Low and Theodore J. Yoder}
}