Abstract The basic idea of quantum complexity geometry is to endow the space of unitary matrices with a metric, engineered to make complex operators far from the identity, and simple operators near. By restricting our attention to a finite subgroup of the unitary group, we observe that this idea can be made rigorous: the complexity geometry becomes what is known as a Cayley graph. This connection allows us to translate results from the geometrical group theory literature into statements about complexity. For example, the notion of δ-hyperbolicity makes precise the idea that complexity geometry is negatively curved. We report an exact (in the large N limit) computation of the average complexity as a function of time in a random circuit model.
Abstract The basic idea of quantum complexity geometry is to endow the space of unitary matrices with a metric, engineered to make complex operators far from the identity, and simple operators near. By restricting our attention to a finite subgroup of the unitary group, we observe that this idea can be made rigorous: the complexity geometry becomes what is known as a Cayley graph. This connection allows us to translate results from the geometrical group theory literature into statements about complexity. For example, the notion of δ-hyperbolicity makes precise the idea that complexity geometry is negatively curved. We report an exact (in the large N limit) computation of the average complexity as a function of time in a random circuit model.
Determining the quantum circuit complexity of a unitary operation is closely related to the problem of finding minimal length paths in a particular curved geometry [Nielsen et al, Science 311, 1133-1135 (2006)]. This paper investigates many of the basic geometric objects associated to this space, including the Levi-Civita connection, the geodesic equation, the curvature, and the Jacobi equation. We show that the optimal Hamiltonian evolution for synthesis of a desired unitary necessarily obeys a simple universal geodesic equation. As a consequence, once the initial value of the Hamiltonian is set, subsequent changes to the Hamiltonian are completely determined by the geodesic equation. We develop many analytic solutions to the geodesic equation, and a set of invariants that completely determine the geodesics. We investigate the problem of finding minimal geodesics through a desired unitary, U, and develop a procedure which allows us to deform the (known) geodesics of a simple and well understood metric to the geodesics of the metric of interest in quantum computation. This deformation procedure is illustrated using some three-qubit numerical examples. We study the computational complexity of evaluating distances on Riemmanian manifolds, and show that no efficient classical algorithm for this problem exists, subject to the assumption that good pseudorandom generators exist. Finally, we develop a canonical extension procedure for unitary operations which allows ancilla qubits to be incorporated into the geometric approach to quantum computing.
Determining the quantum circuit complexity of a unitary operation is closely related to the problem of finding minimal length paths in a particular curved geometry [Nielsen et al, Science 311, 1133-1135 (2006)]. This paper investigates many of the basic geometric objects associated to this space, including the Levi-Civita connection, the geodesic equation, the curvature, and the Jacobi equation. We show that the optimal Hamiltonian evolution for synthesis of a desired unitary necessarily obeys a simple universal geodesic equation. As a consequence, once the initial value of the Hamiltonian is set, subsequent changes to the Hamiltonian are completely determined by the geodesic equation. We develop many analytic solutions to the geodesic equation, and a set of invariants that completely determine the geodesics. We investigate the problem of finding minimal geodesics through a desired unitary, U, and develop a procedure which allows us to deform the (known) geodesics of a simple and well understood metric to the geodesics of the metric of interest in quantum computation. This deformation procedure is illustrated using some three-qubit numerical examples. We study the computational complexity of evaluating distances on Riemmanian manifolds, and show that no efficient classical algorithm for this problem exists, subject to the assumption that good pseudorandom generators exist. Finally, we develop a canonical extension procedure for unitary operations which allows ancilla qubits to be incorporated into the geometric approach to quantum computing.
We develop a geometric approach to operator growth and Krylov complexity in many-body quantum systems governed by symmetries. We start by showing a direct link between a unitary evolution with the Liouvillian and the displacement operator of appropriate generalized coherent states. This connection maps operator growth to a purely classical motion in phase space. The phase spaces are endowed with a natural information metric. We show that, in this geometry, operator growth is represented by geodesics, and Krylov complexity is proportional to a volume. This geometric perspective also provides two novel avenues toward computation of Lanczos coefficients, and it sheds new light on the origin of their maximal growth. We describe the general idea and analyze it in explicit examples, among which we reproduce known results from the Sachdev-Ye-Kitaev model, derive operator growth based on SU(2) and Heisenberg-Weyl symmetries, and generalize the discussion to conformal field theories. Finally, we use techniques from quantum optics to study operator evolution with quantum information tools such as entanglement and Renyi entropies, negativity, fidelity, relative entropy, and capacity of entanglement.
Abstract In the geometric approach to defining complexity, operator complexity is defined as the distance in the operator space. In this paper, based on the analogy with the circuit complexity, the operator size is adopted as the metric of the operator space where the path length is the complexity. The typical sectional curvatures of this complexity geometry are positive. It is further proved that the typical sectional curvatures are always positive if the metric is an arbitrary function of operator size, while complexity geometry is usually expected to be defined on negatively curved manifolds. By analyzing the sectional curvatures distribution for the N-qubit system, it is shown that surfaces generated by Hamiltonians of size smaller than the typical size can have negative curvatures. In the large N limit, the form of complexity metric is uniquely constrained up to constant corrections if we require sectional curvatures are of order 1/N2. With the knowledge of states, the operator size should be modified due to the redundant action of operators, and thus is generalized to be state-dependent. Then we use this state-dependent operator size as the metric of the Hilbert space to define state complexity. It can also be shown that in the Hilbert space, 2-surfaces generated by operators of size much smaller than the typical size acting on typical states also have negative curvatures.
Abstract The “quantum complexity” of a unitary operator measures the difficulty of its construction from a set of elementary quantum gates. While the notion of quantum complexity was first introduced as a quantum generalization of the classical computational complexity, it has since been argued to hold a fundamental significance in its own right, as a physical quantity analogous to the thermodynamic entropy. In this paper, we present a unified perspective on various notions of quantum complexity, viewed as functions on the space of unitary operators. One striking feature of these functions is that they can exhibit non-smooth and even fractal behaviour. We use ideas from Diophantine approximation theory and sub-Riemannian geometry to rigorously quantify this lack of smoothness. Implications for the physical meaning of quantum complexity are discussed.
The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high-energy physics.The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state.It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a shortcut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions.To go further, one may study more generic models of complexity growth.We provide a rigorous connection between complexity growth and unitary k-designs, ensembles that capture the randomness of the unitary group.This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity.We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind.Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.