Universal circuits can be viewed as general-purpose simulators for central classes of circuits and can be used to capture the computational power of the circuit class being simulated. We define and construct quantum universal circuits which are efficient and has very little overhead in simulation. For depth we construct universal circuits whose depth is the same order as the circuits being simulated. For size, there is a log factor blow-up in the universal circuits constructed here which is nearly optimal.
A quantum circuit is a model for Hilbert space computation in which a computation is a sequence of quantum spaces, which are reversible transformations on a quantum mechanical space of an n-bit register. This analogous structure is referred to as an n-space register. We define and can build efficient depth-universal and almost size-universal quantum circuits Such circuits can be viewed as general purpose simulators for central classes of quantum circuits and can be used to capture the computational power of the circuit class being simulated. For depth we construct universal circuits whose depth is the same order as the circuits being simulated. For size, there is a log factor blow-up in the universal circuits constructed here. The architecture scalability afforded by recent proposals of a large-scale photonic-based quantum space computer allows us to move on to a discussion of High performance Hilbert quantum circuits.
Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions:
general total Boolean functions with output size
b: with
1≤m≤Θ(n2n) ancilla, size
O(log(n+m)b2n), depth
O(n+mb2n);
partial Boolean functions of effective support size
d and output size
b: with
Θ(logd)≤m≤Θ(d) ancilla, size
O(nlogd+bd), depth
O(n+mnlognlogd+logn+md(logd+blogm));
sparse Boolean functions of true input size
d: with
Θ(logn+logd)≤m≤Θ(logdnd) ancilla, size
O(n2logd+log(logd+m/n)nd), depth
O(n+mn2lognlogd+logn+mnd).
All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.
Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored.
We prove an explicit depth hierarchy theorem for
QNC0. For each
d≥12, we construct a family of two-round interactive problems on which no depth-
(d−1) quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than
d by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every
d, yielding a hierarchy of problems that show unconditional quantum advantage of
QNC0 over
NC0.
A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits.
These results show that increasing depth strictly increases computational power within
QNC0, establishing a genuinely quantum hierarchy.
We consider recent works on the simulation of quantum circuits using the formalism of matrix product states and the formalism of contracting tensor networks. We provide simplified direct proofs of many of these results, extending an explicit class of efficiently simulable circuits (log depth circuits with 2-qubit gates of limited range) to the following: let C be any poly sized quantum circuit (generally of poly depth too) on n qubits comprising 1- and 2- qubit gates and 1-qubit measurements (with 2-qubit gates acting on arbitrary pairs of qubit lines). For each qubit line j let D_j be the number of 2-qubit gates that touch or cross the line j i.e. the number of 2-qubit gates that are applied to qubits i,k with i \leq j \leq k. Let D=max_j D_j. Then the quantum process can be classically simulated in time n poly(2^D). Thus if D=O(log n) then C may be efficiently classically simulated.