{"id":172,"date":"2005-02-13T16:18:51","date_gmt":"2005-02-13T06:18:51","guid":{"rendered":"http:\/\/michaelnielsen.org\/?p=172"},"modified":"2005-02-13T16:18:51","modified_gmt":"2005-02-13T06:18:51","slug":"geometry-and-quantum-circuits","status":"publish","type":"post","link":"https:\/\/michaelnielsen.org\/blog\/geometry-and-quantum-circuits\/","title":{"rendered":"Geometry and quantum circuits"},"content":{"rendered":"

My major scientific interest for the past few months has been in using ideas from differential geometry to develop insight into quantum computation. I’ve just posted a paper (pdf)<\/a> at the preprint archive on the subject. This post is a somewhat technical overview of what’s done in the paper. The post will, I hope, make a fair bit of sense to people who know something about the technical details of quantum computation, but latter parts will be hard going for other people.<\/p>\n

I’ve also posted a talk (Powerpoint)<\/a> I gave a couple of weeks ago on the subject.<\/p>\n

Update (2005\/02\/19):<\/b> Some typos in my talk fixed, with thanks to Wim van Dam.<\/p>\n

One of the most notoriously difficult problems in computation, either quantum or classical, is to figure out the minimal<\/em> circuit that can be used to compute some function.<\/p>\n

Even the easier problem of proving a lower bound<\/em> on the size of the minimal circuit seems to be intractable for most interesting functions – this is why famous problems like P<\/b> vs. NP<\/b> are so hard.<\/p>\n

Inspired by geometric control theory and ideas from Riemannian and Finsler geometry, I’ve been spendng my time trying to develop a general approach to the proof of lower bounds on circuit size.<\/p>\n

The technical details are lengthy, but the basic motivating ideas are fairly simple.<\/p>\n

The starting point is the observation that what we’re really trying to do is minimize a function (number of gates) over the space of quantum circuits computing the desired function.<\/p>\n

As any high school maths student can tell you, minimizing a discrete function like “number of gates” is a heck of a lot harder than minimizing a smooth function, since we can use the powerful tools of the differential calculus to solve the latter problem.<\/p>\n

The first thing done in the paper is therefore to replace the discrete problem of finding a minimizing quantum circuit by a more smoothly formulated problem, which I call the Hamiltonian control problem<\/em>. Basically, we embed the (discrete) circuit optimization problem inside a smoothed version which lets us use the tools of the calculus.<\/p>\n

This smoothed problem turns out to be essentially a problem of finding “shortest paths” on some suitable geometric space, in this case, the space of n-qubit unitary operations.<\/p>\n

The upshot is that we can get a lower bound<\/em> on the minimal circuit size by computing the length of the minimal geodesic between the desired unitary quantm computation, U, and the identity operation, I, where length is defined by some suitable metric structure.<\/p>\n

(An interesting technical point is that the right type of metric structure to use is a so-called Finsler<\/em> metric structure, which generalizes the Riemannian metrics familiar to physicists by replacing quadratic forms by a more general norm function.)<\/p>\n

Now the calculus comes into play. By using the calculus of variations, it’s possible to derive a second order differential equation (the “geodesic equation”) describing the geodesics of the metric. Because the geodesic equation is second order, once an initial position and velocity are set, the remainder of the geodesic is completely determined.<\/p>\n

This is in sharp 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.<\/p>\n

This contrast makes me think this approach is really worth pursuing as an approach to quantum circuit lower bounds.<\/p>\n

That’s the broad conceptual picture of the program. I’ve also made some technical progress on implementing the program, which I won’t try to describe here, beyond quoting the second half of the abstract:<\/p>\n

\nIn this paper we construct several Finsler metrics whose minimal length geodesics provide lower bounds on quantum circuit size, and 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.\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"

My major scientific interest for the past few months has been in using ideas from differential geometry to develop insight into quantum computation. I’ve just posted a paper (pdf) at the preprint archive on the subject. This post is a somewhat technical overview of what’s done in the paper. The post will, I hope, make… Continue reading Geometry and quantum circuits<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-172","post","type-post","status-publish","format-standard","hentry","category-3","entry"],"_links":{"self":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/172","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/comments?post=172"}],"version-history":[{"count":0,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/172\/revisions"}],"wp:attachment":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/media?parent=172"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/categories?post=172"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/tags?post=172"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}