We provide a method for compiling approximate multicontrolled single qubit gates into quantum circuits. Without ancilla qubits, the total number of elementary gates to decompose an n-qubit multicontrolled gate is proportional to 32n elementary operations. The proposed decomposition depends on an optimization technique that minimizes the CNOT gate count for multitarget and multicontrolled CNOT and SU(2) gates. We also provide an approximate decomposition with ancilla qubits with lower-circuit complexity. Computational experiments show the reduction of CNOT gates when multicontrolled U(2) gates are applied. As multicontrolled single-qubit gates serve as fundamental components of quantum algorithms, the proposed decomposition offers a comprehensive solution that can significantly decrease the count of elementary operations employed in quantum computing applications.
We provide a method for compiling approximate multicontrolled single qubit gates into quantum circuits. Without ancilla qubits, the total number of elementary gates to decompose an n-qubit multicontrolled gate is proportional to 32n elementary operations. The proposed decomposition depends on an optimization technique that minimizes the CNOT gate count for multitarget and multicontrolled CNOT and SU(2) gates. We also provide an approximate decomposition with ancilla qubits with lower-circuit complexity. Computational experiments show the reduction of CNOT gates when multicontrolled U(2) gates are applied. As multicontrolled single-qubit gates serve as fundamental components of quantum algorithms, the proposed decomposition offers a comprehensive solution that can significantly decrease the count of elementary operations employed in quantum computing applications.
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 implementingn-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 ann-qubit multicontrolled SU(2) gate requires a circuit with a number of CNOT gates proportional to28n. In this work, we present a new decomposition ofn-qubit multicontrolled SU(2) gates that require a circuit with a number of CNOT gates proportional to20nand proportional to16nif 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.
The synthesis of quantum operators involves decomposing general quantum gates into the gate set supported by a given quantum device. Multi-controlled gates are essential components in this process. In this work, we present an improved decomposition of multi-controlled NOT gates with logarithmic depth using a single ancilla qubit while reducing the ancillary resource requirements compared to previous work. We further introduce a relative-phase multi-controlled NOT gate that eliminates the need for ancillas. Building on these results, we optimize a previously proposed decomposition of multi-target, multi-controlled special unitary SU(2) gates by identifying the presence of a conditionally clean qubit. Additionally, we introduce the best-known decomposition of multi-controlled approximate unitary U(2) gates, which do not require ancilla qubits. This approach significantly reduces the overall circuit depth and CNOT count while preserving an adjustable error parameter, yielding a more efficient and scalable solution for synthesizing large controlled-unitary gates. Our method is particularly suitable for both NISQ and fault-tolerant quantum architectures. All software developed in this project is freely available.
Multi-controlled gates are fundamental components in the design of quantum algorithms, where efficient decompositions of these operators can enhance algorithm performance. The best asymptotic decomposition of an n-controlled X gate with one borrowed ancilla into single qubit and CNOT gates produces circuits with degree 3 polylogarithmic depth and employs a divide-and-conquer strategy. In this paper, we reduce the number of recursive calls in the divide-and-conquer algorithm and decrease the depth of n-controlled X gate decomposition to a degree of 2.799 polylogarithmic depth. With this optimized decomposition, we also reduce the depth of n-controlled SU(2) gates and approximate n-controlled U(2) gates. Decompositions described in this work achieve the lowest asymptotic depth reported in the literature. We also perform an optimization in the base of the recursive approach. Starting at 52 control qubits, the proposed n-controlled X gate with one borrowed ancilla has the shortest circuit depth in the literature. One can reproduce all the results with the freely available open-source code provided in a public repository.
A large-scale quantum circuit can be partitioned into multiple subcircuits through circuit cutting, where each subcircuit is executed multiple times and the expectation value of the original circuit is reconstructed by classical post-processing from their measurement (sampling) results. In this process, appropriate cut locations are identified after the user-designed quantum circuit, including multi-qubit gates that act on three or more qubits, has been decomposed into single-qubit gates and two-qubit gates such as the CNOT gate. Here, we present a method for reducing the sampling overhead, which refers to the increase in the number of samples required due to the cutting process, by modifying the decomposition strategy of multi-qubit gates. Using MCX and CCCX gates as representatives of multi-qubit gates, we demonstrate that the proposed decomposition method, which introduces a small number of ancilla qubits according to the identified cut locations, effectively decreases the sampling overhead.
Multi-controlled unitary gates have been a subject of interest in quantum computing since its inception, and are widely used in quantum algorithms. The current state-of-the-art approach to implementing n-qubit multi-controlled gates 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 a special unitary SU(2). The most widely-used decomposition of an n-qubit multi-controlled 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 multi-controlled SU(2) gates that requires a circuit with a number of CNOT gates proportional to 20n, and proportional to 16n if the SU(2) gate has at least one real-valued diagonal. This new approach significantly improves 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.
We present an implementation of multicontrolled () quantum gates that provides significant reductions of cost compared to state-of-the-art methods. The operator applied on the target qubit is a unitary, special unitary, or the Pauli X operator (multicontrolled Toffoli), and requires one clean ancilla, no ancilla, or one dirty ancilla, respectively. We generalize our methods for any number of target qubits, and provide further cost reductions if additional ancilla qubits are available. For each type of gate, we provide implementations for unrestricted (all-to-all) connectivity and for linear-nearest-neighbor (LNN) connectivity. All of the methods use a linear cost of gates from the Clifford+ T (fault-tolerant) set. In the context of LNN architecture, the cost and depth of our circuits scale linearly irrespective of the position of the qubits on which the gate is applied. Our methods directly improve the compilation process of many quantum algorithms, providing optimized circuits. Given the scale of our improvements, for example, the quadratic-to-linear controlled- count for LNN, they will naturally result in a large reduction of errors.