A geometric approach to quantum circuit lower bounds

By Morten Nielsen. Quantum information & computation, 2005

397 citations recorded by the source corpus.

What is the minimal size quantum circuit required to exactly implement a specified n-qubit unitary operation, U, without the use of ancilla qubits? We sbow that a lowerbound on the minimal size is provided by the length of the minimal geodesic between Uand the identity, I, where length is defined by a suitable Finsler metric on the manifoldSU(2n). The geodesic curves on these manifolds have the striking property that oncean initial position and velocity are set, the remMnder of the geodesic is completelydeternfined by a second order differential equation known as the geodesic equation. Thisis in contrast with the usual case in circuit design, either classical or quantum, wherebeing given part of an optimal circuit does not obviously assist in the design of therest of the circuit. Geodesic analysis thus offers a potentially powerful approacb to theproblem of proving quantum circuit lower bounds. In this paper we construct severalFinsler metrics whose minimal length geodesics provide lower bounds on quantum circuitsize. For eacb Finsler metric we give a procedure to compute the corresponding geodesicequation. We also construct a large class of solutions to the geodesic equation, whichwe call Pauli geodesics, since they arise from isometries generated by the Pauli group.For any unitary U diagonal in the computational basis, we sbow that: (a) proposed theminimal length geodesic is unique, it must be a Pauli geodesic; (b) finding the length ofthe minimal Pauli geodesic passing from I to U is equivalent to solving an exponentialsize instance of the closest vector in a lattice problem (CVP); and (c) all but a doublyexponentially small fraction of sucb unit aries have nfinimal Pauli geodesics of exponentiallength.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/d5c7452ea3a6c61e28f03f6c101789f6cf28af39

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

In Computational Theory and Mathematics

Citations in the corpus

Circuit complexity for coherent states (2018, background): “While the precise form of the cost function F is not fixed, there are a number of desirable features for reasonable cost functions [56]: 1) Smoothness, 2) Positivity, 3) Triangle inequality and 4) Positive homogeneity — see also [1, 62].”
Switchbacks and the Bridge to Nowhere (2014, methodology): “However, the methods of [5][6] seems well suited to the study of Hamiltonian systems of the kind that may represent black hole evolution.”
Circuit complexity for free fermions (2018, background): “re constructed by many orthogonal generators, this measure denes a ‘Manhattan metric’ on the relevant submanifold and does not provide the most useful measure to distinguish dierent circuits, e.g., [32,39]. Furthermore, as discussed in [32], the precise value of the complexity depends on the precise”
Second law of quantum complexity (2017, methodology): “5) The complexity metric [8][9] is right-invariant but not left-invariant.”
Quantum complexity and negative curvature (2016, background): “Although we do not fully understand the reasons for this correspondence it most likely has its roots in Nielsen’s geometrized approach to complexity [4, 5, 6].”
Comments on holographic complexity (2016, background): “Perhaps, the techniques developed in [46, 47, 48] or in [49] can provide better insight towards developing such a covariant approach.”
Linear growth of quantum circuit complexity (2021, methodology): “Another opportunity involves Nielsen’s geometric notion of complexity [18, 38, 40, 41], which underlies Brown and Susskind’s conjecture.”
Circuit complexity in fermionic field theory (2018, background): “For our purposes in this paper, it is worth noting that this minimization of the number of gates can be re-interpreted à la Nielsen as a geodesic length minimization in the space of circuits [2].”
Circuit complexity in quantum field theory (2017, background): “Neilsen further argues that for the present problem, a physically reasonable cost function must satisfy a number of desirable features: 2See [41] for another application of Nielsen’s ideas in holography.”
On the evolution of operator complexity beyond scrambling (2019, background): “Complexity can then be defined as the size of the smallest circuit or tensor network which approximates the state, given some prescribed set of gates or fundamental tensors (see for instance [4, 5]).”
Qudits and High-Dimensional Quantum Computing (2020, background): “This allow us to define a Riemannian geometry on the space of unitary operations [122].”