Quantum mean value problem is the task of estimating the expected value of a tensor product observable
on the output state of a quantum circuit. This task is a common step of NISQ era quantum algorithms such as VQE or QAOA. I will consider the complexity of the quantum mean value problem as a function of circuit depth, qubit connectivity, and the structure of observables to be measured. Polynomial-time classical algorithms are described solving the quantum mean value problem in two special cases:
(a) 2D constant-depth variational circuits relevant for VQE,
(b) level-1 and level-2 QAOA circuits associated with graph-based optimization problems.
As an application, I will describe a classical simulation of the recently proposed Recursive QAOA
algorithm applied to graph coloring problems.
Based on
arXiv:1909.11485
arXiv:1910.08980
Theory shows that arbitrary-sized quantum computers may offer computational advantages for many problems. However, quantum computers on a reasonable horizon will be restricted in many ways, including size. Motivated by this, we investigate how a smaller quantum computer can genuinely speed up interesting algorithms, even when the problem size is much larger than the computer itself.
To do so, we study hybrid classical-quantum divide-and-conquer strategies, and prove that if certain conditions on the structure and complexities of the underlying classical and quantum algorithms are met, then genuine speed-ups can be obtained.
We will demonstrate how these conditions are met for a few exact constraint satisfaction algorithms (for SAT and Hamilton cycles). In closing we will discuss some of the more recent ideas showing how the hybrid methods can be expanded to the heuristic domain, and (hopefully) achieve practically relevant speed-ups in optimization with near-term devices.
This talk will be based on the following papers:
-VD, Y. Ge, J. I. Cirac, Computational speedups using small quantum devices, Phys. Rev. Lett. 121, 250501 (2018);
-Y. Ge, VD, A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles, J. Math. Phys. 61, 012201 (2020);
-C. Moussa, H. Calandra, VD, To quantum or not to quantum: towards algorithm selection in near-term quantum optimization, arXiv:2001.08271 (2020);
Local Hamiltonians with topological quantum order exhibit highly entangled ground states that cannot be prepared by shallow quantum circuits. Here, we show that this property may extend to all low-energy states in the presence of an on-site Z2 symmetry. This proves a version of the No Low-Energy Trivial States (NLTS) conjecture for a family of local Hamiltonians with symmetry protected topological order. A surprising consequence of this result is that the Goemans-Williamson algorithm outperforms the Quantum Approximate Optimization Algorithm (QAOA) for certain instances of MaxCut, at any constant level. We argue that the locality and symmetry of QAOA severely limits its performance. To overcome these limitations, we propose a non-local version of QAOA, and give numerical evidence that it significantly outperforms standard QAOA for frustrated Ising models on random 3-regular graphs.
This is joint work with Sergey Bravyi, Alexander Kliesch and Eugene Tang.
Since the first observation 20 years ago of first coherent quantum behaviour in a superconducting qubit there have been significant developments in the field of superconducting quantum circuits. With improvements of coherence times by over 5 orders of magnitude, it is now possible to execute increasingly complex quantum algorithms with these circuits. Despite these successes, the coherence time of superconducting devices must still be increased for quantum computation to become a reality. One approach is to improve existing devices. Another approach is to design new superconducting qubits with intrinsic protection against certain types of errors. In this talk, I will discuss how quantum information can be robustly encoded in cat states of the electromagnetic field stored in superconducting quantum devices. A feature of this encoding is that it exhibits biased noise. I will present how to realize bias-preserving gates on this qubit, and how these ideas can be further improved with quantum error correction.
Hardware of quantum computers is limited in qubit count, fidelity, and connectivity now and for the near future. In order to gain maximum advantage from these machines, it is imperative to use these resources in an optimal and efficient way. I will present the example of the SPARQS co-design geared at simulating small clusters of the Fermi Hubbard model at finite nonzero temperature [1], that saves the experimenter the need of intersecting wires and three-dimensional chip integration. I will also show a new example of a co-design of the QAOA-algorithm that permits to avoid programmable interactions [2]. I will finally muse about the fluidity of the line between modern closed-loop gate design and modern variational algorithms, suggesting time-continuous strategies for state preparation [3].
[1] Pierre-Luc Dallaire-Demers and Frank K. Wilhelm, Phys. Rev. A 94, 062304, 2016
[2] David Headley, Thorge Müller, Ana Martin, Enrique Solano, Mikel Sanz, Frank K. Wilhelm, arXiv:2002.12215
[3] Shai Machnes, Nicolas Wittler, Federico Roy, Kevin Pack, Anurag Sasha-Roy, and Frank K. Wilhelm, methodology for Control, Calibration and Characterization of quantum devices,applied to superconducting qubits, in preparation
We examine questions in game theory and online learning from a dynamical systems perspective. Specifically, the goal of the tutorial is to establish links between typically distinct tools such as optimization theory (regret analysis), chaos theory, topology of dynamical systems and more traditional game theoretic ideas such as different classes of equilibria and Price of Anarchy. We will use these connections to elucidate recent results in the area as well as pose open questions.
Classically, the outcome of a learning algorithm is considered in isolation from the effects that it may have on the process that generates the data or the party who is interested in learning. In today's world, increasingly more people and organizations interact with learning systems, making it necessary to consider these effects. This tutorial will cover the mathematical foundation for addressing learning and learnability in the presence of economic and social forces.
We will cover recent advances in the theory of machine learning and algorithmic economics. In the first half of this tutorial, we will consider strategic and adversarial interactions between learning algorithms and those affected by algorithmic actions. What makes these interactions especially powerful is that they often occur over a long-term basis and can corrupt data patterns that are essential for machine learning. In this part of the talk, we work with online decision processes (such as no-regret learning) and solution concepts (such as stackelberg and minmax equilibria) to discuss statistical and computational aspects of learning and learnability in the presence of such interactions. In the second half of the tutorial, we will consider collaborative interactions in machine learning. What makes these interactions especially beneficial is their ability to learn across multiple stakeholders' tasks. In this part of the talk, we see how online algorithms act as a medium for effective collaborations. We also discuss challenges involved in designing efficient data sharing mechanisms that fully account for learner's incentives.
Classically, the outcome of a learning algorithm is considered in isolation from the effects that it may have on the process that generates the data or the party who is interested in learning. In today's world, increasingly more people and organizations interact with learning systems, making it necessary to consider these effects. This tutorial will cover the mathematical foundation for addressing learning and learnability in the presence of economic and social forces.
We will cover recent advances in the theory of machine learning and algorithmic economics. In the first half of this tutorial, we will consider strategic and adversarial interactions between learning algorithms and those affected by algorithmic actions. What makes these interactions especially powerful is that they often occur over a long-term basis and can corrupt data patterns that are essential for machine learning. In this part of the talk, we work with online decision processes (such as no-regret learning) and solution concepts (such as stackelberg and minmax equilibria) to discuss statistical and computational aspects of learning and learnability in the presence of such interactions. In the second half of the tutorial, we will consider collaborative interactions in machine learning. What makes these interactions especially beneficial is their ability to learn across multiple stakeholders' tasks. In this part of the talk, we see how online algorithms act as a medium for effective collaborations. We also discuss challenges involved in designing efficient data sharing mechanisms that fully account for learner's incentives.
This short course will review recent advances in econometric theory for datasets that stem from the strategic interaction of participants in a game theoretic scenario. The course will cover basics of identification and estimation strategies for structural parameters of game theoretic models in settings like market entry games, dynamic games and auctions. In the first part, I will review basic econometric theory and in particular large sample asymptotic theory of generalized method of moment estimators and M-estimators, which forms the basis of many estimation and identification strategies proposed for game theoretic settings. I will then give an application of this theory to entry games of incomplete information. I will finish with an overview of how this approach extends to dynamic games of incomplete information. In the second part, I will analyze games of complete information and focus on the problem arising from the multiplicity of equilibria in these games, due to the unobserved heterogeneity of the participants. The latter leads to partial identification of the parameters of interest and set estimation. Finally, I will focus on econometrics of auction games and in particular estimation of the private value distribution in simple single item auctions. I will finish with a brief description of recent progress at the intersection of algorithmic game theory and econometrics.
This short course will review recent advances in econometric theory for datasets that stem from the strategic interaction of participants in a game theoretic scenario. The course will cover basics of identification and estimation strategies for structural parameters of game theoretic models in settings like market entry games, dynamic games and auctions. In the first part, I will review basic econometric theory and in particular large sample asymptotic theory of generalized method of moment estimators and M-estimators, which forms the basis of many estimation and identification strategies proposed for game theoretic settings. I will then give an application of this theory to entry games of incomplete information. I will finish with an overview of how this approach extends to dynamic games of incomplete information. In the second part, I will analyze games of complete information and focus on the problem arising from the multiplicity of equilibria in these games, due to the unobserved heterogeneity of the participants. The latter leads to partial identification of the parameters of interest and set estimation. Finally, I will focus on econometrics of auction games and in particular estimation of the private value distribution in simple single item auctions. I will finish with a brief description of recent progress at the intersection of algorithmic game theory and econometrics.