Quantum CNOT Circuits Synthesis for NISQ Architectures Using the Syndrome Decoding Problem

Timothée Goubault de Brugière (1, 2) , Marc Baboulin (3, 4) , Benoît Valiron (5, 6, 7) , Simon Martiel (8, 9) , Cyril Allouche (2)

1 ParSys - LRI - Systèmes parallèles (LRI)
2 Bull - Bull SAS
3 MDLS - Maison de la Simulation
4 ParSys - Systèmes Parallèles - LISN
5 CentraleSupélec
6 LMF - Laboratoire Méthodes Formelles
7 PI.R2 - Design, study and implementation of languages for proofs and programs
8 LSV - Laboratoire Spécification et Vérification [Cachan]
9 DEDUCTEAM - Deduction modulo, interopérabilité et démonstration automatique

Current proposals for quantum compilers involve the synthesis and optimization of linear reversible circuits and among them CNOT circuits. This class of circuits represents a significant part of the cost of running an entire quantum circuit and therefore we aim at reducing the size of CNOT circuits. In this paper we present a new algorithm for the synthesis of CNOT circuits based on the solution of the syndrome decoding problem. Our method addresses the case of ideal hardware with an all-to-all qubit connectivity and the case of near-term quantum devices with restricted connectivity. Benchmarks show that our algorithm outperforms existing algorithms in both cases of partial and full connectivity.

Mots clés: Quantum Circuit Synthesis; CNOT Circuits; Syndrome Decoding; Reversible Computation; Noisy Intermediate Scaled Quantum Computers (NISQ)

Domaines: Informatique [cs]

Timothée Goubault de Brugière, Marc Baboulin, Benoît Valiron, Simon Martiel, Cyril Allouche. Quantum CNOT Circuits Synthesis for NISQ Architectures Using the Syndrome Decoding Problem. Reversible Computation, Jul 2020, Oslo, Norway. ⟨10.1007/978-3-030-52482-1_11⟩. ⟨hal-04349410⟩