Speaker
Description
Quantum computers promise a framework to efficiently tackle problems that are intractable even to modern day supercomputers. This new type of computers harnesses properties of quantum of quantum physics, like access to a bigger computational space (thanks to the Hilbert space used to describe quantum phenomena), quantum entanglement and interference. These provide na unprecedented level of parallelism and the ability to tackle problems whose computational complexity is beyond the reach of any classical computer.
Quantum computers based on the ‘Quantum circuit model’ are considered the most viable hosts for universal quantum computation. However, in general, quantum algorithms (in the form of quantum circuits) usually assume complete connectivity between the qubits, and don’t take into account the engineering limitations of the diferente implementations: usually qubits are connected in a Nearest Neighbors (NN) fashion, which means that each qubit is only connected with a limited number of adjacente qubits. Performing quantum algorithms requires then the emulation of a complete graph of connectivity between the ‘virtual qubits’ in the Nearest Neighbor connected graphs in usual implementations.
Such a transformation is called the Qubit Mapping problem. Such a problem is known to be NP-complete, and new tecniques are required to tackle this problema in a scalable way, while providing high-quality mapping, with minimum overhead. Reducing this overhead is especially importante in near-future quantum devices, since imperfect quantum gates and limited coherence time of qubits prevents too long (time-wise) and big (envolving a large number of gates) circuits to be simulated without errors.
