A SAT Encoding for Optimal Clifford Circuit Synthesis

• URL: http://arxiv.org/abs/2208.11713v1
• Date: Wed, 24 Aug 2022 18:00:03 GMT
• Title: A SAT Encoding for Optimal Clifford Circuit Synthesis
• Authors: Sarah Schneider, Lukas Burgholzer, Robert Wille
• Abstract summary: 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.
• Score: 3.610459670994051
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Executing quantum algorithms on a quantum computer requires compilation to representations that conform to all restrictions imposed by the device. Due to device's limited coherence times and gate fidelities, the compilation process has to be optimized as much as possible. To this end, an algorithm's description first has to be synthesized using the device's gate library. In this paper, we consider the optimal synthesis of Clifford circuits -- an important subclass of quantum circuits, with various applications. Such techniques are essential to establish lower bounds for (heuristic) synthesis methods and gauging their performance. Due to the huge search space, existing optimal techniques are limited to a maximum of six qubits. The contribution of this work is twofold: First, we propose an optimal synthesis method for Clifford circuits based on encoding the task as a satisfiability (SAT) problem and solving it using a SAT solver in conjunction with a binary search scheme. The resulting tool is demonstrated to synthesize optimal circuits for up to $26$ qubits -- more than four times as many as the current state of the art. Second, we experimentally show that the overhead introduced by state-of-the-art heuristics exceeds the lower bound by $27\%$ on average. The resulting tool is publicly available at https://github.com/cda-tum/qmap.

Related papers

• High Precision Fault-Tolerant Quantum Circuit Synthesis by Diagonalization using Reinforcement Learning [0.8341988468339112]
  Empirical search-based synthesis methods can generate good implementations for a more extensive set of unitaries. We leverage search-based methods to reduce the general unitary synthesis problem to one of diagonal unitaries. On a subset of algorithms of interest for future term applications, diagonalization can reduce T gate counts by up to 16.8%.
  arXiv  Detail & Related papers  (2024-08-31T12:10:32Z)
• Quantum Compiling with Reinforcement Learning on a Superconducting Processor [55.135709564322624]
  We develop a reinforcement learning-based quantum compiler for a superconducting processor. We demonstrate its capability of discovering novel and hardware-amenable circuits with short lengths. Our study exemplifies the codesign of the software with hardware for efficient quantum compilation.
  arXiv  Detail & Related papers  (2024-06-18T01:49:48Z)
• 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)
• Improving Quantum Circuit Synthesis with Machine Learning [0.7894596908025954]
  We show how applying machine learning to unitary datasets permits drastic speedups for synthesis algorithms. This paper presents QSeed, a seeded synthesis algorithm that employs a learned model to quickly propose resource efficient circuit implementations of unitaries.
  arXiv  Detail & Related papers  (2023-06-09T01:53:56Z)
• Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers [4.208975913508643]
  Optimal synthesis is a central problem in both quantum and classical hardware design. We use entangling input stimuli and the stabilizer formalism to reduce the Clifford synthesis problem to a family of poly-size satisfiability problems. Empirical evaluations show that the optimal synthesis approach yields a substantial depth improvement for random Clifford circuits and Clifford+T circuits for Grover search.
  arXiv  Detail & Related papers  (2023-05-02T18:00:00Z)
• Iterative Qubit Coupled Cluster using only Clifford circuits [36.136619420474766]
  An ideal state preparation protocol can be characterized by being easily generated classically. We propose a method that meets these requirements by introducing a variant of the iterative qubit coupled cluster (iQCC) We demonstrate the algorithm's correctness in ground-state simulations and extend our study to complex systems like the titanium-based compound Ti(C5H5)(CH3)3 with a (20, 20) active space.
  arXiv  Detail & Related papers  (2022-11-18T20:31:10Z)
• 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)
• QFAST: Conflating Search and Numerical Optimization for Scalable Quantum Circuit Synthesis [5.406226763868874]
  We present a quantum synthesis algorithm designed to produce short circuits and to scale well in practice. Main contribution is a novel representation of circuits able to encode placement and topology using generic "gates" When compared against optimal depth, search based state-of-the-art techniques, QFAST produces comparable results.
  arXiv  Detail & Related papers  (2021-03-12T05:20:12Z)
• 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)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
  arXiv  Detail & Related papers  (2020-06-21T15:32:21Z)
• QFAST: Quantum Synthesis Using a Hierarchical Continuous Circuit Space [5.406226763868874]
  We present QFAST, a quantum synthesis tool designed to produce short circuits. We show how to generate shorter circuits by plugging in the best available third party synthesis algorithm at a given hierarchy level.
  arXiv  Detail & Related papers  (2020-03-09T23:55:43Z)

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.