01807nas a2200145 4500008004100000245009300041210006900134260001400203520133200217100001601549700002701565700001701592700001501609856003701624 2023 eng d00aAnalyzing Convergence in Quantum Neural Networks: Deviations from Neural Tangent Kernels0 aAnalyzing Convergence in Quantum Neural Networks Deviations from c3/26/20233 a

A quantum neural network (QNN) is a parameterized mapping efficiently implementable on near-term Noisy Intermediate-Scale Quantum (NISQ) computers. It can be used for supervised learning when combined with classical gradient-based optimizers. Despite the existing empirical and theoretical investigations, the convergence of QNN training is not fully understood. Inspired by the success of the neural tangent kernels (NTKs) in probing into the dynamics of classical neural networks, a recent line of works proposes to study over-parameterized QNNs by examining a quantum version of tangent kernels. In this work, we study the dynamics of QNNs and show that contrary to popular belief it is qualitatively different from that of any kernel regression: due to the unitarity of quantum operations, there is a non-negligible deviation from the tangent kernel regression derived at the random initialization. As a result of the deviation, we prove the at-most sublinear convergence for QNNs with Pauli measurements, which is beyond the explanatory power of any kernel regression dynamics. We then present the actual dynamics of QNNs in the limit of over-parameterization. The new dynamics capture the change of convergence rate during training and implies that the range of measurements is crucial to the fast QNN convergence.

1 aYou, Xuchen1 aChakrabarti, Shouvanik1 aChen, Boyang1 aWu, Xiaodi uhttps://arxiv.org/abs/2303.1484401581nas a2200181 4500008004100000245006200041210006200103260001100165490000600176520106100182100002701243700002301270700001901293700001701312700001801329700001501347856003701362 2023 eng d00aQuantum algorithm for estimating volumes of convex bodies0 aQuantum algorithm for estimating volumes of convex bodies c4/20230 v43 a

Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an n-dimensional convex body within multiplicative error ε using O~(n3.5+n2.5/ε) queries to a membership oracle and O~(n5.5+n4.5/ε) additional arithmetic operations. For comparison, the best known classical algorithm uses O~(n4+n3/ε2) queries and O~(n6+n5/ε2) additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of "Chebyshev cooling", where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error.

1 aChakrabarti, Shouvanik1 aChilds, Andrew, M.1 aHung, Shih-Han1 aLi, Tongyang1 aWang, Chunhao1 aWu, Xiaodi uhttps://arxiv.org/abs/1908.0390301748nas a2200133 4500008004100000245008100041210006900122260001400191520131400205100001601519700002701535700001501562856003701577 2022 eng d00aA Convergence Theory for Over-parameterized Variational Quantum Eigensolvers0 aConvergence Theory for Overparameterized Variational Quantum Eig c5/25/20223 a

The Variational Quantum Eigensolver (VQE) is a promising candidate for quantum applications on near-term Noisy Intermediate-Scale Quantum (NISQ) computers. Despite a lot of empirical studies and recent progress in theoretical understanding of VQE's optimization landscape, the convergence for optimizing VQE is far less understood. We provide the first rigorous analysis of the convergence of VQEs in the over-parameterization regime. By connecting the training dynamics with the Riemannian Gradient Flow on the unit-sphere, we establish a threshold on the sufficient number of parameters for efficient convergence, which depends polynomially on the system dimension and the spectral ratio, a property of the problem Hamiltonian, and could be resilient to gradient noise to some extent. We further illustrate that this overparameterization threshold could be vastly reduced for specific VQE instances by establishing an ansatz-dependent threshold paralleling our main result. We showcase that our ansatz-dependent threshold could serve as a proxy of the trainability of different VQE ansatzes without performing empirical experiments, which hence leads to a principled way of evaluating ansatz design. Finally, we conclude with a comprehensive empirical study that supports our theoretical findings

1 aYou, Xuchen1 aChakrabarti, Shouvanik1 aWu, Xiaodi uhttps://arxiv.org/abs/2205.1248101237nas a2200253 4500008004100000245004100041210004100082260001300123520055200136100001900688700002400707700002100731700002000752700002700772700001800799700001600817700001700833700002000850700002100870700001900891700001300910700002300923856003700946 2021 eng d00aQuantum Machine Learning for Finance0 aQuantum Machine Learning for Finance c9/9/20213 a

Quantum computers are expected to surpass the computational capabilities of classical computers during this decade, and achieve disruptive impact on numerous industry sectors, particularly finance. In fact, finance is estimated to be the first industry sector to benefit from Quantum Computing not only in the medium and long terms, but even in the short term. This review paper presents the state of the art of quantum algorithms for financial applications, with particular focus to those use cases that can be solved via Machine Learning.

1 aPistoia, Marco1 aAhmad, Syed, Farhan1 aAjagekar, Akshay1 aButs, Alexander1 aChakrabarti, Shouvanik1 aHerman, Dylan1 aHu, Shaohan1 aJena, Andrew1 aMinssen, Pierre1 aNiroula, Pradeep1 aRattew, Arthur1 aSun, Yue1 aYalovetzky, Romina uhttps://arxiv.org/abs/2109.0429801551nas a2200181 4500008004100000245006000041210005800101300000800159490000600167520101600173100002701189700002401216700002301240700002701263700002001290700002201310856003701332 2021 eng d00aA Threshold for Quantum Advantage in Derivative Pricing0 aThreshold for Quantum Advantage in Derivative Pricing a4630 v53 a

We give an upper bound on the resources required for valuable quantum advantage in pricing derivatives. To do so, we give the first complete resource estimates for useful quantum derivative pricing, using autocallable and Target Accrual Redemption Forward (TARF) derivatives as benchmark use cases. We uncover blocking challenges in known approaches and introduce a new method for quantum derivative pricing - the re-parameterization method - that avoids them. This method combines pre-trained variational circuits with fault-tolerant quantum computing to dramatically reduce resource requirements. We find that the benchmark use cases we examine require 7.5k logical qubits and a T-depth of 46 million and thus estimate that quantum advantage would require a logical clock speed of 10Mhz. While the resource requirements given here are out of reach of current systems, we hope they will provide a roadmap for further improvements in algorithms, implementations, and planned hardware architectures. 

1 aChakrabarti, Shouvanik1 aKrishnakumar, Rajiv1 aMazzola, Guglielmo1 aStamatopoulos, Nikitas1 aWoerner, Stefan1 aZeng, William, J. uhttps://arxiv.org/abs/2012.0381901867nas a2200145 4500008004100000245007000041210006300111260001300174520141800187100001801605700001901623700002701642700001501669856003701684 2020 eng d00aOn the Principles of Differentiable Quantum Programming Languages0 aPrinciples of Differentiable Quantum Programming Languages c4/2/20203 a

Variational Quantum Circuits (VQCs), or the so-called quantum neural-networks, are predicted to be one of the most important near-term quantum applications, not only because of their similar promises as classical neural-networks, but also because of their feasibility on near-term noisy intermediate-size quantum (NISQ) machines. The need for gradient information in the training procedure of VQC applications has stimulated the development of auto-differentiation techniques for quantum circuits. We propose the first formalization of this technique, not only in the context of quantum circuits but also for imperative quantum programs (e.g., with controls), inspired by the success of differentiable programming languages in classical machine learning. In particular, we overcome a few unique difficulties caused by exotic quantum features (such as quantum no-cloning) and provide a rigorous formulation of differentiation applied to bounded-loop imperative quantum programs, its code-transformation rules, as well as a sound logic to reason about their correctness. Moreover, we have implemented our code transformation in OCaml and demonstrated the resource-efficiency of our scheme both analytically and empirically. We also conduct a case study of training a VQC instance with controls, which shows the advantage of our scheme over existing auto-differentiation for quantum circuits without controls.

1 aZhu, Shaopeng1 aHung, Shih-Han1 aChakrabarti, Shouvanik1 aWu, Xiaodi uhttps://arxiv.org/abs/2004.0112201173nas a2200157 4500008004100000245006400041210006400105260001500169490000600184520070600190100002700896700002300923700001700946700001500963856003700978 2020 eng d00aQuantum algorithms and lower bounds for convex optimization0 aQuantum algorithms and lower bounds for convex optimization c12/18/20190 v43 a

While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n-dimensional convex body using O~(n) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω~(n−−√) evaluation queries and Ω(n−−√) membership queries.

1 aChakrabarti, Shouvanik1 aChilds, Andrew, M.1 aLi, Tongyang1 aWu, Xiaodi uhttps://arxiv.org/abs/1809.0173101601nas a2200145 4500008004100000245007200041210006900113260001500182520114400197100001701341700001801358700002701376700001501403856003701418 2020 eng d00aSublinear classical and quantum algorithms for general matrix games0 aSublinear classical and quantum algorithms for general matrix ga c12/11/20203 a

We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix A∈Rn×d, sublinear algorithms for the matrix game minx∈Xmaxy∈Yy⊤Ax were previously known only for two special cases: (1) Y being the ℓ1-norm unit ball, and (2) X being either the ℓ1- or the ℓ2-norm unit ball. We give a sublinear classical algorithm that can interpolate smoothly between these two cases: for any fixed q∈(1,2], we solve the matrix game where X is a ℓq-norm unit ball within additive error ε in time O~((n+d)/ε2). We also provide a corresponding sublinear quantum algorithm that solves the same task in time O~((n−−√+d−−√)poly(1/ε)) with a quadratic improvement in both n and d. Both our classical and quantum algorithms are optimal in the dimension parameters n and d up to poly-logarithmic factors. Finally, we propose sublinear classical and quantum algorithms for the approximate Carathéodory problem and the ℓq-margin support vector machines as applications.

1 aLi, Tongyang1 aWang, Chunhao1 aChakrabarti, Shouvanik1 aWu, Xiaodi uhttps://arxiv.org/abs/2012.0651901810nas a2200169 4500008004100000245005600041210005600097260001500153490000700168520133300175100002701508700001801535700001701553700001801570700001501588856003701603 2019 eng d00aQuantum Wasserstein Generative Adversarial Networks0 aQuantum Wasserstein Generative Adversarial Networks c2019/10/310 v323 a

The study of quantum generative models is well-motivated, not only because of its importance in quantum machine learning and quantum chemistry but also because of the perspective of its implementation on near-term quantum machines. Inspired by previous studies on the adversarial training of classical and quantum generative models, we propose the first design of quantum Wasserstein Generative Adversarial Networks (WGANs), which has been shown to improve the robustness and the scalability of the adversarial training of quantum generative models even on noisy quantum hardware. Specifically, we propose a definition of the Wasserstein semimetric between quantum data, which inherits a few key theoretical merits of its classical counterpart. We also demonstrate how to turn the quantum Wasserstein semimetric into a concrete design of quantum WGANs that can be efficiently implemented on quantum machines. Our numerical study, via classical simulation of quantum systems, shows the more robust and scalable numerical performance of our quantum WGANs over other quantum GAN proposals. As a surprising application, our quantum WGAN has been used to generate a 3-qubit quantum circuit of ~50 gates that well approximates a 3-qubit 1-d Hamiltonian simulation circuit that requires over 10k gates using standard techniques.

1 aChakrabarti, Shouvanik1 aHuang, Yiming1 aLi, Tongyang1 aFeizi, Soheil1 aWu, Xiaodi uhttps://arxiv.org/abs/1911.0011101473nas a2200157 4500008004100000245008200041210006900123260001500192300001400207490000700221520099100228100001701219700002701236700001501263856003701278 2019 eng d00aSublinear quantum algorithms for training linear and kernel-based classifiers0 aSublinear quantum algorithms for training linear and kernelbased c04/03/2019 a3815-38240 v973 a

We investigate quantum algorithms for classification, a fundamental problem in machine learning, with provable guarantees. Given n d-dimensional data points, the state-of-the-art (and optimal) classical algorithm for training classifiers with constant margin runs in O~(n+d) time. We design sublinear quantum algorithms for the same task running in O~(n−−√+d−−√) time, a quadratic improvement in both n and d. Moreover, our algorithms use the standard quantization of the classical input and generate the same classical output, suggesting minimal overheads when used as subroutines for end-to-end applications. We also demonstrate a tight lower bound (up to poly-log factors) and discuss the possibility of implementation on near-term quantum machines. As a side result, we also give sublinear quantum algorithms for approximating the equilibria of n-dimensional matrix zero-sum games with optimal complexity Θ~(n−−√). 

1 aLi, Tongyang1 aChakrabarti, Shouvanik1 aWu, Xiaodi uhttps://arxiv.org/abs/1904.02276