Optimal T depth quantum circuits for implementing arbitrary Boolean functions

• URL: http://arxiv.org/abs/2506.01542v1
• Date: Mon, 02 Jun 2025 11:07:54 GMT
• Title: Optimal T depth quantum circuits for implementing arbitrary Boolean functions
• Authors: Suman Dutta, Anik Basu Bhaumik, Anupam Chattopadhyay, Subhamoy Maitra,
• Abstract summary: We present a generic construction to obtain an optimal T depth quantum circuit for any arbitrary $n$-input $m$-output Boolean function $f.<n>We achieve this by inspecting the Algebraic Normal Form (ANF) of a Boolean function.<n>The implications of our results are highlighted explaining the provable lower bounds on S-box and block cipher implementations.
• Score: 4.730360540444164
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we present a generic construction to obtain an optimal T depth quantum circuit for any arbitrary $n$-input $m$-output Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}^m$ having algebraic degree $k\leq n$, and it achieves an exact Toffoli (and T) depth of $\lceil \log_2 k \rceil$. This is a broader generalization of the recent result establishing the optimal Toffoli (and consequently T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). We achieve this by inspecting the Algebraic Normal Form (ANF) of a Boolean function. Obtaining a benchmark for the minimum T depth of such circuits are of prime importance for efficient implementation of quantum algorithms by enabling greater parallelism, reducing time complexity, and minimizing circuit latency, making them suitable for near-term quantum devices with limited coherence times. The implications of our results are highlighted explaining the provable lower bounds on S-box and block cipher implementations, for example AES.

Related papers

• 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)
• A log-depth in-place quantum Fourier transform that rarely needs ancillas [0.08113005007481719]
  "optimistic quantum circuits" are often sufficient in the context of larger quantum algorithms.<n>We build an optimistic circuit for the in-place quantum Fourier transform (QFT)<n>We apply our reduction technique to yield an approximate QFT with well-controlled error on all inputs.
  arXiv  Detail & Related papers  (2025-05-01T17:58:36Z)
• 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)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Optimal Toffoli-Depth Quantum Adder [4.183952203508634]
  Efficient quantum arithmetic circuits are commonly found in numerous quantum algorithms of practical significance. In this work, 160 alternative compositions of the carry-propagation structure are explored to determine the optimal depth structure for a quantum adder.
  arXiv  Detail & Related papers  (2024-05-03T23:38:13Z)
• 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)
• Trainability Analysis of Quantum Optimization Algorithms from a Bayesian Lens [2.9356265132808024]
  We show that a noiseless QAOA circuit with a depth of $tildemathtlog nright)$ can be trained efficiently. Our results offer theoretical performance of quantum algorithms in the noisy intermediate-scale quantum era.
  arXiv  Detail & Related papers  (2023-10-10T02:56:28Z)
• Automatic Depth-Optimized Quantum Circuit Synthesis for Diagonal Unitary Matrices with Asymptotically Optimal Gate Count [9.194399933498323]
  It is of great importance to optimize the depth/gate-count when designing quantum circuits for specific tasks. In this paper, we propose a depth-optimized synthesis algorithm that automatically produces a quantum circuit for any given diagonal unitary matrix.
  arXiv  Detail & Related papers  (2022-12-02T06:58:26Z)
• Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation [5.746732081406236]
  We develop a phase estimation method with a distinct feature. The total cost of the algorithm satisfies the Heisenberg-limited scaling $widetildemathcalO(epsilon-1)$. Our algorithm may significantly reduce the circuit depth for performing phase estimation tasks on early fault-tolerant quantum computers.
  arXiv  Detail & Related papers  (2022-11-22T03:15:40Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• 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)

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.