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

• URL: http://arxiv.org/abs/2308.08539v3
• Date: Thu, 14 Nov 2024 18:37:15 GMT
• Title: Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Authors: Jonathan Allcock, Jinge Bao, Joao F. Doriguello, Alessandro Luongo, Miklos Santha,
• Abstract summary: We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. We obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices.
• Score: 40.56175933029223
• License:
• 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\rangle|b\rangle\mapsto |x\rangle|b\oplus f(x)\rangle$ 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\rangle$, 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.

Related papers

• Efficient Fault-Tolerant Single Qubit Gate Approximation And Universal Quantum Computation Without Using The Solovay-Kitaev Theorem [0.0]
  A recent improvement of the Solovay-Kitaev theorem implies that to approximate any single-qubit gate to an accuracy of $epsilon > 0$ requires $textO(logc[1/epsilon)$ quantum gates with $c > 1.44042$. Here I give a partial answer to this question by showing that this is possible using $textO(log[/epsilon] loglog[/epsilon] cdots)$ FT gates chosen from a finite set depending on the value of $
  arXiv  Detail & Related papers  (2024-06-07T11:21:05Z)
• Quantum Circuit for Random Forest Prediction [0.0]
  We present a quantum circuit for a binary classification prediction algorithm using a random forest model. One of our goals is reducing the number of basic quantum gates (elementary gates)
  arXiv  Detail & Related papers  (2023-12-28T08:07:11Z)
• Polylogarithmic-depth controlled-NOT gates without ancilla qubits [0.0]
  Controlled operations are fundamental building blocks of quantum algorithms. Decomposing $n$-control-NOT gates into arbitrary single-qubit and CNOT gates is a crucial but non-trivial task.
  arXiv  Detail & Related papers  (2023-12-20T17:23:11Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(sqrtN k)$ of quantum queries.
  arXiv  Detail & Related papers  (2023-02-20T19:11:44Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Quantum supremacy and hardness of estimating output probabilities of quantum circuits [0.0]
  We prove under the theoretical complexity of the non-concentration hierarchy that approximating the output probabilities to within $2-Omega(nlogn)$ is hard. We show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including trivial circuit with identity gates.
  arXiv  Detail & Related papers  (2021-02-03T09:20:32Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)

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.