Factorized Boolean representations for efficient quantum synthesis

• URL: http://arxiv.org/abs/2608.27430v2
• Date: Tue, 01 Sep 2026 01:35:47 GMT
• Title: Factorized Boolean representations for efficient quantum synthesis
• Abstract summary: We show that the representation of a computation is itself a resource, optimizable before compilation and distinct from both logic minimization and circuit-level optimization.<n>Across benchmarks and oracles from quantum search and factoring algorithms, at the representation level the transformation never increases either cost measure, a guarantee from its construction.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum algorithms promise advantages beyond classical reach, but running them on error-corrected hardware requires translating Boolean specifications into reversible circuits, and the resources that translation demands determine what is executable. Established methods minimize a Boolean expression and map it to a circuit, assuming the minimized form is best. Here we show that minimized expressions retain algebraic structure minimization cannot reach, arising from containment and complementary-polarity relationships among their terms, and that extracting it yields circuits cheaper to execute despite having more operations. The decisive quantity is not a circuit's operation count but the control count of its widest operation, a superlinear cost; extracting shared factors trades a few wide operations for many narrow ones and reduces qubit count. Across benchmarks and oracles from quantum search and factoring algorithms, at the representation level the transformation never increases either cost measure, a guarantee from its construction. Translation to an executable circuit returns part of that advantage, since auxiliary lines must be uncomputed, yet the factorized circuit still left a leading circuit-level optimizer reaching lower final counts, and faster, than unaided. The representation of a computation is therefore itself a resource, optimizable before compilation and distinct from both logic minimization and circuit-level optimization.

Related papers

• General circuit mapping algorithm for neutral atom quantum computers [1.047947389293086]
  Neutral atom quantum computers (NAQC) are emerging as a promising, scalable quantum computing platform.<n> circuit execution often requires physically moving qubits, making compilation a critical optimization challenge.<n>We propose a circuit independent mathematical framework built on graph-theoretic optimization that determines the minimal number of required qubit transfers.
  arXiv  Detail & Related papers  (2026-06-18T17:21:23Z)
• Weights to Code: Extracting Interpretable Algorithms from the Discrete Transformer [65.38883376379812]
  We propose the Discrete Transformer, an architecture engineered to bridge the gap between continuous representations and discrete symbolic logic.<n> Empirically, the Discrete Transformer not only achieves performance comparable to RNN-based baselines but crucially extends interpretability to continuous variable domains.
  arXiv  Detail & Related papers  (2026-01-09T12:49:41Z)
• Arbitrage: Efficient Reasoning via Advantage-Aware Speculation [71.45710345765528]
  Speculative Decoding accelerates inference by employing a fast but inaccurate draft model to autoregressively propose tokens.<n>But due to unnecessary rejections caused by token mismatches in semantically equivalent steps, traditional token-level Speculative Decoding struggles in reasoning tasks.<n>We propose Arbitrage, a novel step-level speculative generation framework that routes generation dynamically based on the relative advantage between draft and target models.
  arXiv  Detail & Related papers  (2025-12-04T17:50:53Z)
• Application Scale Quantum Circuit Compilation with Controlled Error [1.5546281258530152]
  We develop a practical workflow for managing and optimizing tradeoffs in quantum circuit compilation and optimization.<n>We demonstrate our workflow on several benchmark algorithmic circuits acting on up to 380 qubits.
  arXiv  Detail & Related papers  (2025-10-20T18:29:02Z)
• Nontrivial multi-product commutation relation for reducing T-count in sequential Pauli-based computation [2.9436347471485558]
  We introduce a nontrivial and ancilla-free equivalent transformation rule, the multi-product commutation relation (MCR)<n>This rule constructs gate sequences based on specific commutation properties among multi-Pauli operators, yielding seemingly non-commutative instances that can be commuted.<n>Our numerical experiments reveal that the transformation rule based on MCR is not yet incorporated into current compilers.
  arXiv  Detail & Related papers  (2025-09-24T12:19:30Z)
• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• Circuit Cutting with Non-Maximally Entangled States [59.11160990637615]
  Distributed quantum computing combines the computational power of multiple devices to overcome the limitations of individual devices. circuit cutting techniques enable the distribution of quantum computations through classical communication. Quantum teleportation allows the distribution of quantum computations without an exponential increase in shots. We propose a novel circuit cutting technique that leverages non-maximally entangled qubit pairs.
  arXiv  Detail & Related papers  (2023-06-21T08:03:34Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits [0.0]
  reversible circuits represent a subclass of reversible circuits with many applications in quantum computing. We propose a new algorithm for any linear reversible operator by using an optimized version of the Gaussian elimination algorithm and a tuned LU factorization. Overall, our algorithms improve the state-of-the-art methods for specific ranges of problem sizes.
  arXiv  Detail & Related papers  (2022-01-17T16:31:42Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)

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.