Qubit Allocation for Distributed Quantum Computing

With the advancements in quantum communication, optically connected quantum processors can form a distributed quantum computing system. Distributed quantum computing provides a scalable path to execute more complicated computational tasks that a single quantum processor cannot handle. Yet, distributed quantum computing needs a new compiler to map logical qubits of a quantum circuit to different quantum processors in the system. This paper formulates and studies the qubit allocation problem for distributed quantum computing (QA-DQC). We prove the NP-hardness of the formulated problem. Moreover, we show there is no polynomial-time n^a-approximation algorithm for any a < 1 unless P = NP, where n is the number of processors in the quantum network. We first propose a heuristic local search algorithm for QA-DQC. Furthermore, we design a multistage hybrid simulated annealing algorithm (MHSA) by combining the local search algorithm and a simulated annealing meta-heuristic algorithm. Lastly, we perform extensive simulations to evaluate the proposed MHSA under various real quantum circuits and different network topologies. Results show that MHSA outperforms popular baselines.