A geometric approach to quantum circuit lower bounds

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