Abstract

The actual implementation of quantum computing devices is however hindered by many challenging difficulties, the most prominent of which being the control or removal of quantum decoherence [4]. Recent promising experimental research findings [5–7] in the field of Adiabatic Quantum Computing (AQC) suggest that a leading candidate to be the first device to solve practical classically-hard problems using quantum principles is the so called ‘quantum annealer’, which implements the simple yet potentially-powerful quantum-adiabatic algorithmic approach proposed by Farhi et al.[8] about a decade ago. The aforementioned experimental studies, as well as other theoretical work such as the theorem of polynomial equivalence between AQC and the predominant gate model (GM) paradigm of quantum computing [9, 10], provide ample motivation for determining the computational capabilities of AQC and its precise relations with other quantum computing paradigms, specifically GM. Demonstrating that algorithms such as Shor’s integer factorization [1] are implementable as efficiently on a quantum adiabatic computer would undoubtedly have many practical as well as theoretical consequences that would resonate well beyond Quantum Computing.
Recent studies [11–14] examining the performance of certain AQC algorithms, such as Unstructured Database Search [11], Quantum Counting [12] and Simon’s problem [13], against their GM counterparts, suggest that the equivalence between AQC and GM is stronger than the one implied by the principles of polynomial equivalence prescribed in the seminal study of Aharonov et al.[9, 15].

Date

2014

Authors

Itay Hen

Journal

arXiv preprint arXiv:1401.5172