Quantum circuits naturally implement unitary operations on input quantum states. However, non-unitary operations can also be implemented through "block encodings", where additional ancilla qubits are introduced and later measured. While block encoding underlies a host of well-established theoretical applications, its implementation in practice has been prohibitively expensive for current quantum hardware. In this paper, we present practical and explicit block encoding circuits implementing matrix polynomial transformations of a target matrix. With standard approaches, block-encoding a degree-d matrix polynomial requires a circuit depth scaling as d times the depth for block-encoding the original matrix alone. By leveraging the recently introduced Fast One-Qubit Controlled Select Linear Combination of Unitaries (FOQCS-LCU) framework, we show that the additional circuit-depth overhead required for encoding matrix polynomials can be reduced to scale linearly in d with no dependence on system size or the cost of block encoding the original matrix. Moreover, we demonstrate that the FOQCS-LCU circuits and their associated matrix polynomial transformations can be controlled with negligible overhead, enabling efficient applications such as Hadamard tests. Finally, we provide explicit hardware-efficient circuits for representative non-unitary operators, namely quantum spin models, together with detailed non-asymptotic gate counts and circuit depths.
Multicontrolled unitary gates have been a subject of interest in quantum computing since their conception and are widely used in quantum algorithms. The current state-of-the-art approach to implementing
n-qubit multicontrolled gates with a single target without relying on auxiliary qubits or approximate results involves the use of a quadratic number of single-qubit and CNOT gates. However, linear solutions are possible for the case where the controlled gate is special unitary, SU(2). The decomposition of an
n-qubit multicontrolled SU(2) gate requires a circuit with a number of CNOT gates proportional to
28n. In this work, we present a new decomposition of
n-qubit multicontrolled SU(2) gates that require a circuit with a number of CNOT gates proportional to
20nand proportional to
16nif the SU(2) gate has at least one real-valued diagonal. The proposed algorithms produce the most efficient known circuits and improve the existing algorithm by reducing the number of CNOT gates and the overall circuit depth. As an application, we show the use of this decomposition for sparse quantum state preparation. Our results are further validated by demonstrating a proof of principle on a quantum device accessed through quantum cloud services.
In this article we study n-qubit quantum gates which may be represented as direct sums of two-dimensional unitary operators. We call this class of gates uniformly controlled one-qubit gates. We present a quantum circuit which implements any gate of this type using 2^{n-1} - 1 controlled-NOT gates, 2^{n-1} one-qubit gates and a single n-qubit diagonal gate. The construction is based on a modified version of the so-called quantum multiplexor circuit. We illustrate the versatility of the uniformly controlled gates by applying them to the decomposition of a general n-qubit gate and an n-qubit state-preparation procedure. Moreover, we study the implementation of these circuits using only nearest-neighbor gates and give the worst-case one-qubit and CNOT gate counts for all of the aforementioned applications. In all four cases, the proposed method either improves or achieves the previously reported upper bounds for the gate counts.
We introduce a scheme for realizing arbitrary controlled-unitary operations in a two-qubit system. If the $2\ifmmode\times\else\texttimes\fi{}2$ unitary matrix is special unitary (has unit determinant), the controlled-unitary gate operation can be realized in a single pulse operation. The pulse in our scheme will constitute varying one of the parameters of the system between an arbitrarily maximum and a ``calculated'' minimum value. This parameter will constitute the variable parameter of the system while the other parameters, which include the coupling between the two qubits, will be treated as fixed parameters. The values of the parameters are what we solve for using our approach in order to realize an arbitrary controlled-unitary operation. We further show that the computational complexity of the operation is no greater than that required for a controlled-NOT (CNOT) gate. Since conventional schemes realize a controlled-unitary operation by breaking it into a sequence of single-qubit and CNOT gate operations, our method is an improvement because we not only require less time duration, but also fewer control lines to implement the same operation. To demonstrate improvement over other schemes, we show, as examples, how two controlled-unitary operations, one being the controlled-Hadamard gate, can be realized in a single pulse operation using our scheme. Furthermore, our method can be applied to a wide range of coupling schemes and can be used to realize gate operations between two qubits coupled via Ising, Heisenberg, and anisotropic interactions.
In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of
2. It also reduces the total number of cnot gates from
2n to
24232n in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from
11 cnot gates to
9 and the depth from
11 to
5 steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant
δ>0, it
ε-approximates an arbitrary single-qubit gate using
O(log1+δ(1/ε)) clean ancillae, Hadamard and
T single-qubit gates,
O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard,
T, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth
O(loglog(1/ε)), and we prove a matching
Ω(loglog(1/ε))-depth lower bound. Overall, we establish that
Θ(loglog(1/ε))-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis.
These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-
d QAC circuit can be simulated in depth
O(d) using only Hadamard,
X, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity
∈/QAC
0 to proving a Parity lower bound against circuits consisting only of Hadamard,
X, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.