Daniel Vert, PhD

This paper experimentally investigates the behavior of analog quantum computers as commercialized by D-Wave when confronted to instances of the maximum cardinality matching problem which is specifically designed to be hard to solve by means of simulated annealing. We benchmark a D-Wave “Washington” (2X) with 1098 operational qubits on various sizes of such instances and observe that for all but the most trivially small of these it fails to obtain an optimal solution. Thus, our results suggest… Voir plus

This paper experimentally investigates the behavior of analog quantum computers as commercialized by D-Wave when confronted to instances of the maximum cardinality matching problem which is specifically designed to be hard to solve by means of simulated annealing. We benchmark a D-Wave “Washington” (2X) with 1098 operational qubits on various sizes of such instances and observe that for all but the most trivially small of these it fails to obtain an optimal solution. Thus, our results suggest that quantum annealing, at least as implemented in a D-Wave device, falls in the same pitfalls as simulated annealing and hence provides additional evidences suggesting that there exist polynomial-time problems that such a machine cannot solve efficiently to optimality. Additionally, we investigate the extent to which the qubits interconnection topologies explains these latter experimental results. In particular, we provide evidences that the sparsity of these topologies which, as such, lead to QUBO problems of artificially inflated sizes can partly explain the aforementioned disappointing observations. Therefore, this paper hints that denser interconnection topologies are necessary to unleash the potential of the quantum annealing approach. Voir moins

Recent experimental works have studied how the quantum annealing approach, as implemented in D-Wave devices, deals with pathological instances of the (polynomial) bipartite matching problem known to be hard for classical simulated annealing algorithms and shown that the quantum approach also performed rather poorly on such instances. In this paper, we investigate the extent to which the qubits interconnection topologies explains these latter experimental results. In particular, we provide… Voir plus

Recent experimental works have studied how the quantum annealing approach, as implemented in D-Wave devices, deals with pathological instances of the (polynomial) bipartite matching problem known to be hard for classical simulated annealing algorithms and shown that the quantum approach also performed rather poorly on such instances. In this paper, we investigate the extent to which the qubits interconnection topologies explains these latter experimental results. In particular, we provide evidences that the sparsity of these topologies which, as such, lead to QUBO problems of artificially inflated sizes can partly explain the aforementioned disappointing observations. Therefore, this paper hints that denser interconnection topologies are necessary to unleash the potential of the quantum annealing approach. Voir moins

This paper experimentally investigates the behavior of analog quantum computers such as commercialized by D-Wave when confronted to instances of the maximum cardinality matching problem specifically designed to be hard to solve by means of simulated annealing. We benchmark a D-Wave “Washington” (2X) with 1098 operational qubits on various sizes of such instances and observe that for all but the most trivially small of these it fails to obtain an optimal solution. Thus, our results suggest that… Voir plus

This paper experimentally investigates the behavior of analog quantum computers such as commercialized by D-Wave when confronted to instances of the maximum cardinality matching problem specifically designed to be hard to solve by means of simulated annealing. We benchmark a D-Wave “Washington” (2X) with 1098 operational qubits on various sizes of such instances and observe that for all but the most trivially small of these it fails to obtain an optimal solution. Thus, our results suggest that quantum annealing, at least as implemented in a D-Wave device, falls in the same pitfalls as simulated annealing and therefore provides additional evidences suggesting that there exist polynomial-time problems that such a machine cannot solve efficiently to optimality. Voir moins

This paper experimentally investigates the behavior of analog quantum computers such as commercialized by D-Wave when confronted to instances of the maximum cardinality matching problem specifically designed to be hard to solve by means of simulated annealing. We benchmark a D-Wave “Washington” (2X) with 1098 operational qubits on various sizes of such instances and observe that for all but the most trivially small of these it fails to obtain an optimal solution. Thus, our results suggests… Voir plus

This paper experimentally investigates the behavior of analog quantum computers such as commercialized by D-Wave when confronted to instances of the maximum cardinality matching problem specifically designed to be hard to solve by means of simulated annealing. We benchmark a D-Wave “Washington” (2X) with 1098 operational qubits on various sizes of such instances and observe that for all but the most trivially small of these it fails to obtain an optimal solution. Thus, our results suggests that quantum annealing, at least as implemented in a D-Wave device, falls in the same pitfalls as simulated annealing and therefore suggest that there exist polynomial-time problems that such a machine cannot solve efficiently to optimality. Voir moins

This paper investigates the possibility of using an analog quantum computer as commercialized by D-Wave to solve large QUBO problems by means of a single invocation of the quantum annealer. Indeed this machine solves a spin glass problem with programmable coefficients but subject to quite strong topology restrictions on the set of non-zero coefficients. Rather than mapping problem variables onto multiple qbits, an approach which requires many invocations of the annealer to solve small size… Voir plus

This paper investigates the possibility of using an analog quantum computer as commercialized by D-Wave to solve large QUBO problems by means of a single invocation of the quantum annealer. Indeed this machine solves a spin glass problem with programmable coefficients but subject to quite strong topology restrictions on the set of non-zero coefficients. Rather than mapping problem variables onto multiple qbits, an approach which requires many invocations of the annealer to solve small size problems, it is tempting to investigate the existence of sparse relaxations compliant with the qbits interconnection topology of the machine, hence solvable in one invocation of the annealing oracle, but still providing good-quality solutions to the original problem. This paper provides an experimental setup which aims to determine whether or not such convenient relaxations do exist or, rather, are easy to find. Our experiments suggest that it is not the case and, therefore, that solving even moderate size arbitrary problems with a single call to a quantum annealer is not possible at least within the constraints of the so-called Chimera topology. We conclude the paper with a number of perspectives that this results imply on the design of heuristics taking profit of a quantum annealing oracle to solve large scale problems. Voir moins

Sur le plan pratique, l’émergence à moyen terme d’ordinateurs quantiques capables de rivaliser, pour la résolution de certains problèmes, avec les performances des calculateurs classiques les plus puissants reste hautement spéculative. En effet, et bien qu’il soit tout à fait pertinent d’investiguer les conséquences de l’existence de telles machines dans différents domaines applicatifs, les réalisations actuelles que l’on peut apparenter à des ordinateurs quantiques, bien qu’impressionnantes… Voir plus

Sur le plan pratique, l’émergence à moyen terme d’ordinateurs quantiques capables de rivaliser, pour la résolution de certains problèmes, avec les performances des calculateurs classiques les plus puissants reste hautement spéculative. En effet, et bien qu’il soit tout à fait pertinent d’investiguer les conséquences de l’existence de telles machines dans différents domaines applicatifs, les réalisations actuelles que l’on peut apparenter à des ordinateurs quantiques, bien qu’impressionnantes sur le plan de la physique, restent très modestes sur le plan informatique. Ces remarques concernent néanmoins ce qu’il convient d’appeler aujourd’hui l’ordinateur quantique numérique, c’est-à-dire composé de portes logiques quantiques s’appliquant sur des qbits. Cette voie n’est néanmoins pas la seule, afin de mettre à profit les propriétés quantiques de la nature pour le traitement de l’information. Ces dernières années, sont apparues des machines quantiques dites analogiques, dont les calculateurs actuellement commercialisés par la société canadienne D-Wave sont les premiers représentants, fonctionnant selon un principe de recuit à accélération quantique.. Ces machines ont l’avantage d’exister à une échelle non triviale et le chemin technologique en vue de leur passage à l’échelle est beaucoup moins flou que celui de leurs cousins numériques. Dans ce contexte, nous cherchons des chemins de transformations polynomiales permettant aussi efficacement que possible de ramener des problèmes d’optimisation vers le type de problème traité par ces machines. Voir moins