Polynomial transformations towards operating analog quantum computers
Published : 24 April 2017
Over the last few years, a new breed of machines have appeared in the quantum computing landscape, the so-called analog quantum computers of which the machines presently sold by the Canadian company D-Wave are the first instances. From an abstract point of view, such a machine may be seen as an oracle specialized in the resolution of an NP-hard optimization problem (of the spin-glass type) with an algorithm analogous to the well-known simulated annealing but with a quantum speedup (the precise characterization of which still being an open question). If the theory of quantum annealing is now relatively well understood by the physics community, the extent to which D-Wave machines implements it properly is still the subject of some controversy within that community. Still, quantum annealing machines do exists today at a non-trivial scale (between 500 and 1000 bits of internal state) and their technological path towards larger scales is much clearer than for their digital cousins. Furthermore, it is presently considered that a quantum annealing machines with an internal state between 6 to 10 kbits would be competitive with the most powerful classical computers for solving optimization problems. In this context, the present thesis aims at investigating polynomial transformation paths from some NP problems (not necessarily NP-hard and which selection will be done as part of the thesis work) towards the reference problem of the annealing machine. Thus, the main objective of this thesis is to develop a better understanding of the theoretical performances of these machines, as well as a first return on experience if access to a D-Wave machine (via an institution owning such a machine) is possible. Depending on the candidate profile, the subject will bend more towards either physical aspects, computational complexity theory aspects or more applicative aspects (operations research, cryptanalysis notably).