A doubly stochastic matrices-based approach to optimal qubit routing

• URL: http://arxiv.org/abs/2211.07222v1
• Date: Mon, 14 Nov 2022 09:25:35 GMT
• Title: A doubly stochastic matrices-based approach to optimal qubit routing
• Authors: Nicola Mariella, Sergiy Zhuk
• Abstract summary: Swap mapping is a quantum compiler optimization that, by SWAP gates, maps a logical quantum circuit to an equivalent physically implementable one. In this work, we employ a structure called doubly convex matrix, which is defined as a combination of permutation matrices. We show that the proposed algorithm, at the cost of additional time, can deliver significant depth reduction when compared to the state of the art algorithm SABRE.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Swap mapping is a quantum compiler optimization that, by introducing SWAP gates, maps a logical quantum circuit to an equivalent physically implementable one. The physical implementability of a circuit is determined by the fulfillment of the hardware connectivity constraints. Therefore, the placement of the SWAP gates can be interpreted as a discrete optimization process. In this work, we employ a structure called doubly stochastic matrix, which is defined as a convex combination of permutation matrices. The intuition is that of making the decision process smooth. Doubly stochastic matrices are contained in the Birkhoff polytope, in which the vertices represent single permutation matrices. In essence, the algorithm uses smooth constrained optimization to slide along the edges of the polytope toward the potential solutions on the vertices. In the experiments, we show that the proposed algorithm, at the cost of additional computation time, can deliver significant depth reduction when compared to the state of the art algorithm SABRE.

Related papers

• A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm [9.804179673817574]
  We propose a new quantum algorithm for the quantum linear system problem (QLSP) inspired by the classical proximal point algorithm (PPA) Our proposed method can be viewed as a meta-algorithm that allows inverting a modified matrix via an existing texttimattQLSP_solver. By carefully choosing the step size $eta$, the proposed algorithm can effectively precondition the linear system to mitigate the dependence on condition numbers that hindered the applicability of previous approaches.
  arXiv  Detail & Related papers  (2024-06-19T23:15:35Z)
• Tensor networks based quantum optimization algorithm [0.0]
  In optimization, one of the well-known classical algorithms is power iterations. We propose a quantum realiziation to circumvent this pitfall. Our methodology becomes instance agnostic and thus allows one to address black-box optimization within the framework of quantum computing.
  arXiv  Detail & Related papers  (2024-04-23T13:49:11Z)
• GRAPE optimization for open quantum systems with time-dependent decoherence rates driven by coherent and incoherent controls [77.34726150561087]
  The GRadient Ascent Pulse Engineering (GRAPE) method is widely used for optimization in quantum control. We adopt GRAPE method for optimizing objective functionals for open quantum systems driven by both coherent and incoherent controls. The efficiency of the algorithm is demonstrated through numerical simulations for the state-to-state transition problem.
  arXiv  Detail & Related papers  (2023-07-17T13:37:18Z)
• 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)
• Classical and Quantum Iterative Optimization Algorithms Based on Matrix Legendre-Bregman Projections [1.5736899098702972]
  We consider Legendre-Bregman projections defined on the Hermitian matrix space and design iterative optimization algorithms based on them. We study both exact and approximate Bregman projection algorithms. In particular, our approximate iterative algorithm gives rise to the non-commutative versions of the generalized iterative scaling (GIS) algorithm for maximum entropy inference.
  arXiv  Detail & Related papers  (2022-09-28T15:59:08Z)
• Generating quantum feature maps for SVM classifier [0.0]
  We present and compare two methods of generating quantum feature maps for quantum-enhanced support vector machine. The first method is a genetic algorithm with multi-objective fitness function using penalty method, which incorporates maximizing the accuracy of classification. The second method uses variational quantum circuit, focusing on how to contruct the ansatz based on unitary matrix decomposition.
  arXiv  Detail & Related papers  (2022-07-23T07:28:23Z)
• A quantum algorithm for solving eigenproblem of the Laplacian matrix of a fully connected weighted graph [4.045204834863644]
  We propose an efficient quantum algorithm to solve the eigenproblem of the Laplacian matrix of a fully connected weighted graph. Specifically, we adopt the optimal Hamiltonian simulation technique based on the block-encoding framework. We also show that our algorithm can be extended to solve the eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.
  arXiv  Detail & Related papers  (2022-03-28T02:24:08Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• 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)

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.