CNOT-Optimal Clifford Synthesis as SAT

• URL: http://arxiv.org/abs/2504.00634v1
• Date: Tue, 01 Apr 2025 10:35:58 GMT
• Title: CNOT-Optimal Clifford Synthesis as SAT
• Authors: Irfansha Shaik, Jaco van de Pol,
• Abstract summary: Minimization of noisy gates, like 2-qubit CNOT gates, is crucial for practical computing.<n>We propose an exhaustive search only on Clifford circuits in a certain normal form to guarantee CNOT count optimality.<n>In experiments, our encodings significantly outperform existing SAT approaches on random Clifford circuits.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Clifford circuit optimization is an important step in the quantum compilation pipeline. Major compilers employ heuristic approaches. While they are fast, their results are often suboptimal. Minimization of noisy gates, like 2-qubit CNOT gates, is crucial for practical computing. Exact approaches have been proposed to fill the gap left by heuristic approaches. Among these are SAT based approaches that optimize gate count or depth, but they suffer from scalability issues. Further, they do not guarantee optimality on more important metrics like CNOT count or CNOT depth. A recent work proposed an exhaustive search only on Clifford circuits in a certain normal form to guarantee CNOT count optimality. But an exhaustive approach cannot scale beyond 6 qubits. In this paper, we incorporate search restricted to Clifford normal forms in a SAT encoding to guarantee CNOT count optimality. By allowing parallel plans, we propose a second SAT encoding that optimizes CNOT depth. By taking advantage of flexibility in SAT based approaches, we also handle connectivity restrictions in hardware platforms, and allow for qubit relabeling. We have implemented the above encodings and variations in our open source tool Q-Synth. In experiments, our encodings significantly outperform existing SAT approaches on random Clifford circuits. We consider practical VQE and Feynman benchmarks to compare with TKET and Qiskit compilers. In all-to-all connectivity, we observe reductions up to 32.1% in CNOT count and 48.1% in CNOT depth. Overall, we observe better results than TKET in the CNOT count and depth. We also experiment with connectivity restrictions of major quantum platforms. Compared to Qiskit, we observe up to 30.3% CNOT count and 35.9% CNOT depth further reduction.

Related papers

• DeepPrune: Parallel Scaling without Inter-trace Redundancy [53.62015294143274]
  Over 80% of parallel reasoning traces yield identical final answers, representing substantial wasted computation.<n>We propose DeepPrune, a novel framework that enables efficient parallel scaling through dynamic pruning.<n>Our work establishes a new standard for efficient parallel reasoning, making high-performance reasoning more efficient.
  arXiv  Detail & Related papers  (2025-10-09T17:24:54Z)
• Heuristic and Optimal Synthesis of CNOT and Clifford Circuits [3.1952340441132474]
  Linear reversible circuits, equivalent to circuits composed of CNOT gates, have important applications in classical computing.<n>We present methods for CNOT and general Clifford circuit synthesis which can be used to minimise either the entangling two-qubit gate count or the circuit depth.<n>The algorithms have been implemented in a GitHub repository for use by the classical and quantum computing community.
  arXiv  Detail & Related papers  (2025-03-18T19:09:58Z)
• Empirical Evaluation of the Implicit Hitting Set Approach for Weighted CSPs [46.010796136659536]
  We explore some alternatives to the existing algorithm of reference for the weighted CSP problem.<n>Our empirical study shows that for WCSP it is not easy to identify the best alternative.
  arXiv  Detail & Related papers  (2025-01-13T15:59:28Z)
• Optimal Layout-Aware CNOT Circuit Synthesis with Qubit Permutation [0.0]
  CNOT optimization plays a significant role in noise reduction for Quantum Circuits. We provide optimization for both CNOT gate count and circuit depth. We show that allowing qubit permutations can further reduce up to 56% in CNOT count and 46% in circuit depth.
  arXiv  Detail & Related papers  (2024-08-08T10:20:13Z)
• Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits [0.0]
  scalable layout synthesis is of utmost importance for NISQ processors. We propose a SAT encoding based on parallel plans that apply 1 SWAP and a group of CNOTs at each time step. For the first time, we can optimally map several 8, 14, and 16 qubit circuits onto 54, 80, and 127 qubit platforms with up to 17 SWAPs.
  arXiv  Detail & Related papers  (2024-03-18T09:19:01Z)
• Quantum State Preparation Using an Exact CNOT Synthesis Formulation [8.078625517374967]
  Minimizing the use of CNOT gates in quantum state preparation is a crucial step in quantum compilation. We propose an effective state preparation algorithm using an exact CNOT synthesis formulation.
  arXiv  Detail & Related papers  (2024-01-02T03:37:00Z)
• Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
  We show that the hardness of SAT encodings for LEC instances can be estimated textitw.r.t some SAT partitioning. The paper proposes several methods for constructing partitionings, which, when used in practice, allow one to estimate the hardness of SAT encodings for LEC with good accuracy.
  arXiv  Detail & Related papers  (2022-10-04T09:19:13Z)
• A SAT Encoding for Optimal Clifford Circuit Synthesis [3.610459670994051]
  We consider the optimal synthesis of Clifford circuits -- an important subclass of quantum circuits. We propose an optimal synthesis method for Clifford circuits based on encoding the task as a satisfiability problem. The resulting tool is demonstrated to synthesize optimal circuits for up to $26$ qubits.
  arXiv  Detail & Related papers  (2022-08-24T18:00:03Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• AQD: Towards Accurate Fully-Quantized Object Detection [94.06347866374927]
  We propose an Accurate Quantized object Detection solution, termed AQD, to get rid of floating-point computation. Our AQD achieves comparable or even better performance compared with the full-precision counterpart under extremely low-bit schemes.
  arXiv  Detail & Related papers  (2020-07-14T09:07:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.