Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers

• URL: http://arxiv.org/abs/2305.01674v2
• Date: Fri, 2 Jun 2023 13:50:12 GMT
• Title: Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers
• Authors: Tom Peham, Nina Brandl, Richard Kueng, Robert Wille and Lukas Burgholzer
• Abstract summary: 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.
• Score: 4.208975913508643
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Circuit synthesis is the task of decomposing a given logical functionality into a sequence of elementary gates. It is (depth-)optimal if it is impossible to achieve the desired functionality with even shorter circuits. Optimal synthesis is a central problem in both quantum and classical hardware design, but also plagued by complexity-theoretic obstacles. Motivated by fault-tolerant quantum computation, we consider the special case of synthesizing blocks of Clifford unitaries. Leveraging entangling input stimuli and the stabilizer formalism allows us to reduce the Clifford synthesis problem to a family of poly-size satisfiability (SAT) problems -- one for each target circuit depth. On a conceptual level, our result showcases that the Clifford synthesis problem is contained in the first level of the polynomial hierarchy ($\mathsf{NP}$), while the classical synthesis problem for logical circuits is known to be complete for the second level of the polynomial hierarchy ($\Sigma_2^{\mathsf{P}}$). Based on this theoretical reduction, we formulate a SAT encoding for depth-optimal Clifford synthesis. We then employ SAT solvers to determine a satisfying assignment or to prove that no such assignment exists. From that, the shortest depth for which synthesis is still possible (optimality) as well as the actual circuit (synthesis) can be obtained. Empirical evaluations show that the optimal synthesis approach yields a substantial depth improvement for random Clifford circuits and Clifford+T circuits for Grover search.

Related papers

• QuCLEAR: Clifford Extraction and Absorption for Significant Reduction in Quantum Circuit Size [8.043057448895343]
  Currently available quantum devices suffer from noisy quantum gates, which degrade the fidelity of executed quantum circuits. We present QuCLEAR, a compilation framework designed to optimize quantum circuits.
  arXiv  Detail & Related papers  (2024-08-23T18:03:57Z)
• Unitary Synthesis of Clifford+T Circuits with Reinforcement Learning [2.4646794072984477]
  Unitary synthesis aims to identify a quantum circuit that represents a given unitary. We apply the tree-search method Gumbel AlphaZero to solve the problem for a subset of exactly synthesizable Clifford+T unitaries. Our method effectively synthesizes circuits for up to five qubits generated from randomized circuits with up to 60 gates.
  arXiv  Detail & Related papers  (2024-04-23T09:37:52Z)
• 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)
• A graph-state based synthesis framework for Clifford isometries [0.0]
  We tackle the problem of synthesizing a Clifford isometry into an executable quantum circuit. We propose a simple framework for synthesis that exploits the elementary properties of the Clifford group and one equation of the symplectic group. We report an improvement of the two-qubit depth necessary for the execution of a Clifford circuit on an LNN architecture.
  arXiv  Detail & Related papers  (2022-12-13T22:50:24Z)
• 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 single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Symbolic Synthesis of Clifford Circuits and Beyond [0.0]
  We show that the unitarity problem is co-NP-hard in general, but that it is in P when restricted to Clifford path sums. We then provide an algorithm to synthesize a Clifford circuit from a unitary Clifford path sum. We also provide a generalization of our extraction algorithm to arbitrary path sums.
  arXiv  Detail & Related papers  (2022-04-29T16:33:42Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete. We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes. Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
  arXiv  Detail & Related papers  (2021-08-10T15:00:20Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNF-based SAT and MaxSAT solvers are central to logic synthesis and verification systems. In this work, we propose a one-shot model derived from the Transformer architecture to solve the MaxSAT problem.
  arXiv  Detail & Related papers  (2021-07-15T04:47:35Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)

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.