@article {2388, title = {Distributional property testing in a quantum world}, journal = {Proceedings of ITCS 2020}, volume = {25}, year = {2020}, month = {02/02/2019}, pages = {1-25}, abstract = {

A fundamental problem in statistics and learning theory is to test properties of distributions. We show that quantum computers can solve such problems with significant speed-ups. In particular, we give fast quantum algorithms for testing closeness between unknown distributions, testing independence between two distributions, and estimating the Shannon / von Neumann entropy of distributions. The distributions can be either classical or quantum, however our quantum algorithms require coherent quantum access to a process preparing the samples. Our results build on the recent technique of quantum singular value transformation, combined with more standard tricks such as divide-and-conquer. The presented approach is a natural fit for distributional property testing both in the classical and the quantum case, demonstrating the first speed-ups for testing properties of density operators that can be accessed coherently rather than only via sampling; for classical distributions our algorithms significantly improve the precision dependence of some earlier results.

}, doi = {http://dx.doi.org/10.4230/LIPIcs.ITCS.2020.25}, url = {https://arxiv.org/abs/1902.00814}, author = {Andras Gilyen and Tongyang Li} } @article {2501, title = {Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning}, journal = {to appear in Proceedings of STOC 2020}, year = {2020}, month = {6/18/2020}, abstract = {

We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang\&$\#$39;s breakthrough quantum-inspired algorithm for recommendation systems [STOC\&$\#$39;19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gily{\'e}n et al. [STOC\&$\#$39;19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all recent results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: l2-norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.

}, doi = {https://doi.org/10.1145/3357713.3384314}, url = {https://arxiv.org/abs/1910.06151}, author = {Nai-Hui Chia and Andras Gilyen and Tongyang Li and Han-Hsuan Lin and Ewin Tang and Chunhao Wang} } @conference {2599, title = {Symmetries, graph properties, and quantum speedups}, booktitle = {Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020), pp. 649{\textendash}660 (2020)}, year = {2020}, month = {6/23/2020}, abstract = {

Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup?
In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups.
In contrast, in the adjacency list model for bounded-degree graphs (where graph symmetry is manifested differently), we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).

}, doi = {https://doi.org/10.1109/FOCS46700.2020.00066}, url = {https://arxiv.org/abs/2006.12760}, author = {Shalev Ben-David and Andrew M. Childs and Andras Gilyen and William Kretschmer and Supartha Podder and Daochen Wang} } @article {2175, title = {Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics}, journal = {Proceedings of the 51st ACM Symposium on Theory of Computing }, year = {2018}, month = {2018/06/05}, pages = {193-204}, abstract = {

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.

}, doi = {https://doi.org/10.1145/3313276.3316366}, url = {https://arxiv.org/abs/1806.01838}, author = {Andras Gilyen and Yuan Su and Guang Hao Low and Nathan Wiebe} }