-
Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization
Authors:
Masoud Mohseni,
Daniel Eppens,
Johan Strumpfer,
Raffaele Marino,
Vasil Denchev,
Alan K. Ho,
Sergei V. Isakov,
Sergio Boixo,
Federico Ricci-Tersenghi,
Hartmut Neven
Abstract:
Optimizing highly complex cost/energy functions over discrete variables is at the heart of many open problems across different scientific disciplines and industries. A major obstacle is the emergence of many-body effects among certain subsets of variables in hard instances leading to critical slowing down or collective freezing for known stochastic local search strategies. An exponential computati…
▽ More
Optimizing highly complex cost/energy functions over discrete variables is at the heart of many open problems across different scientific disciplines and industries. A major obstacle is the emergence of many-body effects among certain subsets of variables in hard instances leading to critical slowing down or collective freezing for known stochastic local search strategies. An exponential computational effort is generally required to unfreeze such variables and explore other unseen regions of the configuration space. Here, we introduce a quantum-inspired family of nonlocal Nonequilibrium Monte Carlo (NMC) algorithms by developing an adaptive gradient-free strategy that can efficiently learn key instance-wise geometrical features of the cost function. That information is employed on-the-fly to construct spatially inhomogeneous thermal fluctuations for collectively unfreezing variables at various length scales, circumventing costly exploration versus exploitation trade-offs. We apply our algorithm to two of the most challenging combinatorial optimization problems: random k-satisfiability (k-SAT) near the computational phase transitions and Quadratic Assignment Problems (QAP). We observe significant speedup and robustness over both specialized deterministic solvers and generic stochastic solvers. In particular, for 90% of random 4-SAT instances we find solutions that are inaccessible for the best specialized deterministic algorithm known as Survey Propagation (SP) with an order of magnitude improvement in the quality of solutions for the hardest 10% instances. We also demonstrate two orders of magnitude improvement in time-to-solution over the state-of-the-art generic stochastic solver known as Adaptive Parallel Tempering (APT).
△ Less
Submitted 26 November, 2021;
originally announced November 2021.
-
Simulations of Quantum Circuits with Approximate Noise using qsim and Cirq
Authors:
Sergei V. Isakov,
Dvir Kafri,
Orion Martin,
Catherine Vollgraff Heidweiller,
Wojciech Mruczkiewicz,
Matthew P. Harrigan,
Nicholas C. Rubin,
Ross Thomson,
Michael Broughton,
Kevin Kissell,
Evan Peters,
Erik Gustafson,
Andy C. Y. Li,
Henry Lamm,
Gabriel Perdue,
Alan K. Ho,
Doug Strain,
Sergio Boixo
Abstract:
We introduce multinode quantum trajectory simulations with qsim, an open source high performance simulator of quantum circuits. qsim can be used as a backend of Cirq, a Python software library for writing quantum circuits. We present a novel delayed inner product algorithm for quantum trajectories which can result in an order of magnitude speedup for low noise simulation. We also provide tools to…
▽ More
We introduce multinode quantum trajectory simulations with qsim, an open source high performance simulator of quantum circuits. qsim can be used as a backend of Cirq, a Python software library for writing quantum circuits. We present a novel delayed inner product algorithm for quantum trajectories which can result in an order of magnitude speedup for low noise simulation. We also provide tools to use this framework in Google Cloud Platform, with high performance virtual machines in a single mode or multinode setting. Multinode configurations are well suited to simulate noisy quantum circuits with quantum trajectories. Finally, we introduce an approximate noise model for Google's experimental quantum computing platform and compare the results of noisy simulations with experiments for several quantum algorithms on Google's Quantum Computing Service.
△ Less
Submitted 3 November, 2021;
originally announced November 2021.
-
Generative latent neural models for automatic word alignment
Authors:
Anh Khoa Ngo Ho,
François Yvon
Abstract:
Word alignments identify translational correspondences between words in a parallel sentence pair and are used, for instance, to learn bilingual dictionaries, to train statistical machine translation systems or to perform quality estimation. Variational autoencoders have been recently used in various of natural language processing to learn in an unsupervised way latent representations that are usef…
▽ More
Word alignments identify translational correspondences between words in a parallel sentence pair and are used, for instance, to learn bilingual dictionaries, to train statistical machine translation systems or to perform quality estimation. Variational autoencoders have been recently used in various of natural language processing to learn in an unsupervised way latent representations that are useful for language generation tasks. In this paper, we study these models for the task of word alignment and propose and assess several evolutions of a vanilla variational autoencoders. We demonstrate that these techniques can yield competitive results as compared to Giza++ and to a strong neural network alignment system for two language pairs.
△ Less
Submitted 28 September, 2020;
originally announced September 2020.
-
Neural Baselines for Word Alignment
Authors:
Anh Khoa Ngo Ho,
François Yvon
Abstract:
Word alignments identify translational correspondences between words in a parallel sentence pair and is used, for instance, to learn bilingual dictionaries, to train statistical machine translation systems , or to perform quality estimation. In most areas of natural language processing, neural network models nowadays constitute the preferred approach, a situation that might also apply to word alig…
▽ More
Word alignments identify translational correspondences between words in a parallel sentence pair and is used, for instance, to learn bilingual dictionaries, to train statistical machine translation systems , or to perform quality estimation. In most areas of natural language processing, neural network models nowadays constitute the preferred approach, a situation that might also apply to word alignment models. In this work, we study and comprehensively evaluate neural models for unsupervised word alignment for four language pairs, contrasting several variants of neural models. We show that in most settings, neural versions of the IBM-1 and hidden Markov models vastly outperform their discrete counterparts. We also analyze typical alignment errors of the baselines that our models overcome to illustrate the benefits-and the limitations-of these new models for morphologically rich languages.
△ Less
Submitted 28 September, 2020;
originally announced September 2020.
-
TensorFlow Quantum: A Software Framework for Quantum Machine Learning
Authors:
Michael Broughton,
Guillaume Verdon,
Trevor McCourt,
Antonio J. Martinez,
Jae Hyeon Yoo,
Sergei V. Isakov,
Philip Massey,
Ramin Halavati,
Murphy Yuezhen Niu,
Alexander Zlokapa,
Evan Peters,
Owen Lockwood,
Andrea Skolik,
Sofiene Jerbi,
Vedran Dunjko,
Martin Leib,
Michael Streif,
David Von Dollen,
Hongxiang Chen,
Shuxiang Cao,
Roeland Wiersema,
Hsin-Yuan Huang,
Jarrod R. McClean,
Ryan Babbush,
Sergio Boixo
, et al. (4 additional authors not shown)
Abstract:
We introduce TensorFlow Quantum (TFQ), an open source library for the rapid prototyping of hybrid quantum-classical models for classical or quantum data. This framework offers high-level abstractions for the design and training of both discriminative and generative quantum models under TensorFlow and supports high-performance quantum circuit simulators. We provide an overview of the software archi…
▽ More
We introduce TensorFlow Quantum (TFQ), an open source library for the rapid prototyping of hybrid quantum-classical models for classical or quantum data. This framework offers high-level abstractions for the design and training of both discriminative and generative quantum models under TensorFlow and supports high-performance quantum circuit simulators. We provide an overview of the software architecture and building blocks through several examples and review the theory of hybrid quantum-classical neural networks. We illustrate TFQ functionalities via several basic applications including supervised learning for quantum classification, quantum control, simulating noisy quantum circuits, and quantum approximate optimization. Moreover, we demonstrate how one can apply TFQ to tackle advanced quantum learning tasks including meta-learning, layerwise learning, Hamiltonian learning, sampling thermal states, variational quantum eigensolvers, classification of quantum phase transitions, generative adversarial networks, and reinforcement learning. We hope this framework provides the necessary tools for the quantum computing and machine learning research communities to explore models of both natural and artificial quantum systems, and ultimately discover new quantum algorithms which could potentially yield a quantum advantage.
△ Less
Submitted 26 August, 2021; v1 submitted 5 March, 2020;
originally announced March 2020.
