Size optimization of CNOT circuits on NISQ

• URL: http://arxiv.org/abs/2210.05184v1
• Date: Tue, 11 Oct 2022 06:44:04 GMT
• Title: Size optimization of CNOT circuits on NISQ
• Authors: Anpeng Zhang, Xiutao Feng and Shengyuan Xu
• Abstract summary: We study the optimization of the CNOT circuits on some noisy intermediate-scale quantum(NISQ) devices. We implement our algorithm on IBM20 and some other NISQ devices, the results are better than most other methods in our experiment.
• Score: 13.391818915679796
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum computers in practice today require strict memory constraints, where 2-qubit operations can only be performed between the qubits closest to each other in a graph structure. So a quantum circuit must undergo a transformation to the graph before it can be implemented. In this paper, we study the optimization of the CNOT circuits on some noisy intermediate-scale quantum(NISQ) devices. Compared with previous works, we decompose it into two sub-problems: optimization with a given initial qubit distribution and optimization without limitations of initial qubit distribution. We find that most of the previous researches focused on the first sub-problem, and ignored the influence of different distribution of qubits in the same topology structure on the optimization results. In this paper, We take both sub-problems into account and give some new optimization algorithms. In short, our method is divided into two steps: matrix optimization and routing optimization. We implement matrix optimization with the algorithm in [XZL+20] and put forward a new heuristic algorithm with MILP method which can solve the second step. We implement our algorithm on IBM20 and some other NISQ devices, the results are better than most other methods in our experiment.

Related papers

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  gradient-based algorithms are widely used in bilevel optimization. We introduce a without-replacement sampling based algorithm which achieves a faster convergence rate. We validate our algorithms over both synthetic and real-world applications.
  arXiv  Detail & Related papers  (2024-11-07T17:05:31Z)
• A Pure Quantum Approximate Optimization Algorithm Based on CNR Operation [0.0]
  We propose a general-purpose pure quantum approximate optimization algorithm. The algorithm is constructed to a $p$-level divide-and-conquer structure. We show the algorithm performance in detail when the required qubits number of the two optimization problems is 10.
  arXiv  Detail & Related papers  (2023-10-27T06:54:39Z)
• Optimizing Variational Circuits for Higher-Order Binary Optimization [2.578242050187029]
  We propose new approaches to encode their Hamiltonian into a ready-to-implement circuit involving only two-qubit gates. We evaluate our approaches by comparing them with the state of the art, showcasing clear gains in terms of circuit depth.
  arXiv  Detail & Related papers  (2023-07-31T15:27:06Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Improving Quantum Computation by Optimized Qubit Routing [0.0]
  We propose a high-quality decomposition approach for qubit routing by swap insertion. This optimization problem arises in the context of compiling quantum algorithms onto specific quantum hardware. We present numerical results for the integrated allocation and token swapping problem.
  arXiv  Detail & Related papers  (2022-06-02T20:32:18Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Improving the Quantum Approximate Optimization Algorithm with postselection [0.0]
  Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers. We consider a well-studied quantum algorithm for optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs. We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable.
  arXiv  Detail & Related papers  (2020-11-10T22:17:50Z)

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.