qubit mapping

Quantum mapping, aka quantum circuit transformation (QCT), is the process of transforming an ideal quantum (logical) circuit LC = (Q, C) to a (physical) circuit PC that is executable on a near-term quantum device with architectural graph AG = (V,E) such that

LC and PC are functional equivalent
Every gate in PC is supported by the quantum device
Every two-qubit gate in PC acts on two connected qubits

The target of qubit mapping is to construct such a PC with minimal gate or depth overhead. See our Publications

Construct an initial mapping

The first step of qubit mapping is to construct an initial mapping, which assigns to each logical qubit p in LC a physical qubit v in AG. We propose two methods for constructing such an initial mapping:

simulated annealing (in SAHS)
subgraph isomporphism (in FiDLS)

Starting from LC, we construct a graph with node set Q and connect two nodes if there is a CNOT between them. Using the vf2 algorithm, we give two methods for constructing initial mappings that can embed a maximal front subgraph or a maximal (in a sense) weighted subgraph of G to AG.

AI Search

Starting from an initial mapping, we search step by step the best action which can execute gates in LC. Some techniques we've exploited include:

Look-ahead and select the action associated to the child state with the best grandchild state (SAHS)
Execute gates greedily, search all actions with up to k SWAPs and use filters to exclude less promising actions earlier (FiDLS)
Develop Monte Carlo Tree Search style search algorithms to go deeper in search (MCTS)

Page updated

Google Sites

Report abuse