Constant-depth circuits for Uniformly Controlled Gates and Boolean
functions with application to quantum memory circuits
- URL: http://arxiv.org/abs/2308.08539v2
- Date: Thu, 14 Dec 2023 09:52:40 GMT
- Title: Constant-depth circuits for Uniformly Controlled Gates and Boolean
functions with application to quantum memory circuits
- Authors: Jonathan Allcock, Jinge Bao, Jo\~ao 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: 42.979881926959486
- License: http://creativecommons.org/publicdomain/zero/1.0/
- 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{n}\log\log{n})$ ancillae and $O(n\log{n})$ Fan-Out gates or
$O(n\log{n})$ ancillae and $6$ Global Tunable gates. On the other hand, the
implementation based on Boolean analysis requires only $2$ Global Tunable gates
at the expense of $O(n^2)$ 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.