We consider the task of breaking down a quantum computation given as an isometry into C-NOTs and single-qubit gates, while keeping the number of C-NOT gates small. Although several decompositions are known for general isometries, here we focus on a method based on Householder reflections that adapts well in the case of sparse isometries. We show how to use this method to decompose an arbitrary isometry before illustrating that the method can lead to significant improvements in the case of sparse isometries. We also discuss the classical complexity of this method and illustrate its effectiveness in the case of sparse state preparation by applying it to randomly chosen sparse states.
The preparation of quantum states is one of the most fundamental tasks in quantum computing, and a key primitive in many quantum algorithms. Of particular interest to areas such as quantum simulation and linear-system solvers are sparse quantum states, which contain only a small number
s of non-zero computational basis states compared to a generic state. In this work, we present an approach that prepares
s-sparse states on
n qubits, reducing the number of Toffoli gates required compared to prior art. We work in the established framework of first preparing a dense state on a
⌈log(s)⌉-qubit sub-register, and then mapping this state to the target state via an isometry, with the latter step dominating the cost of the full algorithm. The speed-up is achieved by designing an efficient algorithm for finding and implementing the isometry. The worst-case Toffoli cost of our isometry circuit, which may be viewed as a batched version of an approach by Malvetti et al., is essentially
2s for sufficiently large values of
n, yielding roughly a
log(s)/2 improvement factor over the state-of-the-art. In numerical benchmarks on randomly chosen states, the cost is closer to
s. With the improved isometry circuit, we examine the dense-state preparation step and present ways to optimize the joint cost of both steps, particularly in the case of target states with purely real coefficients, by outsourcing some sub-tasks from the dense-state preparation to the isometry.
Initializing an isometry in a quantum circuit is a fundamental yet challenging task, espe- cially when aiming for efficient state preparation and resource optimization. In this work, we present a comparative analysis of the Householder Decomposition for isometry implementation, leveraging three distinct state preparation methods starting from the original Pivot method and extending the study to two additional strategies: Merge and Low Rank. The study investigates how each method impacts the performance of the isometry decomposition, focusing on key metrics such as CNOT gate count and circuit depth. To provide a comprehensive evaluation, we examine variations in matrix size and sparsity levels, capturing the effects of structural complexity on resource requirements. Our results reveal that the Merge state preparation method generally outperforms the other two approaches, particularly in terms of scalability and gate efficiency. Building upon these findings, we further compare the best-performing method, Merge, with the state-of- the-art isometry decomposition implementation available in Qiskit, a widely used quantum computing framework. The analysis demonstrates that, for isometries involving up to 6 qubits, Qiskit’s implementation exhibits superior performance. However, beyond this threshold, our proposed decomposition method proves more effective, especially for highly sparse isometries or those characterized by a smaller number of columns. This work highlights the potential for optimizing isometry decompositions in scenarios where sparsity and structural constraints are critical factors. These findings contribute to advancing state preparation techniques and offer insights into improving the efficiency of quantum circuits for applications in quantum information processing.
We consider the decomposition of arbitrary isometries into a sequence of single-qubit and controlled-not (cnot) gates. In many experimental architectures, the cnot gate is relatively costly and hence we aim to keep the number of these as low as possible. We derive a theoretical lower bound on the number of cnot gates required to decompose an arbitrary isometry from
m to
n qubits and give three explicit gate decompositions that achieve this bound up to a factor of about 2 in the leading order. We also perform some further optimizations for certain cases where
m and
n are small. In addition, we show how to apply our result for isometries to give a decomposition scheme for an arbitrary quantum operation via Stinespring's theorem and derive a lower bound on the number of cnot gates in this case too. These results will have an impact on experimental efforts to build a quantum computer, enabling them to go further with the same resources.
Quantum state preparation is a fundamental and significant subroutine in quantum computing. In this paper, we conduct a systematic investigation on the circuit size (the total count of elementary gates in the circuit) for sparse quantum state preparation. A quantum state is said to be
d-sparse if it has only
d non-zero amplitudes. For the task of preparing an
n-qubit
d-sparse quantum state, we obtain the following results: \textbf{Without ancillary qubits:} Any
n-qubit
d-sparse quantum state can be prepared by a quantum circuit of size
O(lognnd+n) without using ancillary qubits, which improves the previous best results. It is asymptotically optimal when
d=poly(n), and this optimality holds for a broader scope under some reasonable assumptions. \textbf{With limited ancillary qubits:} (i) Based on the first result, we prove for the first time a trade-off between the number of ancillary qubits and the circuit size: any
n-qubit
d-sparse quantum state can be prepared by a quantum circuit of size
O(log(n+m)nd+n) using
m ancillary qubits for any
m∈O(logndnd+n). (ii) We establish a matching lower bound
Ω(log(n+m)nd+n) under some reasonable assumptions, and obtain a slightly weaker lower bound
Ω(log(n+m)+logdnd+n) without any assumptions. \textbf{With unlimited ancillary qubits:} Given arbitrary amount of ancillary qubits available, the circuit size for preparing
n-qubit
d-sparse quantum states is
Θ(logndnd+n).
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.