Optimal Layout-Aware CNOT Circuit Synthesis with Qubit Permutation

• URL: http://arxiv.org/abs/2408.04349v1
• Date: Thu, 8 Aug 2024 10:20:13 GMT
• Title: Optimal Layout-Aware CNOT Circuit Synthesis with Qubit Permutation
• Authors: Irfansha Shaik, Jaco van de Pol,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: CNOT optimization plays a significant role in noise reduction for Quantum Circuits. Several heuristic and exact approaches exist for CNOT optimization. In this paper, we investigate more complicated variations of optimal synthesis by allowing qubit permutations and handling layout restrictions. We encode such problems into Planning, SAT, and QBF. We provide optimization for both CNOT gate count and circuit depth. For experimental evaluation, we consider standard T-gate optimized benchmarks and optimize CNOT sub-circuits. We show that allowing qubit permutations can further reduce up to 56% in CNOT count and 46% in circuit depth. In the case of optimally mapped circuits under layout restrictions, we observe a reduction up to 17% CNOT count and 19% CNOT depth.

Related papers

• HOPPS: Hardware-Aware Optimal Phase Polynomial Synthesis with Blockwise Optimization for Quantum Circuits [14.068472784717294]
  We introduce HOPPS: a hardware-aware optimal phase synthesis algorithm.<n>CNOT, Rz blocks with CNOT count or depth optimality could be generated.<n>For large QAOA circuit, after mapping by Qiskit, circuit can be reduced CNOT count and depth by up to 44.4% and 42.4%.
  arXiv  Detail & Related papers  (2025-11-24T05:07:32Z)
• Dynamic Depth Quantum Approximate Optimization Algorithm for Solving Constrained Shortest Path Problem [2.6276526932487276]
  We introduce a variant of QAOA called dynamic depth Quantum Approximate Optimization Algorithm (DDQAOA)<n>Our method adaptively expands circuit depth, starting from p = 1 and progressing up to p = 10, by transferring learned parameters to deeper circuits based on convergence criteria.<n>Our DDQAOA achieved superior approximation ratios and success probabilities with fewer CNOT gate evaluations than the standard QAOA for p = 3, 5, 10, and 15.
  arXiv  Detail & Related papers  (2025-11-11T15:05:14Z)
• Quantum Circuit Optimization Based on Dynamic Grouping and ZX-Calculus for Reducing 2-Qubit Gate Count [9.400669963756508]
  Two-qubit gates in quantum circuits are more susceptible to noise than single-qubit gates.<n>This paper proposes a quantum circuit optimization approach based on dynamic grouping and ZX-calculus.
  arXiv  Detail & Related papers  (2025-07-19T02:05:32Z)
• CNOT-Optimal Clifford Synthesis as SAT [0.0]
  Minimization of noisy gates, like 2-qubit CNOT gates, is crucial for practical computing. We propose an exhaustive search only on Clifford circuits in a certain normal form to guarantee CNOT count optimality. In experiments, our encodings significantly outperform existing SAT approaches on random Clifford circuits.
  arXiv  Detail & Related papers  (2025-04-01T10:35:58Z)
• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT circuits are a common building block of general quantum circuits. This article presents state-of-the-art algorithms for optimizing the number of CNOT gates. A simulated evaluation shows that the suggested is almost always beneficial and reduces the number of CNOT gates by up to 10%.
  arXiv  Detail & Related papers  (2024-08-07T19:51:22Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• 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 Circuit Optimization with AlphaTensor [47.9303833600197]
  We develop AlphaTensor-Quantum, a method to minimize the number of T gates that are needed to implement a given circuit. Unlike existing methods for T-count optimization, AlphaTensor-Quantum can incorporate domain-specific knowledge about quantum computation and leverage gadgets. Remarkably, it discovers an efficient algorithm akin to Karatsuba's method for multiplication in finite fields.
  arXiv  Detail & Related papers  (2024-02-22T09:20:54Z)
• Automatic Depth-Optimized Quantum Circuit Synthesis for Diagonal Unitary Matrices with Asymptotically Optimal Gate Count [9.194399933498323]
  It is of great importance to optimize the depth/gate-count when designing quantum circuits for specific tasks. In this paper, we propose a depth-optimized synthesis algorithm that automatically produces a quantum circuit for any given diagonal unitary matrix.
  arXiv  Detail & Related papers  (2022-12-02T06:58:26Z)
• Wide Quantum Circuit Optimization with Topology Aware Synthesis [0.8469686352132708]
  Unitary synthesis is an optimization technique that can achieve optimal multi-qubit gate counts while mapping quantum circuits to restrictive qubit topologies. We present TopAS, a topology aware synthesis tool built with the emphBQSKit framework that preconditions quantum circuits before mapping.
  arXiv  Detail & Related papers  (2022-06-27T21:59:30Z)
• Sketching the Best Approximate Quantum Compiling Problem [4.125187280299247]
  We solve the optimization problem classically and consider algorithmic tools to scale it to higher numbers of qubits. For all three algorithms, we compute the gradient efficiently using matrix-vector instead of matrix-matrix computations. Our implementation is able to compile 9 qubit, 27 CNOT circuits; 12 qubit, 24 CNOT circuits; and 15 qubit, 15 CNOT circuits.
  arXiv  Detail & Related papers  (2022-05-09T04:21:33Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  We introduce LAW, a new efficient batch acquisition method based on the determinantal point process. We provide a regret analysis for our method to gain insight in its theoretical properties. We evaluate the method on several standard problems involving permutations such as quadratic assignment.
  arXiv  Detail & Related papers  (2021-02-26T10:15:57Z)
• Relaxed Peephole Optimization: A Novel Compiler Optimization for Quantum Circuits [15.9208532173357]
  We propose a novel quantum compiler optimization, named relaxed peephole optimization (RPO) for quantum computers. We define a qubit is in a basis state when, at a given point in time, its state is either in the X-, Y-, or Z-basis. We extend our approach to optimize the quantum gates when some input qubits are in known pure states.
  arXiv  Detail & Related papers  (2020-12-14T17:03:06Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.