This week the scientific advisory board of the CQT is coming to town, so we’re having lots and lots of talks.

Right now Michele Mosca, deputy director of the Institute for Quantum Computing in Waterloo, Canada, is speaking about “Trends in Quantum Information Processing” from a computer science / mathematics perspective.

(Why mathematics? He says he will always consider himself a mathematician…)

#### Alice and Bob

Mosca began by noting some of the cultural / linguistic differences that become important in large interdisciplinary collaborations. For example, computer scientists like to talk about people named Alice and Bob playing bizarre games. These games are usually an attempt to distill some aspect of a hard problem into a simple story.

#### Impossibility

Mosca also made a remark on “impossibility”. Namely: proofs that things are impossible, often called “no-go theorems”, are very important, but we shouldn’t overinterpret them. Just because one approach to doing something doesn’t work, doesn’t mean we can’t do it! From an optimistic viewpoint, no-go theorems simply tell us what assumptions we need to get around. There is, however, a difference between optimism and insanity.

For example: *“We can’t build a quantum computer because of decoherence…”*

Knill, Laflamme and Milburn initially set out to prove that linear optics alone would not give universal quantum computer… but then they discovered it *could*.

• E. Knill, R. Laflamme, and G. J. Milburn, A scheme for efficient quantum computation with linear optics, *Nature* **409** (2001), 46. Also see their paper Efficient linear optics quantum computation on the arXiv.

Another example: *“Quantum *black-box* algorithms give at most a polynomial speedup for *total* functions…”*

If this result — proved by whom? — had been discovered before Shor’s algorithm, it might have discouraged Shor from finding this algorithm. But his algorithm involves a *partial* function.

Yet another: *“Nuclear magnetic resonance quantum computing is not scalable…”*

So far each argument for this can be gotten around, though nobody knows how to get around *all* of them simultaneously. Attempts to do this have led to important discoveries.

#### From theory to practice

Next, Mosca showed a kind of flow chart. Abstract algorithms spawn various models of quantum computation: circuit models, measurement-based models, adiabatic models, topological models, continuous-time models, cellular automaton models, and so on. These spawn specific architectures for (so far hypothetical) quantum computers; a lot of work still needs to be done to develop *fault-tolerant* architectures. Then come specific physical realizations that might implement these architectures: involving trapped ions, photon qubits, superconducting circuit qubits, spin qubits and so on. We’re just at the beginning of a long path.

#### A diversity of quantum algorithms

There are still lots of people who say there are just two interesting quantum algorithms:

• Shor’s algorithm (for factoring integers in a time that’s polynomial as a function in their number of digits), and

• Grover’s algorithm for searching lists in a time that’s less than linear as a function of the number of items in the list.

Mosca said:

The next time you hear someone say this, punch ’em in the head!

For examples of many different quantum algorithms, see Stephen Jordan’s ‘zoo’, and this paper:

• Michele Mosca, Quantum algorithms.

Then Mosca discussed three big trends…

#### 1. Working with untrusted quantum apparatus

This trend started with:

• Artur Ekert, Quantum cryptography based on Bell’s theorem,

*Phys. Rev. Lett.* **67** (1991 Aug 5), 661-663.

Then:

• Dominic Mayers and and Andrew Yao, Quantum cryptography with imperfect apparatus.

And then much more, thanks in large part to people at the CQT! The idea is that if you have a quantum system whose behavior you don’t entirely trust, you can still do useful stuff with it. This idea is related to the subject of multi-prover interactive proofs, which however are studied by a different community.

This year some of these ideas got implemented in an actual experiment:

• S. Pironio, A. Acin, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe, Random numbers certified by Bell’s theorem, *Nature* **464** (2010), 1021.

(Yay! Someone who had the guts to put a paper for *Nature* on the arXiv!)

#### 2. Ideas from topological quantum computing

The seeds here were planted in the late 1990s by:

• Michael Freedman, P/NP, and the quantum field computer,

*Proc. Natl. Acad. Sci. USA* **95** (1998 January 6), 98–101.

This suggested that a topological quantum computer could efficiently compute the Jones polynomial at certain points — a #P-hard problem. That would mean quantum computers can solve NP problems in polynomial time! But it turned out that limitations in precision prevent this. With a great sigh of relief, computer scientists decided they didn’t need to learn topological quantum field theory… but then came:

• A. Kitaev, Fault-tolerant quantum computation by anyons, *Ann. Phys.* **303** (2003), 2-30.

This sort of computer may or may not ever be built, but it’s very interesting either way. And in 2005, Raussendorf, Harrington and Goyal used ideas from topological quantum computing to build fault-tolerance into another approach to quantum computing, based on “cluster states”:

• Robert Raussendorf, Jim Harrington, and Kovid Goyal, Topological fault-tolerance in cluster state quantum computation, 2007.

Subsequently there’s been a huge amount of work along these lines. (Physics junkies should check out the Majorana fermion codes of Bravyi, Leemhuis and Terhal.)

#### 3. Semidefinite programming

The seeds here were planted about 10 years ago by Kitaev and Watrous. There’s been a wide range of applications since then. If you search quant-ph for abstracts containing the buzzword “semidefinite” you’ll get almost a hundred hits!

So what is semidefinite programming? It’s a relative of linear programming, an optimization method that’s widely used in microeconomics and the management of production, transportation and the like. I don’t understand it, but I guess it’s like a quantum version of linear programming!

I can parrot the definition:

A **semidefinite program** is a triple . Here is a linear map that sends linear operators on some Hilbert space to linear operators on some Hilbert space . Such a linear map is called a superoperator, since it operates on operators! We assume takes *self-adjoint* operators to *self-adjoint* operators. What about and ? They are self-adjoint operators on and , respectively.

This data gives us two problems:

**Primal problem:** find , a positive semidefinite operator on that minimizes subject to the constraint such that .

**Dual problem:** find , a positive semidefinite operator on Y that maximizes subject to the constraint .

This should remind you of duality in linear programming. In linear programming, the dual of the dual problem is the original ‘primal’ problem! Also, if you know the solution to either problem, you know the solution to both. Is this stuff true for semidefinite programming too?

Example: given a bunch of density matrices, find an optimal bunch of measurements that distinguish them.

Example: ‘Quantum query algorithms’ are a generalization of Grover’s search algorithm. Reichardt used semidefinite programming to show there is always an optimal algorithm that uses just 2 reflections:

• Ben W. Reichardt, Reflections for quantum query algorithms.

There are lots of other trends, of course! These are just a few. Mosca apologized to anyone whose important work wasn’t mentioned, and I apologize even more, since I left out a lot of what he said….

In regard to the

boldfacedclaim…… was this result ever published? Skimming through the titles and abstracts of the 26 papers that the Science Citation Index lists as citing the above paper, none obviously looked to me like proofs of unphysically stringent accuracy requirements for topological field theory quantum computers to solve #P hard problems.

Or, are you referring to the discussion of accuracy that Freedman himself makes in this article? (I ask because that I always interpreted as him saying it was an open question whether or not an implementable quantum computer could have adequate accuracy. Am I wrong?)

Thanks.

Unfortunately I am not the one who can answer your question; I was just reporting Mosca’s talk. It’s an interesting question. Let’s hope that someone reading this blog can answer it.

I finally succeeded in cornering Michele and asking him your question.

Michele said Freedman hadn’t made any

mistakein his paper: he had merely left open the question whether an implementable topological quantum computer could have enough accuracy to solve #P-hard problems. Later it became clear that they do not. But Michele said he didn’t know whether this result had been published: he had only heard it from a colleague.Thank you very much John for cornering Michele and asking him!

Through my own research since asking the question, I have some further thoughts on the issue. Since I have a deep neurotic drive for completeness, I divide my comments into two versions:

I’ve since come across the topological quantum computing lecture notes of one of Freedman’s frequent co-authors, Zhenghan Wang:

Zhengfan Wang,

Topological Quantum Computation, CBMS Regional Conference Series in Mathematics, Number 112 [American Mathematical Society: Providence, RI 2010].Most of it is freely viewable* on Google Books, and most conveniently this free portion includes the entirety of Wang’s review of the matters pertinent to my question.

Chapter 3: Approximation of the Jones Polynomial

This chapter nicely summarizes the case that what the naive** type of topological quantum algorithm Freedman proposed in 1998 actually accomplishes is the approximation of the Jones polynomial to within an additive error ε in time O[poly(1/ε)]. Alas, as Freedman already laid out in his original 1998 proposal, one would need to produce such an approximation exponentially more quickly — that is, in time O[polylog(1/ε)] — in order to solve #P-hard problems in polynomial time. Of course, the O[poly(1/ε)] result is nothing to be sneezed at: it suffices to reproduce any polynomial time quantum computation — that is, it’s BQP-complete — and it’s superpolynomially faster than the best known classical algorithm.

Footnotes:

* Annoyingly, the freely viewable part does not include the bibliography. However, I reproduce the relevant portion of Wang’s bibliography below.

** I say “naive” since all one’s doing (!) is directly implementing or computationally simulating a physical system obeying a SU(2) Chern-Simons theory and determining the expectation values of certain system observables by just directly measuring those observables as accurately as one can. There’s no additional quantum dynamics/quantum information processing before measurement.

My fuller understanding of the chronology is as follows (NB: references follow Wang’s abbreviations):

Freedman’s 1998 Proc. Nat. Acad. Sci. paper that you reference above [Fr1] made 2 key points

i) From Witten, we know that the expectation values of certain observables of a physical system governed by a SU(2) Chern-Simons theory will be values of the Jones polynomial at nontrivial roots of unity. This fact immediately suggests an algorithm for approximating the Jones polynomial at these nontrivial roots. Namely, just build the system and then repeatedly measure these observables as accurately as one can. Now, this possibly is a naive algorithm since all the quantum “processing” is the system just evolving under its SU(2) Chern-Simons theory without any extra quantum dynamics/algorithmic processing being performed. But, who knows? Potentially, it’s optimal. In any case, analyzing this possibly naive algorithm is nontrivial in and of itself, so let’s start here.

ii) On that note, how accurate would your measurements have to be in order to solve the #P-hard problem of exactly evaluating the Jones polynomial at nontrivial roots? Freedman’s conclusion was you needed to measure with an accuracy threshold that shrinks *exponentially* in the size of the problem, though he phrased it in terms of needing a “linear” number of “reliable bits”. Specifically, he wrote:

Now, while the exponentially fine accuracy afforded by a linearly growing number of bits is a routine task in classical digital computing (e.g., the arbitrary precision arithmetic done by Lisp, Python, Mathematica, Maple, etc.), it’s a pretty grim omen for the odd hybrid of analog and digital computing that is quantum computing. But as Freedman notes, there are some quantum computing contexts where exponential such accuracy is achievable with polynomially-bounded memory and time resources. For example (and, of course, I’m not sure whether this is the example to which Freedman was alluding), the quantum phase estimation algorithm can measure the phase of an eigenvalue from a unitary operator down to n bits of accuracy with just O(n) qubits and O(n

^{2}) time.Freedman and coworkers establish that topological quantum computation isn’t fundamentally more powerful than standard quantum computation (i.e., circuits with unitary operators for gates). Each can simulate the other with only polynomial overhead [FKW, FLW1]. Though there wasn’t yet an explicit argument for why the exponential accuracy required to solve #P problems exactly would be intractable, I have a feeling that this was one of the times that, as you put it John, “with a great sigh of relief, computer scientists decided they didn’t need to learn topological quantum field theory.”

Freedman and coworkers present an explicit analysis [FKLW] of a topological quantum computer on which one can perform the naive algorithm of just implementing the system and measure the relevant observables as accurately as possible. *Implicit* in the answer they get for the probability of a certain of measurement outcome is that approximating the Jones polynomial at the 5th root of unity to within an additive error ε will require time of O[Poly(1/ε)] — that is, if J(ξ) is the true value of the Jones polynomial at the 5th root of unity ξ = 2 π i / 5, then producing an estimate J

_{est}(ξ) ∈ [J(ξ) – ε, J(ξ) + ε] requires time O[Poly(1/ε)]. As such, it’s *implicit* in [FKLW] that achieving the exponential accuracy demands set out in [Fr1] requires exponential time.However, Freedman, et al. do *not* make this explicit (at least not in published work) for another 4 years.

It’s at this point that it becomes explicit that efficient “additive approximation” of the Jones polynomial is really what this naive algorithm accomplishes and not efficient solution of #P-hard problems.

First, Freedman and coworkers sketch out the connection between topological quantum computing and “approximate counting” problems in general [BFLW].

And soon after, two researchers from the standard quantum computation community, Dorit Aharonov and Zeph Landau, along with Vaughan Jones himself [AJL] make it clear that in order to devise efficient quantum additive approximation algorithms for Jones polynomial, you really don’t need to know any topological quantum field theory and instead just a little algebraic knot theory. Computer scientists definitely breath a “great sigh of relief”.

With topological quantum field theory no longer a necessary prerequisite, various researchers from the standard quantum computing community publish results on efficient quantum additive approximations of various knot polynomials [e.g., AAEL, SJ, WY].

And at least 2 people who aren’t obviously crackpots ;) hold out hope that a more advanced use of topological quantum resources (processing with a supposedly efficient non-Abelian quantum Fourier transform?) can produce better results for #P-hard problems [MR].

[AAEL] Dorit Aharonov, Itai Arad, Elad Eban, and Zeph Landau, Polynomial quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane http://arxiv.org/abs/quant-ph/0702008.

[AJL] Dorit Aharonov, Vaughn Jones, and Zeph Landau, A polynomial quantum algorithm for approximating the Jones Polynomial,

Proc. 38th Ann. ACM Symp. on Theory of Computing (STOC ’06)427-36, http://arxiv.org/abs/quant-ph/0511096.[BFLW] Magnus Bordewich, Michael H. Freedman, Laszlo Lovasz, Dominic J.A. Welsh, Approximate counting and quantum computation,

Combin. Probab. Comput.14(2005) 737-754, http://arxiv.org/abs/0908.2122.[Fr1] Michael H. Freedman, P/NP, and the quantum field computer,

Proc. Natl. Acad. Sci. USA95(January 6, 1998), 98–101, http://stationq.cnsi.ucsb.edu/~freedman/Publications/65.pdf.[FKW] Michael H. Freedman, Alexei Kitaev, and Zhenghan Wang, Simulation of topological field theories by quantum computers,

Commun. Math. Phys.227(June 2002) 587-603 http://arxiv.org/abs/quant-ph/0001071.[FKLW] Michael H. Freedman, Alexei Kitaev, Michael J. Larsen, and Zhenghan Wang, Topological Quantum Computation,

Bull. Amer. Math. Soc. (N.S.)40(January 2003) 31-38, http://arxiv.org/abs/quant-ph/0101025.[FLW1] Michael H. Freedman, Michael J. Larsen, and Zhenghan Wang, A modular functor which is universal for quantum computation,

Commun. Math. Phys.227(June 2002) 605-622, http://arxiv.org/abs/quant-ph/0001108.[FLW2] Michael H. Freedman, Michael J. Larsen, and Zhengfan Wang. The two-eigenvalue problem and density of Jones representation of braid groups,

Commun Math Phys228(June 2002) 177-199, http://arxiv.org/abs/math/0103200.[MR] Annalisa Marzouli and Mario Rasetti, Towards a quantum algorithm for the permanent,

Int. J. Quant. Info.5(2007) 223-228.[SJ] Peter W. Shor and Stephen P. Jordan, Estimating Jones polynomials is a complete problem for one clean qubit,

Quant. Info. Comput.8(September 2008) 681-714, http://arxiv.org/abs/0707.2831.[V] Dirk Vertigan, The computational complexity of Tutte invariants for planar graphs,

SIAM J. Comput.35(March 2005) 690-712.[Wel] Dominic J.A. Welsh,

Complexity: Knots, Colourings, and Counting, London Mathematical Society Lecture Note Series186[Cambridge University Press: Cambridge 1993].[WY] Pawel Wocjan and Jon Yard, The Jones polynomial: quantum algorithms and applications in quantum complexity theory,

Quant. Info. Comput.8(January 2008) 147-180, http://arxiv.org/abs/quant-ph/0603069.Ooops, just in case anyone’s reading the “Long Version” above, I should correct one error that stemmed from the fact that I initially numbered the references and then changed to Wang’s abbreviations for them. Namely, when I wrote

I meant to write

.

In short, Ref [4] = [FKLW] and Ref [1] = [Fr1], and “achieving” doesn’t have an extra “i” ;)

Bill wrote:

You’re my kind of guy!

I’ve always thought that usenet newsgroups, blogging and the like get more interesting when people take them really seriously and put work into their writing. That’s how it worked on sci.physics.research and the n-Category Café when I was there — and I hope it still does. And that’s what I want here. Your comment is a

marvelof detail and clarity, which takes my rushed summary of topological quantum computation and expands it to a really gripping story. Thanks!I have taken the liberty of polishing your typography a bit, and also changing one sentence of yours. You had written

which seems to conflict with your earlier usage of the letter xi:

So, I’ve changed the former passage to:

I hope that’s okay — if I misunderstood, please let me know.

I’m so glad like you liked my summary of the literature topological computing for approximating the Jones polynomial (and thus #P problems).

Thanks for prettying up the formatting and correcting that error about “ξ^5”. I indeed incorrectly notated it, meaning to type “ξ_5” since it’s indeed meant to signify the 5th root of unity e^{2πi/5}.

Also, I just noted one other error. I opened the “Long Version” of my comments saying:

I meant to write:

All the best!

–Bill

I’ve fixed the other little errors you noticed.

Ahhh, yes, Alice and Bob usually try to communicate in a safe way, that is in a way that the nasty Gina either cannot understand, or where Alice inevitably notices that Gina intercepted the message

With regard to semidefinite programming John wrote:

I don’t understand it either, but the name simply comes from a “semidefinite” condition on a

linearproblem: find an operator X for a given operator A that minimizes trace(XA), subject tolinearconstraints . Up to this point, the problem is a purely linear programming problem.Now we add the nonlinear, but convex, constraint that X must be selfadjoint, positive semidefinite, hence the name, semidefinite programming is therefore simply a subset of convex optimization.

No, duality theory is explained e.g. in the book Aspects of semidefinite programming. Wikipedia also cites a duality theorem.

John wrote:

Tim casually replied:

No? Which

partisn’t true? Both parts?Sorry for being snippy, it’s because I think I don’t understand this stuff well enough to try to explain it. But I can try:

A) Is the dual of the dual problem the original problem?

Let’s see what I know about this (everything in finite dimensions): Convex optimization problems can be reformulated in a standard form, where the objective function is linear and the set of allowed values for the variables (also called the

feasibility set) is the intersection of an affine subspace and a cone.There are cones that are selfdual, we have

1. positive orthant: linear programming,

2. second order cone: second order cone programming,

3. positive semidefinite cone: semidefinite programming.

1. and 2. are special cases of 3.

Since the cones are selfdual, the original problem and its dual problem can be cast in exactly the same form, so I’d say: Yes, in this sense the dual of the dual is the original problem.

B) In linear programming, if you know either solution (one of the original problem or one of the dual problem) you know both. Is the same true for semidefinite programming?

No, there are examples where the original problem does not have a solution, but the dual one has. If both have solutions and you can deduce one from the other, people say that

strong or perfect dualityholds. For this, one needs additional assumptions, these are listed in the statement of the duality theorem by Wikipedia. One assumption is that ofstrict feasibility, that means that thefeasibility set(the set of values for the variables that fulfill the constraints) has interior points, strict feasibility is also called strong feasibility, Slater’s constraint qualification or Slater’s regularity condition, the assumption of it holdings is also called theinterior point assumption.The other assumption is that the feasibility set is bounded from below resp. bounded from above (dual problem).

Thanks! Sorry to be unclear and/or rude: I wasn’t complaining about your being “snippy” or not explaining stuff you don’t understand. (Most people are

very happyto explain stuff they don’t understand — that’s whatreallybugs me.) I was just frustrated that I asked two questions and you answered them both with one “No”, leaving me uncertain as to your meaning.I feel happy if A) the dual of the dual is the original problem (if it weren’t, we shouldn’t use the term ‘duality’!) but B) sometimes a problem has a solution even if its dual doesn’t.

(However, your counterexample to B) seems to come from linear programming rather than this ‘semidefinite programming’ that I was asking about. I think that the ‘interior point assumption’ is pretty common in linear programming, and now I know why! So, I’m still wondering if

given analogous niceness assumptionsthe primal problem has a solution iff the dual one does in semidefinite programming. It’s not a very urgent question, given how little I know or, umm, care about semidefinite programming. But I would like to pose it here, in case an expert floats by who deigns to tell us the answer!)Strong duality:

It is true generically, in the sense that by changing the problem very little you can enforce it to hold. But there are degenerate cases where it fails.

This can be made completely precise but then the simplicity of the situation as in LP is lost.

Just a simple-minded remark, about something you have probably understood already: The `semidefinite program’ as you defined looks very much like something from a category, with being an arrow from to . So you have classes of self-adjoint operators on Hilbert spaces, and (linear) morphisms between them …

Hi, Amitabha! I’m in your neighborhood now!

I actually haven’t thought at all about these ‘semidefinite programs’. I was just taking notes on this talk. But I guess you’re right: there is a category where:

• an object is a Hilbert space equipped with self-adjoint operator , and

• a morphism from to is a

semidefinite program: that is, a superoperator from operators on to operators on that happens to send $a$ to $b$.So then the question is: have people thought about composing semidefinite programs? Is it useful to do so?

The duality for semidefinite programs might also have a nice categorical interpretation.

Thanks!

Yes John, I noticed you are rather close by. Hopefully we should be able to meet up before you pack your bags again! :)

Yes, of course those two are categories, the second looks like a double category to me …

Don’t know anything about composing programs, except for the physicists’ view that breaking a problem into pieces usually helps solve it faster.

Do linear programming and its duality have categorical interpretations?

Sorry, I read your reply too quickly and thought you were talking about a category of Hilbert spaces and morphisms between categories.

To correct myself, semidefinite programs don’t form a double category.