Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates

Abstract

We explore the power of the unbounded Fan-Out gate and the Global Tunable gates generated by Ising-type Hamiltonians in constructing constant-depth quantum circuits, with particular attention to quantum memory devices. We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. These gates include the Fan-In gates defined by $|x⟩|b⟩\mapsto |x⟩|b\oplus f(x)⟩$ for $x\in \{0,1{\}}^n$ and $b\in \{0,1\}$, where $f$ is a Boolean function. The first of our constructions is based on computing the one-hot encoding of the control register $|x⟩$, while the second is based on Boolean analysis and exploits different representations of $f$ such as its Fourier expansion. Via these constructions, we obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices -- Quantum Random Access Memory (QRAM) and Quantum Random Access Gate (QRAG) -- of memory size $n$. The implementation based on one-hot encoding requires either $O(n{\log }^{(d)}n{\log }^{(d+1)}n)$ ancillae and $O(n{\log }^{(d)}n)$ Fan-Out gates or $O(n{\log }^{(d)}n)$ ancillae and $16d-10$ Global Tunable gates, where $d$ is any positive integer and ${\log }^{(d)}n=\log \cdots \log n$ is the $d$-times iterated logarithm. On the other hand, the implementation based on Boolean analysis requires $8d-6$ Global Tunable gates at the expense of $O(n^{1/(1-2^{-d})})$ ancillae.

54 pages, 11 figures. v2: corrected typos, added one figure and references; v3: published version in Quantum Journal, added more references, included a table of related results, improved the ancillary complexity for both QRAM and QRAG, changed the title

References in corpus (65)

• Quantum algorithm for solving linear systems of equations
• Surface codes: Towards practical large-scale quantum computation
• Characterizing Quantum Supremacy in Near-Term Devices
• Quantum random access memory
• Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
• Experimental Quantum Computations on a Topologically Encoded Qubit
• Quantum advantage with shallow circuits
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Quantum-state preparation with universal gate decompositions
• Quantum speedup of Monte Carlo methods
• Architectures for a quantum random access memory
• Minimal Universal Two-qubit Quantum Circuits
• Creating superpositions that correspond to efficiently integrable probability distributions
• Efficient decomposition of quantum gates
• Efficient Distributed Quantum Computing
• Parallel Entangling Operations on a Universal Ion Trap Quantum Computer
• A divide-and-conquer algorithm for quantum state preparation
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Quantum circuits with uniformly controlled one-qubit gates
• Circuit-Based Quantum Random Access Memory for Classical Data
• Quantum advantage with noisy shallow circuits in 3D
• On the robustness of bucket brigade quantum RAM
• Black-box quantum state preparation without arithmetic
• Efficient Arbitrary Simultaneously Entangling Gates on a trapped-ion quantum computer
• High-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits
• Pattern recognition on a quantum computer
• Quantum Circuits with Unbounded Fan-out
• Two-qubit entangling gates within arbitrarily long chains of trapped ions
• A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
• Fault tolerant resource estimation of quantum random-access memories
• Decompositions of general quantum gates
• Compiling quantum algorithms for architectures with multi-qubit gates
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Single-step implementation of high fidelity $n$-bit Toffoli gate
• Resilience of quantum random access memory to generic noise
• Fast multi-qubit gates through simultaneous two-qubit gates
• Use of global interactions in efficient quantum circuit constructions
• Loading Classical Data into a Quantum Computer
• Efficient construction of three- and four-qubit quantum gates by global entangling gates
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
• Scalable and High-Fidelity Quantum Random Access Memory in Spin-Photon Networks
• Constructing quantum circuits with global gates
• Depth optimization of CZ, CNOT, and Clifford circuits
• Fast Black-Box Quantum State Preparation
• Synthesis of and compilation with time-optimal multi-qubit gates
• Constant-cost implementations of Clifford operations and multiply controlled gates using global interactions
• Quantum algorithm for optical template recognition with noise filtering
• Average-Case Quantum Advantage with Shallow Circuits
• Preparing Arbitrary Continuous Functions in Quantum Registers With Logarithmic Complexity
• Measuring the parity of an $N$-qubit state
• Quantum Expectation-Maximization for Gaussian Mixture Models
• Efficient quantum programming using EASE gates on a trapped-ion quantum computer
• Signal processing techniques for efficient compilation of controlled rotations in trapped ions
• On the Pauli Spectrum of QAC0
• Implementing the fanout gate by a Hamiltonian
• Approximate Quantum Random Access Memory Architectures
• Unconditional Quantum Advantage for Sampling with Shallow Circuits
• Noisy decoding by shallow circuits with parities: classical and quantum
• Depth-2 QAC circuits cannot simulate quantum parity
• Scalability and high-efficiency of an $(n+1)$-qubit Toffoli gate sphere via blockaded Rydberg atoms
• A colossal advantage: 3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits
• Quantum algorithms for classical Boolean functions via adaptive measurements: Exponential reductions in space-time resources
• Improved Circuit Lower Bounds and Quantum-Classical Separations
• On the Computational Power of QAC0 with Barely Superlinear Ancillae

Cited by in corpus (5)

• Quantum Algorithms for the Pathwise Lasso
• Hybrid Quantum-Classical Algorithm For Robust Optimization via Stochastic-Gradient Online Learning
• Achieving computational gains with quantum error-correction primitives: Generation of long-range entanglement enhanced by error detection
• Des-q: a quantum algorithm to provably speedup retraining of decision trees
• Unified Architecture for Quantum Lookup Tables