Efficient and high-performance routing of lattice-surgery paths on three-dimensional lattice

• URL: http://arxiv.org/abs/2401.15829v1
• Date: Mon, 29 Jan 2024 01:28:42 GMT
• Title: Efficient and high-performance routing of lattice-surgery paths on three-dimensional lattice
• Abstract summary: We propose a fast and high-performance scheduling algorithm for lattice-surgery instructions. We numerically show that this method reduced the execution time of benchmark programs generated from quantum phase estimation algorithms by 2.7 times.
• Score: 0.2209921757303168
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Encoding logical qubits with surface codes and performing multi-qubit logical operations with lattice surgery is one of the most promising approaches to demonstrate fault-tolerant quantum computing. Thus, a method to efficiently schedule a sequence of lattice-surgery operations is vital for high-performance fault-tolerant quantum computing. A possible strategy to improve the throughput of lattice-surgery operations is splitting a large instruction into several small instructions such as Bell state preparation and measurements and executing a part of them in advance. However, scheduling methods to fully utilize this idea have yet to be explored. In this paper, we propose a fast and high-performance scheduling algorithm for lattice-surgery instructions leveraging this strategy. We achieved this by converting the scheduling problem of lattice-surgery instructions to a graph problem of embedding 3D paths into a 3D lattice, which enables us to explore efficient scheduling by solving path search problems in the 3D lattice. Based on this reduction, we propose a method to solve the path-finding problems, Dijkstra projection. We numerically show that this method reduced the execution time of benchmark programs generated from quantum phase estimation algorithms by 2.7 times compared with a naive method based on greedy algorithms. Our study establishes the relation between the lattice-surgery scheduling and graph search problems, which leads to further theoretical analysis on compiler optimization of fault-tolerant quantum computing.

Related papers

• Rolling Stock Planning Using the Quantum Approximate Optimization Algorithm [0.0]
  Rolling stock planning is a complex optimization problem in railway management.<n>We reformulate the problem as a Maximum-Weight Independent Set (MWIS) problem on a graph where nodes represent feasible train cycles.<n>To handle the computational complexity of the large search space, we propose a hybrid divide-and-conquer algorithm.
  arXiv  Detail & Related papers  (2026-06-09T19:06:55Z)
• Exploration of Design Alternatives for Reducing Idle Time in Shor's Algorithm: A Study on Monolithic and Distributed Quantum Systems [4.430488261124667]
  We introduce an alternating design approach to minimize idle time while preserving qubit efficiency in Shor's algorithm. We also demonstrate how task rearrangement enhances execution efficiency in the presence of multiple distribution channels. Our findings provide a structured framework for optimizing compiled quantum circuits for Shor's algorithm.
  arXiv  Detail & Related papers  (2025-03-28T16:07:52Z)
• Theoretical Analysis of Quality Diversity Algorithms for a Classical Path Planning Problem [12.1622929638257]
  We study the behaviour of Quality diversity (QD) algorithms for a classical planning problem seeking several solutions. Our results show that Map-Elites QD algorithms are able to compute a shortest path for each pair of nodes efficiently in parallel.
  arXiv  Detail & Related papers  (2024-12-16T04:58:32Z)
• Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions [1.3812010983144802]
  We introduce a novel approach based on the greedy algorithm by opt_einsum that computes efficient contraction paths in less time. With our approach, we are even able to compute paths for large problems where modern algorithms fail.
  arXiv  Detail & Related papers  (2024-05-08T09:25:39Z)
• Task Scheduling Optimization with Direct Constraints from a Tensor Network Perspective [41.94295877935867]
  This work presents a novel method for task optimization in industrial plants using quantum-inspired tensor network technology.<n>Three algorithms for computation are presented: the main algorithm, the iterative algorithm which adds only the minimal amount of necessary constraints, and the genetic algorithm which combines the iterative algorithm with basic genetic algorithms.
  arXiv  Detail & Related papers  (2023-11-17T10:10:46Z)
• 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)
• Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning Problems [0.7614628596146599]
  We propose a novel algorithm for adaptive step length selection in the classical SGD framework. Under reasonable conditions, the algorithm produces step lengths in line with well-established theoretical requirements. We show that the algorithm can generate step lengths comparable to the best step length obtained from manual tuning.
  arXiv  Detail & Related papers  (2023-05-17T06:22:11Z)
• FastDiagP: An Algorithm for Parallelized Direct Diagnosis [64.65251961564606]
  FastDiag is a typical direct diagnosis algorithm that supports diagnosis calculation without predetermining conflicts. We propose a novel algorithm, so-called FastDiagP, which is based on the idea of speculative programming. This mechanism helps to provide consistency checks with fast answers and boosts the algorithm's runtime performance.
  arXiv  Detail & Related papers  (2023-05-11T16:26:23Z)
• Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds [7.428782604099876]
  A major obstacle to practical applications of Gibbs distributions is the need to estimate their partition functions. We present a novel method for reducing the computational complexity of rigorously estimating the partition functions.
  arXiv  Detail & Related papers  (2021-11-14T15:42:02Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• 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)
• Learning to solve TV regularized problems with unrolled algorithms [18.241062505073234]
  Total Variation (TV) is a popular regularization strategy that promotes piece-wise constant signals. We develop and characterize two approaches to do so, describe their benefits and limitations, and discuss the regime where they can actually improve over iterative procedures.
  arXiv  Detail & Related papers  (2020-10-19T14:19:02Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• SONIA: A Symmetric Blockwise Truncated Optimization Algorithm [2.9923891863939938]
  This work presents a new algorithm for empirical risk. The algorithm bridges the gap between first- and second-order search methods by computing a second-order search-type update in one subspace, coupled with a scaled steepest descent step in the Theoretical complement.
  arXiv  Detail & Related papers  (2020-06-06T19:28:14Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

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.