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)