Quantum circuit complexity is one of the most crucial factors to take into consideration in quantum computation. It provides an account of computation with a minimal number of steps and time needed in order to implement a given unitary. One can associate quantum circuit complexity with the complexity involved in the preparation of a given quantum fiducial state from its initial state. For instance, a quantum state generated by a quantum chaotic Hamiltonian evolution will be highly complex, if the quantum circuit preparing it requires a lot of time on a quantum computer. When determining the overall complexity of a quantum circuit, an essential factor that needs to be accounted for, is the cost of such circuit while keeping into consideration the circuit design.
While the above factors can contribute to analyzing the complexity of quantum circuits, it is not trivial to calculate these factors quantitatively. Although there are (classical) algorithmic procedures that can find a decomposition of a unitary into a quantum circuit including Clifford and T-gates, which can be done in exponential run-time in circuit size, computing the complexity still requires optimization over these decompositions. During such decompositions, cancellations of gates occur that make the impact of a unitary gate to be partially compensated by the application of a following similar gate. One potential correlation to explore is whether the entanglement (created by quantum gates) has any impact on circuit complexity or at the cost of a unitary.
The author in this work analyzes such a relationship when both the entanglement of a state and the cost of a unitary take small values, based on how values of entangling power of quantum gates add up. It provides a simple lower bound for the cost of a quantum circuit that is tight for small values of the cost. The idea of these bounds comes from the entanglement capabilities of the quantum gates. Quantum gates that are close to the identity in operator norm have little capability to create entanglement from product states. It is however theorized that their contribution of entanglement to a given entangled state is also very little. The bound presented in this work implies that, assuming linear growth of entanglement entropies with time, cost also increases linearly.
Furthermore, for Gaussian continuous-variable systems, there is a small incremental entanglement bound as well as a harmonic equivalent of the above relationship between entanglement and quantum circuit cost. This bound can also be applied both to spin systems and Gaussian bosonic continuous-variable settings, which are important in approximating non-interacting bosonic theories. A noteworthy observation is that when a quantum many-body system undergoes non-equilibrium dynamics leading to a linear increase in the entanglement entropy, the quantum state complexity also increases.
An important result from the presented bounds, is that one can derive the required depth of a quantum circuit that can produce a given entanglement pattern in a desired final state, for either pure or mixed states. The presented bounds can also help in assessing the computational performance of analog quantum simulators and their direct comparison to their digital counterparts. One can argue that for a precisely defined computational effort, both analog and digital quantum simulators can achieve similar results. These simple bounds can provide a useful and versatile tool in various studies of such comparisons and relations.