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 the use of ancilla qubits? We show that a lower bound on the minimal size is provided by the length of the minimal geodesic between U and the identity, I, where length is defined by a suitable Finsler metric on the manifold SU(2(n)). The geodesic curves on these manifolds have the striking property that once an initial position and velocity are set, the remainder of the geodesic is completely determined by a second order differential equation known as the geodesic equation. This is in contrast with the usual case in circuit design, either classical or quantum, where being given part of an optimal circuit does not obviously assist in the design of the rest of the circuit. Geodesic analysis thus offers a potentially powerful approach to the problem of proving quantum circuit lower bounds. In this paper we construct several Finsler metrics whose minimal length geodesics provide lower bounds on quantum circuit size. For each Finsler metric we give a procedure to compute the corresponding geodesic equation. We also construct a large class of solutions to the geodesic equation, which we call Pauli geodesics, since they arise from isometries generated by the Pauli group. For any unitary U diagonal in the computational basis, we show that: (a) provided the minimal length geodesic is unique, it must be a Pauli geodesic; (b) finding the length of the minimal Pauli geodesic passing from I to U is equivalent to solving an exponential size instance of the closest vector in a lattice problem (CVP); and (c) all but a doubly exponentially small fraction of such unitaries have minimal Pauli geodesics of exponential length.

Geodesics without differential equations: general relativistic calculations for introductory modern physics classes

Introductory courses covering modem physics sometimes introduce some elementary ideas from general relativity, though the idea of a geodesic is generally limited to shortest Euclidean length on a curved surface of two spatial dimensions rather than extremal aging in spacetime. It is shown that Epstein charts provide a simple geometric picture of geodesics in one space and one time dimension and that for a hypothetical uniform gravitational field, geodesics are straight lines on a planar diagram. This means that the properties of geodesics in a uniform field can be calculated with only a knowledge of elementary geometry and trigonometry, thus making the calculation of some basic results of general relativity accessible to students even in an algebra-based survey course on physics.

On the chaotic instability of a nonsliding liquid-filled top with a small spheroidal base via Melnikov-Holmes-Marsden integrals

Chaotic orientations of a top containing a fluid filled cavity are investigated analytically and numerically under small perturbations. The top spins and rolls in nonsliding contact with a rough horizontal plane and the fluid in the ellipsoidal shaped cavity is considered to be ideal and describable by finite degrees of freedom. A Hamiltonian structure is established to facilitate the application of Melnikov-Holmes-Marsden (MHM) integrals. In particular, chaotic motion of the liquid-filled top is identified to be arisen from the transversal intersections between the stable and unstable manifolds of an approximated, disturbed flow of the liquid-filled top via the MHM integrals. The developed analytical criteria are crosschecked with numerical simulations via the 4th Runge-Kutta algorithms with adaptive time steps.

Optimal control, geometry, and quantum computing

We prove upper and lower bounds relating the quantum gate complexity of a unitary operation, U, to the optimal control cost associated to the synthesis of U. These bounds apply for any optimal control problem, and can be used to show that the quantum gate complexity is essentially equivalent to the optimal control cost for a wide range of problems, including time-optimal control and finding minimal distances on certain Riemannian, sub-Riemannian, and Finslerian manifolds. These results generalize the results of [Nielsen, Dowling, Gu, and Doherty, Science 311, 1133 (2006)], which showed that the gate complexity can be related to distances on a Riemannian manifold.