Lowering the T-depth of Quantum Circuits By Reducing the Multiplicative Depth Of Logic Networks

• URL: http://arxiv.org/abs/2006.03845v1
• Date: Sat, 6 Jun 2020 11:08:06 GMT
• Title: Lowering the T-depth of Quantum Circuits By Reducing the Multiplicative Depth Of Logic Networks
• Authors: Thomas H\"aner and Mathias Soeken
• Abstract summary: We describe a programming based logic synthesis algorithm to reduce the multiplicative depth in logic networks. Our algorithm has applications to cryptography and quantum computing, as a reduction in the multiplicative depth directly translates to a lower $T$-depth of the corresponding quantum circuit.
• Score: 1.4902915966744057
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The multiplicative depth of a logic network over the gate basis $\{\land, \oplus, \neg\}$ is the largest number of $\land$ gates on any path from a primary input to a primary output in the network. We describe a dynamic programming based logic synthesis algorithm to reduce the multiplicative depth in logic networks. It makes use of cut enumeration, tree balancing, and exclusive sum-of-products (ESOP) representations. Our algorithm has applications to cryptography and quantum computing, as a reduction in the multiplicative depth directly translates to a lower $T$-depth of the corresponding quantum circuit. Our experimental results show improvements in $T$-depth over state-of-the-art methods and over several hand-optimized quantum circuits for instances of AES, SHA, and floating-point arithmetic.

Related papers

• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Resource quantification for programming low-depth quantum circuits [13.23922654679552]
  We investigate the gate complexity and the size of quantum memory required to program low-depth brickwork circuits.<n>Our findings suggest that faithful gate-wise programming is optimal in the low-depth regime.
  arXiv  Detail & Related papers  (2025-09-11T17:30:32Z)
• Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms [10.292476979020522]
  We present a systematic meta-algorithm that converts essentially any circuit into a feedforward neural network (NN)<n>We show that, on any digital computer, our construction emulates the circuit exactly--no approximation, no rounding, modular overflow included--demonstrating that no reasoning task lies beyond the reach of neural networks.
  arXiv  Detail & Related papers  (2025-08-25T21:55:37Z)
• Optimization and Synthesis of Quantum Circuits with Global Gates [44.99833362998488]
  We use global interactions, such as the Global Molmer-Sorensen gate present in ion trap hardware, to optimize and synthesize quantum circuits.<n>The algorithm is based on the ZX-calculus and uses a specialized circuit extraction routine that groups entangling gates into Global MolmerSorensen gates.<n>We benchmark the algorithm in a variety of circuits, and show how it improves their performance under state-of-the-art hardware considerations.
  arXiv  Detail & Related papers  (2025-07-28T10:25:31Z)
• Learning Circuits with Infinite Tensor Networks [0.4972323953932129]
  Hamiltonian simulation on quantum computers is constrained by gate counts, motivating techniques to reduce circuit depths.<n>We leverage tensor networks to support circuit design, with datasets of tensor networks enabling a unitary synthesis inspired by quantum machine learning.<n>Our approach finds circuits to efficiently prepare ground states, and perform time evolution on both infinite and finite systems.
  arXiv  Detail & Related papers  (2025-06-02T18:00:01Z)
• Optimizing Quantum Circuits via ZX Diagrams using Reinforcement Learning and Graph Neural Networks [38.499527873574436]
  We introduce a framework based on ZX calculus, graph-neural networks and reinforcement learning for quantum circuit optimization.<n>By combining reinforcement learning and tree search, our method addresses the challenge of selecting optimal sequences of ZX calculus rewrite rules.<n>We demonstrate our method's competetiveness with state-of-the-art circuit generalizations and capabilities on large sets of diverse random circuits.
  arXiv  Detail & Related papers  (2025-04-04T13:19:08Z)
• Extractors: QLDPC Architectures for Efficient Pauli-Based Computation [42.95092131256421]
  We propose a new primitive that can augment any QLDPC memory into a computational block well-suited for Pauli-based computation. In particular, any logical Pauli operator supported on the memory can be fault-tolerantly measured in one logical cycle. Our architecture can implement universal quantum circuits via parallel logical measurements.
  arXiv  Detail & Related papers  (2025-03-13T14:07:40Z)
• Distributed quantum logic algorithm [0.0]
  This work examines a method for reducing circuit depth by introducing auxiliary qubits to enable parallel gate execution. We show that any circuit on $n$ qubits with depth $Oleft(M n2right)$, where $M = M(n)$ is some function of $n$, can be transformed into a circuit with depth $Oleft(log_2(M) n2right)$ operating on $Oleft(M nright)$ qubits.
  arXiv  Detail & Related papers  (2024-11-18T19:08:07Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose arbitrary exponentials into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions. We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT circuits are a common building block of general quantum circuits. This article presents state-of-the-art algorithms for optimizing the number of CNOT gates. A simulated evaluation shows that the suggested is almost always beneficial and reduces the number of CNOT gates by up to 10%.
  arXiv  Detail & Related papers  (2024-08-07T19:51:22Z)
• Bootstrapping shallow circuits [0.1227734309612871]
  We bootstrap local inversion learning (LIL) to optimize quantum circuit depth by learning shallow representations for its sub-unitaries. Due to the binary search structure, the optimization algorithm has time logarithmic complexity in the depth of the original given circuit.
  arXiv  Detail & Related papers  (2024-03-21T18:00:00Z)
• A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
  Current quantum algorithms for solving CFD problems use a single quantum circuit and, in some cases, lattice-based methods. We introduce the a novel multiple circuits algorithm that makes use of a quantum lattice Boltzmann method (QLBM) The problem is cast as a stream function--vorticity formulation of the 2D Navier-Stokes equations and verified and tested on a 2D lid-driven cavity flow.
  arXiv  Detail & Related papers  (2024-01-20T15:32:01Z)
• Learning shallow quantum circuits [7.411898489476803]
  We present an algorithm for learning the description of any unknown $n$-qubit shallow quantum circuit $U$. We also provide a classical algorithm for learning the description of any unknown $n$-qubit state $lvert psi rangle$. Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions.
  arXiv  Detail & Related papers  (2024-01-18T16:05:00Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPs were introduced by Macchi as a model in quantum optics the 1970s. Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a classical computer is easier than on a classical one. Vanilla sampling consists in two steps, of respective costs $mathcalO(N3)$ and $mathcalO(Nr2)$ operations on a classical computer, where $r$ is the rank of the kernel matrix.
  arXiv  Detail & Related papers  (2023-05-25T08:43:11Z)
• Reducing the Depth of Quantum FLT-Based Inversion Circuit [0.5735035463793008]
  We propose to reduce the depth of the existing quantum Fermat's Little Theorem ( gates)-based inversion circuit for binary finite field. Our approach can serve as an alternative for a time-efficient implementation.
  arXiv  Detail & Related papers  (2022-04-16T00:20:18Z)
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
  arXiv  Detail & Related papers  (2022-01-27T13:16:30Z)
• A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
  We show that conditions amenable to classical trainability via gradient descent coincide with those necessary for efficiently solving quantum linear systems. We numerically demonstrate that the MNIST image dataset satisfies such conditions. We provide empirical evidence for $O(log n)$ training of a convolutional neural network with pooling.
  arXiv  Detail & Related papers  (2021-07-19T23:41:03Z)
• Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
  Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm. We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with. Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks.
  arXiv  Detail & Related papers  (2020-12-03T07:12:08Z)

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.