Optimal Toffoli-Depth Multi-Controlled Toffoli Decomposition in 2D Qubit Layout

• URL: http://arxiv.org/abs/2606.15113v1
• Date: Sat, 13 Jun 2026 05:02:39 GMT
• Title: Optimal Toffoli-Depth Multi-Controlled Toffoli Decomposition in 2D Qubit Layout
• Abstract summary: We study architecture-aware mappings of optimal Toffoli-depth MCT decompositions onto restricted two-dimensional qubit layouts.<n>We introduce a motif-based packing framework in which interaction motifs are represented by basic Toffoli gates.
• Score: 2.5756681494057045
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The multi-controlled Toffoli (MCT) gate is a key primitive in quantum arithmetic, oracle construction, and quantum cryptanalysis. Although recent work has established optimal Toffoli-depth MCT decompositions under all-to-all qubit connectivity, their realization on near-term quantum hardware with restricted qubit connectivity remains largely unexplored. While general-purpose quantum mappers can route arbitrary circuits, they do not explicitly exploit the repeated interaction patterns inherent in MCT decompositions. In our present paper, we study architecture-aware mappings of optimal Toffoli-depth MCT decompositions onto restricted two-dimensional qubit layouts. We begin with a structured geometric placements that preserve the parallelism of state-of-the-art Toffoli and MCT decompositions with no additional depth overhead. We further introduce a motif-based packing framework in which decomposition layers are represented by interaction motifs derived from basic Toffoli gates. By embedding these motifs vertex-disjointly into hardware graphs, we characterize the minimum-size topologies supporting the required qubit resources and derive explicit bounds on the resulting depth overhead under tight qubit budgets. Finally, we compare these bounds with routing-aware placement heuristics and empirically evaluate the effectiveness of embedding different motifs across a range of hardware topologies.

Related papers

• Structure-Aware Placement and Routing of Multi-Controlled Toffoli on Bivariate Bicycle Code Architectures [6.023860258848104]
  We introduce a targeted placement strategy that exploits the binary-tree structure of MCT decompositions to co-locate interacting subtrees.<n>We also evaluate the impact of factory placement across different topologies, demonstrating that grid-based layouts yield up to a $mathbf23.7%$ reduction in inter-module instructions.
  arXiv  Detail & Related papers  (2026-09-01T07:47:42Z)
• Adaptive Clifford+T Decomposition of Large Toffoli Gates with One Clean Ancilla [1.214455026524814]
  Multi-controlled Toffoli gates are fundamental building blocks in quantum computation, with applications in quantum arithmetic, simulation, and search algorithms.<n>Recent advances have demonstrated that the use of ancillary qubits, relative-phase Toffoli gates, and dynamic circuit techniques can substantially reduce this overhead.<n>We derive explicit resource bounds for Clifford+T implementations incorporating dynamic-circuit-based uncomputation and measurement-conditioned corrections.
  arXiv  Detail & Related papers  (2026-05-18T10:11:18Z)
• Occlusion Boundary and Depth: Mutual Enhancement via Multi-Task Learning [3.4174356345935393]
  We propose MoDOT, a novel method that jointly estimates depth and OBs from a single image.<n>MoDOT incorporates a new module, CASM, which combines cross-attention and multi-scale strip convolutions to leverage mid-level OB features.<n>Experiments demonstrate the mutual benefits of jointly estimating depth and OBs, and validate the effectiveness of MoDOT's design.
  arXiv  Detail & Related papers  (2025-05-27T14:15:19Z)
• Landscaping Linear Mode Connectivity [76.39694196535996]
  linear mode connectivity (LMC) has garnered interest from both theoretical and practical fronts. We take a step towards understanding it by providing a model of how the loss landscape needs to behave topographically for LMC.
  arXiv  Detail & Related papers  (2024-06-24T03:53:30Z)
• 360 Layout Estimation via Orthogonal Planes Disentanglement and Multi-view Geometric Consistency Perception [56.84921040837699]
  Existing panoramic layout estimation solutions tend to recover room boundaries from a vertically compressed sequence, yielding imprecise results. We propose an orthogonal plane disentanglement network (termed DOPNet) to distinguish ambiguous semantics. We also present an unsupervised adaptation technique tailored for horizon-depth and ratio representations. Our solution outperforms other SoTA models on both monocular layout estimation and multi-view layout estimation tasks.
  arXiv  Detail & Related papers  (2023-12-26T12:16:03Z)
• A T-depth two Toffoli gate for 2D square lattice architectures [49.88310438099143]
  We present a novel Clifford+T decomposition of a Toffoli gate. Our decomposition requires no SWAP gates in order to be implemented on 2D square lattices of qubits. This decomposition enables shallower, more fault-tolerant quantum computations on both NISQ and error-corrected architectures.
  arXiv  Detail & Related papers  (2023-11-21T10:33:51Z)
• Low-depth simulations of fermionic systems on square-grid quantum hardware [0.0]
  We present a strategy for mapping fermionic systems to quantum hardware with square qubit connectivity. We report unprecedentedly low circuit depths per single Trotter layer with up to a $70 %$ improvement upon previous state-of-the-art.
  arXiv  Detail & Related papers  (2023-02-03T17:08:26Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• Suppress and Balance: A Simple Gated Network for Salient Object Detection [89.88222217065858]
  We propose a simple gated network (GateNet) to solve both issues at once. With the help of multilevel gate units, the valuable context information from the encoder can be optimally transmitted to the decoder. In addition, we adopt the atrous spatial pyramid pooling based on the proposed "Fold" operation (Fold-ASPP) to accurately localize salient objects of various scales.
  arXiv  Detail & Related papers  (2020-07-16T02:00:53Z)
• Deep Semantic Matching with Foreground Detection and Cycle-Consistency [103.22976097225457]
  We address weakly supervised semantic matching based on a deep network. We explicitly estimate the foreground regions to suppress the effect of background clutter. We develop cycle-consistent losses to enforce the predicted transformations across multiple images to be geometrically plausible and consistent.
  arXiv  Detail & Related papers  (2020-03-31T22:38:09Z)

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.