Multi-qubit circuit synthesis and Hermitian lattices

• URL: http://arxiv.org/abs/2405.19302v1
• Date: Wed, 29 May 2024 17:27:50 GMT
• Title: Multi-qubit circuit synthesis and Hermitian lattices
• Authors: Vadym Kliuchnikov, Sebastian Schönnenbeck,
• Abstract summary: We present new optimal and synthesis algorithms for exact synthesis of multi-qubit unitaries and isometries. The optimal algorithms are the A* search instantiated with a new data structure for graph and new consistent functions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present new optimal and heuristic algorithms for exact synthesis of multi-qubit unitaries and isometries. For example, our algorithms find Clifford and T circuits for unitaries with entries in $\mathbb{Z}[i,1/\sqrt{2}]$. The optimal algorithms are the A* search instantiated with a new data structure for graph vertices and new consistent heuristic functions. We also prove that for some gate sets, best-first search synthesis relying on the same heuristic is efficient. For example, for two-qubit Clifford and T circuits, our best-first search runtime is proportional to the T-count of the unitary. Our algorithms rely on Hermite and Smith Normal Forms of matrices with entries in a ring of integers of a number field, and we leverage the theory of and algorithms for Hermitian lattices over number fields to prove efficiency. These new techniques are of independent interest for future work on multi-qubit exact circuit synthesis and related questions.

Related papers

• A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman Problem [0.9790236766474201]
  This paper proposes a hybrid genetic algorithm for solving the Multiple Traveling Salesman Problem (mTSP) A novel crossover operator is designed to combine similar tours from two parents and offers great diversity for the population. Our algorithm outperforms all existing algorithms on average, with similar cutoff time thresholds, when tested against benchmark sets.
  arXiv  Detail & Related papers  (2023-07-14T01:57:10Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• 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)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  We propose a new Hessian inverse free Fully Single Loop Algorithm for bilevel optimization problems. We show that our algorithm converges with the rate of $O(epsilon-2)$.
  arXiv  Detail & Related papers  (2021-12-09T02:27:52Z)
• 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)
• Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
  We introduce a new notion of well-separation to reduce the work and space of our algorithm for HDBSCAN$*$. We show that our algorithms are theoretically efficient: they have work (number of operations) matching their sequential counterparts, and polylogarithmic depth (parallel time) Our experiments on large real-world and synthetic data sets using a 48-core machine show that our fastest algorithms outperform the best serial algorithms for the problems by 11.13--55.89x, and existing parallel algorithms by at least an order of magnitude.
  arXiv  Detail & Related papers  (2021-04-02T16:05:00Z)
• 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)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• A Study of Performance of Optimal Transport [16.847501106437534]
  We show that network simplex and augmenting path based algorithms can consistently outperform numerical matrix-scaling based methods. We present a new algorithm that improves upon the classical Kuhn-Munkres algorithm.
  arXiv  Detail & Related papers  (2020-05-03T20:37:05Z)

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.