Computer Science

1. Landscape Independence.  Consider problems where instances come from a fixed distritution such as MAX CUT on d-regular random graphs of fixed size.  Then regardless of the depth of the algorithm, for fixed parameters the expected value of cost funtion in the associated quantum state is independent of the instance up to finite size effects. This Landscape Independence shows that once good parameters have been chosen for one instance they can be used for others coming from the same distribution. 2.Sherrington Kirkpatrick.  This is an all to all connected spin glass model. We have a method for calculating the expected value of the cost function at any parameters for typical instances in the infinite size limit. The method works for any depth p (independent of the number of spins) and numerically we have gone out to p of 8.  I will also discuss provable concentration results which confirm Landscape Independence for the SK model.

Algorithms on convex bodies is a central topic in the theory of convex optimization. In this talk, I will introduce two quantum algorithms that we recently proposed with quantum speedups compared to their state-of-the-art classical counterparts. First, I will present a quantum algorithm that estimates the volume of an n-dimensional convex body within multiplicative error eps using tilde{O}(n^3+n^2.5/eps) queries to the membership oracle of the convex body and tilde{O}(n^5+n^4.5/eps) additional arithmetic operations. For comparison, the best-known classical algorithm uses tilde{O}(n^4+n^3/eps^2) queries and tilde{O}(n^6+n^5/eps^2) additional arithmetic operations. Furthermore, I will also briefly introduce a quantum algorithm that can optimize a convex function over an n-dimensional convex body using tilde{O}(n) queries to the membership oracle and the evaluation oracle of the convex function. This represents a quadratic improvement over the best-known classical algorithm.

Second-order cone programs (SOCPs) are a class of convex optimization problems that generalize linear programs (LPs).  We present a quantum interior-point method for SOCPs with n variables and r  conic constraints with running time $O( n^{1.5} r^{0.5} \kappa/ \delta^2)$ where $\delta$ bounds the distance of intermediate solutions from the cone boundary and $\kappa$ is an upper bound on the condition number of matrices arising in the classical interior-point method for SOCPs. We present experimental evidence that the proposed quantum algorithm achieves a polynomial speedup over classical SOCP solvers for the Support Vector Machine (SVM) and Portfolio Optimization problems, which are known to be reducible to SOCPs.

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. The class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into constant factor approximations of the original quadratic optimization problem. This is joint work with Fernando Brandão and Daniel Stilck França.

We discuss a classical analogue to the singular value transformation framework for quantum linear algebra algorithms developed by Gilyén et al. The proofs underlying this classical framework have natural connections to well-known ideas in randomized numerical linear algebra. Namely, our proofs are based on one key observation: approximating matrix products is easy in the quantum-inspired input model. This primitive's simplicity makes finding classical analogues to quantum machine learning algorithms straightforward and intuitive. We present sketches of the key proofs of our sketches as well as of its applications to dequantizing low-rank quantum machine learning. Joint work with Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang.

A small random sample of rows/columns of any matrix is a decent proxy for the matrix, provided sampling probabilities are proportional to squared lengths. Since the early theorems on this from the 90’s, there has been a substantial body of work using sampling (random projections and probabil-ties based on leverage scores are two examples) to reduce matrix sizes for Linear Algebra computations. The talk will describe theorems, applications and challenges in the area.

Variational Quantum Circuits, which include examples of quantum approximate optimization algorithms (QAOA),  variational quantum eigensolver (VQE), and quantum neural-networks (QNN), are predicted to be one of the most important near-term quantum applications, not only because of their potential promises as classical neural-networks but also because of their feasibility on near-term noisy intermediate size quantum (NISQ) machines. This talk reports some progress toward a principled understanding of the training of variational quantum circuits. First, I will demonstrate the difficulty of training by constructing an example with exponentially many local optima,  however,  due to a differential nature from classical neural-networks. Second, I will explain how to facilitate the training by incorporating the optimal-transport norm in the context of quantum generative adversarial networks (GANs), as well as its application in compressing quantum circuits in practical uses.

We will review recent work on quantum Machine Learning with a focus on longer-term quantum algorithms. We will discuss challenges and prospects for such algorithms and ways of bringing them closer to practical solutions.

Elliptic curves play a prominent role in cryptography. For instance, the hardness of the elliptic curve discrete logarithm problem is a foundational assumption in public key cryptography. Drinfeld modules are positive characteristic function field analogues of elliptic curves. It is natural to ponder the existence/security of Drinfeld module analogues of elliptic curve cryptosystems. But the Drinfeld module discrete logarithm problem is easy even on a classical computer. Beyond discrete logarithms, elliptic curve isogeny based cryptosystems have have emerged as candidates for post-quantum cryptography, including supersingular isogeny Diffie-Hellman (SIDH) and commutative supersingular isogeny Diffie-Hellman (CSIDH) protocols. We formulate Drinfeld module analogues of these elliptic curve isogeny based cryptosystems and devise classical polynomial time algorithms to break these Drinfeld analogues catastrophically.  

The Hidden Subgroup Problem (HSP) aims at capturing all problems that are susceptible to be solvable in quantum polynomial time following the blueprints of Shor’s celebrated algorithm. Successful solutions to this problems over various commutative groups allow to efficiently perform number-theoretic tasks such as factoring or finding discrete logarithms. The latest successful generalization (Eisenträger et al. STOC 2014) considers the problem of finding a full-rank lattice as the hidden subgroup of the continuous vector space R^m , even for large dimensions m. It unlocked new cryptanalytic algorithms (Biasse-Song SODA 2016, Cramer et al. EUROCRYPT 2016 and 2017), in particular to find mildly short vectors in ideal lattices. The cryptanalytic relevance of such a problem raises the question of a more refined and quantitative complexity analysis. In the light of the increasing physical difficulty of maintaining a large entanglement of qubits, the degree of concern may be different whether the above algorithm requires only linearly many qubits or a much larger polynomial amount of qubits. This is the question we start addressing with this work. We propose a detailed analysis of (a variation of) the aforementioned HSP algorithm, and conclude on its complexity as a function of all the relevant parameters. Our modular analysis is tailored to support the optimization of future specialization to cases of cryptanalytic interests. We suggest a few ideas in this direction.

In this talk, we will first give an introduction on multivariate public key cryptography with the emphasis on the fundamental cryptanalysis tools. We will then discuss a new quantum attack algorithm developed by Gao etc against the multivariate schemes using the HHL quantum algorithm. The complexity of this algorithm depends on the so-called condition numbers.  The work of Gao etc  claims that there is a possibility such an algorithm is polynomial asymptotically. If it is indeed true, then we will have a quantum algorithm to solve a NP-complete problem in polynomial time. We will present a proof we developed recently that in general this new algorithm is actually exponential in terms of its complexity in solving a set of quadratic equations over a finite field. This second part  of the talk is a joint work with Vlad Gheorghiu from University of Waterloo.