Sunday, January 15, 2023

Some Recent Important Quantum Theory Results, Part One: MIP* = RE

 While preparing for class, and for my general edification, I have been trying to organize thoughts about recent important results in theory and algorithms. The latter I try to keep up with on general principles, but the former is largely above my station on the mountain, as I stand on the col looking up at the peak through the swirling clouds of my own ignorance. I'm an engineer, and proud of it, and so I have an engineer's understanding of complexity theory. In fact, I have the understanding of an engineer trained in the 1980s; the theorists have been busy since then, and have really changed the landscape! So, take all that I say here with a grain of salt...

MIP* = RE 

(announced in January 2020, with evaluation ongoing) 
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen

I'm not part of the CS theory community, but I could hear the trumpets, kazoos and champagne corks from over here in the Engineering quad on our global, virtual campus. This paper is considered a big deal, assuming it's right, to which most people seem to have given provisional assent.

The introductory paragraph of the CACM version summarizes forty years of theory -- exactly what I need. The key advances: understanding the importance of randomness (in both the action of the algorithm, and in a willingness to accept a probabilistic answer, I believe), interactive proofs, and multiple interactive provers. The authors then go on to cite the addition of entanglement as the fourth major shift. I feel like if I understood this paragraph alone, I would be a far better researcher.

Backing up a bit, computational complexity classes...checking The Complexity Zoo, we see that there are currently 546 complexity classes acknowledged there. Back when I was an undergrad, I learned about 2.5 of them: P, NP, and "bigger than NP", so things have changed a bit. To understand the importance of this paper, we are going to have to understand IP, MIP, MIP*, and RE and their relationship to some of the other basics. Okay, the Complexity Zoo itself is pretty intimidating, so let's try the introductory Petting Zoo, which introduces sixteen important classes...none of which are IP, MIP, MIP*, or RE.  All right, let's roll up our sleeves and see what we know...

  • P is the class of problems solvable in polynomial time -- the simple ones.
  • NP does not mean "non-polynomial", it means non-deterministic polynomial. If you have a Turing machine that solves problems with high combinatoric complexity, then the challenge is to pick good potential answers to try. If trying one solution and failing doesn't help a whole lot in eliminating other possible solutions, you might be in NP territory. Typically, if the size of the problem is n, then the number of possible solutions is O(e^n). But the formal definition of NP is such that the Turing machine scratches its head, shrugs its shoulders, and somehow magically picks the right answer each time, in polynomial time. The practical implication is that there is an exponential number of potential answers that have to be checked one by one, but once you have found an answer it is easy to verify that the answer is correct.
  • MA is Merlin-Arthur, and is the first time we run into two parties in our theoretical conception and proofs. Merlin has infinite computational power, and wants to prove to Arthur that he knows the solution to a problem, so Merlin sends Arthur a proof. (This proof must be no more than polynomial in size, relative to the problem size n.)  Arthur has normal, mortal computational power, but he also has access to a source of randomness (coin flips), which he uses after receiving the proof from Merlin. Arthur check the proof, using his coin flips as needed, but there is a probability he will wrongly decide whether or not the proof is correct. Generally, we require the probability of correctly accepting a true proof to be at least 2/3, and the probability of incorrectly accepting a wrong proof at 1/3. (That is, the probability of false positive or false negative is each no more than 1/3.) This is the introduction of randomness discussed above. Note that, in this conception, only one round of communication is used.
    Merlin can be called the prover (P), and Arthur the verifier (V). Those terms come up a lot later.
    (Theorists were actively working on this around the time I was an undergrad, but I was completely oblivious to it. Babai 1985 is a key reference.)
  • AM is Arthur-Merlin, which is similar except that Arthur makes his coin tosses before Merlin produces the proof, and sends the coin toss results to Merlin, who can use them as he wishes. After Merlin sends the proof to Arthur, Arthur is required to deterministically check the proof.
  • IP is Interactive Proof, also introduced in 1985 by Goldwasser, Micali and Rackoff. It's similar to AM, except that there can be a polynomial number of rounds. This is where the interaction mentioned above comes in.
  • MIP is Multiple Interactive Provers, introduced by Goldwasser & co. in 1988, uses two (or more?) provers. The provers are allowed to decide on a shared strategy or otherwise share information before the proof starts, but not after it begins. Perhaps the easiest way to enforce that non-communication is to verify the position of the two provers, and require their answers to be received by the verifier in time so short that the speed of light prevents them from having communicated with each other. Now we have our multiple provers.
  • RE is Recursively Enumerable, and is the set of all problems that a Turing machine can solve in finite (but not limited to polynomial) time. It's a very big set.
  • ...and for the purposes of this blog entry, there things stood for a long time...until:
  • MIP*: MIP, except that the provers get to share entanglement beforehand. MIP* includes things like the CHSH game.

I'd like to have good pedagogical examples to go with each of those classes, but at the moment, I don't. My apologies; I'll try to add some later. One important note is that from MA on down, a lot of classes are often expressed in terms of cryptographic functions or cryptographic games.

Also, roughly, that list goes from less complex to more complex, with each class including all of the problems in the classes above it on the list, but in general not all of the relationships are exactly known. Most famously, NP is commonly believed to include problems that are outside of P, but that has never been proven.

And so, the proof of MIP* = RE...drum roll, please...

I don't understand it.

But I'm not alone, most people don't. It's a complicated thing.

In fact, the link above is to the CACM version of the paper, which is written for readers like me, but the full paper is 237 pages. Not very many people have even read the whole thing.

But, I think I am safe in saying this: Very, very, very roughly, it is now (provisionally) known that polynomial amounts of entanglement can be used to solve some very enormous problems. What "polynomial" means here, and what the constant factors are, and real-world examples of problems that are classically intractable but quantumly tractable in practice, all remain as future work. Henry Yuen even refers to this as an "elephant" they are trying to get a feel for.

I wish I could do a better job of explaining its importance, though.  Instead, I will defer to one of the authors, Henry Yuen, and to Scott Aaronson. Scott in particular links to a lot of other explanations, so you can go from there.

Book Progress: Quantum Communications

Over the Christmas & New Year's break, a lot of editing on the book got done -- thousands of edits, according to git. 14/15 of the chapters are in serious local review. Chapter 15 still needs quite a bit of editing. Boilerplate, exercises, index, etc. are partially done; no cover yet. Glossary and table of notation aren't done yet.

If you want to be an alpha reviewer, let me know! It will be distributed soon.

Thursday, December 15, 2022

Quantum Internet class for undergrads!

It's now official -- next fall I will be teaching an undergraduate class titled "Quantum Internet". As far as I am aware, this is the world's first Quantum Internet course aimed at undergraduates!

Next year, we will have two undergraduate courses:
  •  Quantum Information Processing: intended to be a moderate introduction, suitable not only for those planning to continue in quantum but also those not planning to continue in quantum but who want to understand the key ideas. Intended to be accessible to ambitious freshmen, the only math required is a little bit of linear algebra and discrete probability. This course is based on two short online courses we have created, plus some hands-on exercises. Taught flipped classroom style.
    • "Understanding Quantum Computers" (UQC) -- basic ideas of computation (superposition, interference, entanglement, unitary evolution, measurement, decoherence and no-cloning; algorithms; types of hardware), not a lot of math
    • "Overview of Quantum Communications" (English and Japanese) (OQC) -- a little more math and the basic ideas of quantum communications (teleportation, BB84, purification, entanglement swapping) as well as critical basic technology (especially waveguides/optical fibers and lasers)
    • exercises using IBM machines via GUI & Qiskit
  • Quantum Internet: intended for those wanting to go a little deeper, but not limited to those joining my research group, AQUA. The QIP course above is a strict prerequisite, and this course will also be taught flipped classroom style. There will be substantially more math in this, but it's not purely abstract, most of it is in service of designing real systems. It will be based on our 2nd and 3rd Q-Leap Quantum Academy modules:
    • "From Classical to Quantum Light" (CQL) (English and Japanese) -- Maxwell's equations, single photons, more on waveguides
    • "Quantum Internet" (QI) -- the module we are recording lessons for right now: deeper analysis of errors and error handling, network engineering issues such as routing, multiplexing, security.
    • Exercises are still a little TBD, but will include QuISP and Intel-based exercises
UQC was funded internally by Keio. OQC, CQL and QI are funded by the Japanese government Q-Leap program. Portions of OQC are now being translated into Chinese, Thai, Arabic, Korean and French, thanks to a grant from Intel. More announcements on languages to come!
The material from OQC is now being compiled into a book. We expect an alpha-release draft to be available in January 2023 and a near-final version in 2Q2023. We have not selected a publisher for the book yet, but are looking for one.
All of the materials are or will be available under a Creative Commons license. People are encouraged to reuse, remix, translate, etc. -- just give us credit and make your own work available, too.

Monday, November 21, 2022

Book Progress: Quantum Communications

 Seven of the fifteen chapters in our next book, "Quantum Communications", are ready for local students to use/review. With this momentum, the book should be 2/3 ready in a week. Aiming for 4/5 finished by Dec. 19, then completion of alpha release quality over New Year's.

Sometime in Q1 2023, I expect to open up a PDF for wide review and the git repository for pull requests for corrections or contributions. With luck, the completed book, at least at strong beta reader level, will be on the arXiv April-ish.
The book will be Creative Commons, CC-BY-SA. People will be encouraged to contribute to our version, recompile or restructure for their own local use, or translate into other languages.
Keio and the Japanese government pay me to create knowledge, but it does no good if it's not shared, and I want it to go much farther than just the students of Keio and the other elite Japanese universities. Intel is also providing us with support for education. Let's work toward a high-quality, online, flexible, supported, inclusive, highly available quantum curriculum with global reach, including language.

Sunday, November 06, 2022

Spelunking CACM, Vol. 12 (1969)

 The first half of the year seems to move along smoothly, with a lot of algorithm papers but not much exciting. Automated printed circuit routing with a stepping aperture, by Stanley E. Lass, is the first hardware CAD/routing paper I've seen in CACM, but it cites a couple of things from the early 1960s. I remember VLSI engineers at Caltech in the early 1980s worrying that chips being designed by computers automatically were too complex to verify by hand. Of course, we now think of verification as being a task best suited for automation.

One letter to the editor in June, though, concerns an LA chapter meeting that bothered the author:

My disappointment stems from the subject matter and from the speakers. Three of the last meetings which I attended had to do with social conscience and community aspects. Two of these were on the same subject "Operation Bootstrap," which is an L.A. area self-help program for black people.

If only we had been more successful all the way back in 1969 in creating an inclusive atmosphere, and providing mentoring and help to those who needed it!

 A July paper talks about adding features to Dave Farber's SNOBOL. I haven't programmed in SNOBOL, so there are things I definitely don't grok, but there is a feature called "indirection", in which a variable contains the name of another variable, and via indirection the value of that variable can be read or written. This, of course, requires that the symbol table be available at run time, since the variable name can be constructed by the program! No indication in this paper as to what happens when the name isn't found in the symbol table (or, in modern terms, a dictionary?).

The September issue has a solid theory paper by David L. Parnas, On simulating networks of parallel processes in which simultaneous events may occur. It's dealing with discrete event simulation, and provides formal logic solutions for handling simultaneous events in the simulation of digital logic circuits. This work is roughly contemporaneous with the cooperating sequential processes work of Dijkstra and a little before the communicating sequential processes work of Hoare. Although this paper explicitly discusses the parallel nature of the work to be done and some machines that do the work in parallel, the paper really focuses on how to guarantee an acceptable sequential ordering.

And, in fact, in the following month's issue there is an article by Tony Hoare on An axiomatic basis for computing programming. This particular paper takes an...optimistic?...view of programming?

Computer programming is an exact science in that all the properties of a program and all the consequences of executing it in any given environment can, in principle, be found out from the text of the program itself by means of purely deductive reasoning. 

And then later,

When the correctness of a program, its compiler, and the hardware of the computer have all been established with mathematical certainty, it will be possible to place great reliance on the results of the program, and predict their properties with a confidence limited only by the reliability of the electronics.

Ah, would that it were so...


Friday, August 26, 2022

Quantum Ethics, the Conversation Continues

 In the magazine Foreign Policy, Vivek Wadwha and Mauritz Kop have an article titled, "Why Quantum Computing is Even More Dangerous than Artificial Intelligence", published in August 2022. It's one in a series of recent articles by Vivek arguing that technology needs to be regulated to address ethical concerns. In the article, Vivek and Mauritz argue that the unregulated, market-driven, ad hoc use of technology such as AI has produced outcomes that we would all consider undesirable, chiefly through mechanisms such as AI adopting our own biases or misuse of indiscriminately collected personal data. They tie quantum to these same issues, which I think is correct. In fact, I argued in a March blog posting that the ethical issues in quantum are, in the short run, very similar to classical computing, though I consider it too early to connect quantum to AI.

The authors have referenced some valuable online resources, such as the video "Quantum Ethics | A Call to Action", which includes excerpts from John Martinis, Nick Farina, Faye Wattleton, Ilyas Khan, Ilana Wisby, and Abe Asfaw, which I highly recommend.

I would not have picked the adjective "dangerous", but the conversation is critical. We should not be afraid of our technological future, but we should not use it without paying attention to the macro-level changes it brings. I believe quantum technology, the Second Quantum Revolution, will bring tremendous benefits in the long run -- if we use it wisely.

Monday, July 25, 2022

Spelunking CACM, vol. 11 (1968): Operating Systems Bonanza and Ethics, but not the ARPAnet!

If 1967 was a little dry, 1968 more than made up for it. The May issue is worth reading end-to-end! As it happens, that issue contains retypeset (and possibly updated?) versions of papers from the first Symposium on Operating Systems Principles (SOSP), which took place in 1967.  That first SOSP includes Larry Roberts's description of the ARPAnet, though that paper doesn't seem to have made it into CACM. (Some of the links below may be open access via the second link above, if the links below take to you the paywall.)

The year was just chock-full of operating systems papers by names such as Jack Dennis, Butler Lampson, and Edsger Dijkstra, and a comprehensive view of systems by E.L. Harder and another view of things by Jack Dennis, many but not all of them from that SOSP. This year also provided the first proposed ethics guidelines for ACM members, to the best of my recollection.

Donn B. Parker's article, "Rules of Ethics in Information Processing," presents the ACM's Guidelines for Professional Conduct in Information Processing. The article begins with three major points we still debate today, and a fourth (fraudulent programming schools) which seems to have been more transient. It begins:

There are a number of serious ethical problems in the arts and sciences of information processing. A few of these are: invasion of privacy by use of the computer; implications of copyrighting computer programs; and fraudulent programming trade schools. The "little" problems of personal ethics are of equal importance and are often closely related to the more imposing problems.

The original version filled less than a page, divided into rules for relations with the public, with employers and clients, and with other professionals. I can't help but notice the continuous use of the pronoun "he" to describe an ACM member, though honestly that probably would have been not so different even a decade ago.  This set of guidelines has now grown into ACM's Code of Ethics, which everyone in the field should read.

As a Caltech grad, this paper on a means of recovering an on-disk structure after a system crash, caught my eye. Of course it's a systems paper, so I'm naturally interested, but otherwise maybe not so remarkable by today's standards. It's the first non-Knuth-sensei Caltech paper I remember spotting, but I haven't checked the affiliation of every single author. (Knuth-sensei's first paper with a Caltech affiliation might be 1961.) I don't recognize either of the authors, Peter C. Lockemann and W. Dale Knutsen. Caltech punches far above its weight in almost every scientific field, and many Caltech alumni have made major contributions to computing, but computing seems to be relatively weaker than fields like physics and chemistry.

The April issue has a breathtaking, simultaneously contemporary and prescient view of how the need for computers was broadening. "Perhaps the computer is too big for the space vehicle, or to put in your vest pocket," Harder posited. It serves as a harbinger of the papers to come in May.

Daley and Dennis described virtual memory in MULTICS, one of the three or four most influential systems in history. Oppenheimer and Weizer presented their resource management in mid-sized systems. Van Horn of GE described a set of formal criteria for reproducibility in debugging. Interestingly, he used the term "virtual computer", essentially describing a process as an instance of a virtual machine, language very similar to what I use today. And Dennis shows up again, with a position paper arguing in favor of timesharing machines over networks that is well worth a read.

But the star, the paper for the ages, is Dijkstra's "The Structure of the THE Multiprogramming System", which features the observation that "an interrupt system to fall in love with is certainly an inspiring feature." Part of what makes the paper spectacular is that Dijkstra describes their failures and mistakes. We could all learn from this approach! Although perhaps his claim that the delivered system would be perfect should be taken with a grain of salt? The paper doesn't have references(!), but this is a real-world implementation of Dijkstra's Cooperating Sequential Processes, the idea he was developing in the mid- to late-1960s that would become one of the foundations of theoretical work on computing systems. The clever language also makes the paper a pleasure to read. All systems people should read this paper!