A Quantum Computer and a Scripting Studio

7-10 Split

Apple's AppleScript Studio is an interesting example of the melding of cultures that resulted from Apple's acquisition of NeXT back in 1997. AppleScript, the language, is a legacy of Macintosh System 7, which was released in 1991 and was the most significant upgrade to the MacOS up to that point, and also since that point, prior to OS X.

AppleScript really annoyed developer Dave Winer, who had spent a lot of time and effort bringing his own Macintosh scripting language to market with Apple's encouragement, while all the time Apple was working on its own scripting language. As it turned out, though, AppleScript didn't spell the end of Winer's Frontier because of two System 7 technologies: AppleEvents and the Open Scripting Architecture (OSA). Frontier and AppleScript turned out to take different approaches to user scripting, and Frontier, with its novel built-in object database and outline-based program editors and data viewers, was moderately successful.

Back then Apple was calling AppleEvents "the enabling technology for a user scripting language," and I remember writing in 1990 that we might see not just one but several such languages. In 2002, both AppleScript and Frontier are still around, although only AppleScript has been upgraded for OS X and Frontier has been repositioned as a web-content management system.

AppleScript has proved to be a remarkably benign technology: It's also free; it's utterly ignorable if you have no use for it but right there if you need it; and it's self documenting. That is, every application that supports AppleScript can be queried for the AppleScript vocabulary that it supports, and it will answer, revealing its AppleScript dictionary in a perfectly predictable and consistent way.

It's never been a flashy performer, though. AppleScript is a tool that developers and power users employ to get a job done, not often something that is used directly to produce salable software; a utility, not an application development platform. Art directors and webmasters and video production types like it for its ability to automate repetitive file operations: batch renaming of files, moving files into new directories, uploading web pages, doing routine graphic file conversions. Many of its uses are of the quiet, invisible, background kind, unobtrusive except that they tend to litter the desktop if you leave them there to keep them handy.

Not Your Father's Scripting Environment

Enter AppleScript Studio, with the potential to radically change the uses to which people put AppleScript, because AppleScript Studio produces applications. I imagine those same art directors and webmasters and video production types suddenly realizing that they can bundle up the little script files they have produced and tweaked to a fine efficiency over the years, putting a unifying interface on them, integrating them more tightly, and selling the resulting application to others of their ilk.

And those applications will be Cocoa apps, not Carbonized apps, because the development environment for AppleScript is straight from the NeXT lobe of Apple's brain.

Cocoa is OpenStep is NextStep is the development environment that evolved out of the work that Avie Tevanian did on Mach at Carnegie Mellon before Jobs hired him at NeXT. Cocoa's two weapons in its campaign to make software development as simple as possible (why does this sound like a Monty Python sketch?) are Project Builder and Interface Builder. These, plus AppleScript and a couple of Frameworks, make up AppleScript Studio. So it's not so much a new product from Apple as a new combination of some new and old software to produce something new — call it a virtual product.

AppleScript Studio is not an entry-level scripting system like HyperCard. It uses the same development environment in which Java and Objective-C developers create mainstream Cocoa applications, and anyone working in AppleScript Studio is also going to be producing real mainstream Cocoa apps. Although AppleScript Studio developers can do all their coding strictly in AppleScript, AppleScript Studio does automatically place a small amount of essential Objective-C code in every application it produces, and this code can be edited and augmented with more C or Java code.

Design Patterns and AppleScript

The documentation for AppleScript Studio is a (downloadable) 264-page book called Building Applications with AppleScript Studio (http://www.apple.com/applescript/macosx/ascript_studio/). A large part of it is given over to building a significant application called "Watson." This is not the same as the Mac shareware app named Watson. The tutorial Watson is an e-mail search utility; the shareware Watson bundles together various web services. Even more confusingly, the shareware Watson looks like it could have been written using AppleScript Studio, although it would be a bigger project than the tutorial Watson.

By a minor coincidence, as I was working through the AppleScript Studio example project, James W. Cooper's book Visual Basic Design Patterns: VB6.0 and VB.NET (Addison-Wesley, 2002; ISBN 0-201-70265-7) arrived in the mail. I call that a coincidence because a certain amount of the complexity of the AppleScript Studio example project — complexity in terms of this being an elementary tutorial on AppleScript Studio — is owing to the fact that it grinds to a halt in the middle to explain the venerable model-view-controller (MVC) paradigm. This is the granddaddy of all design patterns, introduced early on in the development of the Smalltalk programming language. Nothing wrong with that, I suppose; in fact, I guess you could say that if you're not explicitly using some standard design pattern, you're probably implicitly using some bad or inappropriate design pattern. But I'm guessing that some AppleScript scripters (or VB programmers, for that matter) might be thrown a little by the level of discussion at this point in the tutorial.

But as I worked through the Watson tutorial, I began to appreciate how different the results of using AppleScript Studio are likely to be. This is not just a better script editor. In the past, the capabilities in Watson would have been coded in one or more scripts, possibly saved as script applications, but with not much user interface. Watson is a real standalone application. AppleScript Studio really ought to inspire a new (mostly shareware, maybe) market of utilities.

And AppleScript Studio has something for both scripters and Cocoa developers. It lets Cocoa developers add scripting capabilities to their apps and it lets scripters build real Cocoa apps with all the Aqua spiffiness that Cocoa provides. It could give a boost to Cocoa development as well as raising the quality and usefulness of scripting solutions created with AppleScript.

With the latest version of AppleScript the integration is pretty impressive, given that this is System 7 technology melded with NextStep. You can even call Objective-C methods directly from AppleScript scripts. For example, placing the AppleScript command:

call method "performClick:" of object 

	       (button 1 of window 1) with

parameters (button 2 of window 2)

in the clicked handler for button 2, will cause button 1 to act as though it had been clicked whenever button 2 is clicked.

I'm just at the finished-the-tutorial-now-what stage, but I expect to put AppleScript Studio to good use. I do a lot of scripting already, and the ability to produce Cocoa applications with those pretty Aqua interface widgets is highly appealing.

Quantum Entanglement

Every month or so brings a new "breakthrough" in quantum computing or nanotechnology, and not all of these are real breakthroughs. Quantum developments are not always quantum; nano advances are not always nano; and quantum computers or nanocircuits are sometimes not really computers or circuits.

But the achievement of real, practical quantum computing would be such a paradigm-breaking event for computing that every baby step is worth a look. That became acutely clear in 1994, when Peter Shor of AT&T Research published what is universally known as Shor's Algorithm, demonstrating that, if quantum computing becomes a practical reality, every current encryption scheme will be crackable. I guess you might call that scenario quantum computing's killer app.

A quick review, more for me than for you, perhaps:

Quantum Computing: An approach to computing that exploits quantum woo-woo, by virtue of which a single processing unit can simultaneously be in a superposition of multiple states and can perform a transformation on all possible permutations of states at once. Making a whole bunch of really tough things suddenly very easy. This is called "quantum parallelism."

Qubit: A quantum bit. The smallest unit of quantum woo-woo. Just as a 3-bit register can hold any integer from 0 to 7, a 3-qubit register can hold integers from 0 to 7. However, the qubit register can hold a superposition of all the integers from 0 to 7 at the same time. Quantum computing has its own limitations, but those limitations are fundamentally different from those of classical computers, and real quantum computers would change the computing world in fundamental ways. It was quickly perceived by those exploring this territory back in the 1970s that one thing that would be changed drastically, at least in principle, was encryption. In 1994, that went from abstract principle to published algorithm.

Shor's Algorithm: An algorithm for factoring large numbers exponentially faster than the theoretical limit on factoring large numbers. By algorithms implemented on conventional computers, that is. Certain key steps of Shor's Algorithm must be implemented on a quantum computer. In December 2001, researchers at IBM's Almaden Research Center announced a quantum computing breakthrough involving Shor's algorithm. In language unusually coy for a press release, IBM said that it had "caused" a bunch of custom-designed molecules in a test tube to "become" a 7-qubit quantum computer, and used that computer to factor a large number, via Shor's Algorithm. Well, relatively large. Fifteen.

Even granting that qubits are rather magical, 7 qubits or 7 bits or 7 blivits doesn't really sound like enough to call IBM's device a computer. IBM usually holds itself to a higher standard than that. It's probably safer to call it a quantum computational device, especially since Shor's Algorithm is not intended to run on a pure quantum computer. So what exactly is this computational device, and just what did IBM do with it?

Do Quantum B-Trees Have Shor Leaves?

I think I more or less understand the algorithm, but the physics of the construction of the device is a little beyond me. Here's what I could glean from various sources: The IBM researchers filled a test tube with a liquid made up of just the right goo so that they could map each of their 7 qubits onto a whole bunch of molecules. They needed a lot of molecules to get around the problem of decoherence: By mapping each qubit to corresponding atoms in many identical molecules, they could let measurements interact with a few of them.

The deliberate interaction involved NMR (short for "nuclear magnetic resonance"): NMR operating on quantum particles in the atomic nuclei of the molecules makes particles with spin act like magnets and line up with an externally applied magnetic field. Alignments parallel or antiparallel to the field represent two quantum states — voilà, a qubit. Varying electromagnetic fields can be used to flip selected spins between states at will.

Three years ago, these researchers had built a 2-qubit quantum computer from a thimbleful of chloroform. The number of qubits depends on the size of the molecule; chloroform could yield them 2 qubits, and more complex molecules could yield more, but the NMR technique puts an upper limit on the size of the molecules and thus on the number of qubits such a device can contain: 10 qubits is apparently the biggest device that can be built using this technique. This winter, their 7-qubit device factored the number 15 into 3 and 5 using Shor's Algorithm.

Peter Shor's publications include a co-authored quantum computing limerick, but his most famous work is the Algorithm. Here is a quick sketch of the use of Shor's Algorithm to factor the number n using NMR and a jar of goo (thanks to Matthew Hayward and other sources):

1. Determine if n is prime, even, or an integer power of a prime. If any of these, use one of the known efficient algorithms to factor n on a classical computer.

2. Pick an integer q that is the power of 2 and that lies between n2 and 2n2. Do this on a classical computer.

3. From integers coprime to n, pick one and call it x. Do this on a classical computer.

4. Determine how many qubits will be needed to perform the quantum portion of the computation. The quantum computation will require a two-part register, the first part, R1, capable of holding integers as large as q-1, the second, R2, able to hold integers up to n-1. This determination is done on a classical computer. I confess to being a little unsure exactly how they proceeded here, since it looks to me like they needed more than 7 qubits. However...

5. Load R1 with an equally weighted superposition of all the nonnegative integers less than q, and load R2 with zeroes. This is the first operation for which we have to use the quantum device. We are using NMR to twiddle the spins of particles in the goo, I gather.

6. Apply the function xa mod n to each integer a in R1 and store the results in R2. More NMR, and due to quantum woo-woo, this parallel operation on all the integers encoded in the superposition of states in R1 can be done in one quantum operation.

7. Measure R2 and call the observed value k. This has the effect of collapsing R1 to an equal superposition of values a between 0 and q-1 such that xa mod n=k. This is the third operation that we perform on the quantum device.

8. Compute the discrete Fourier transform on R1. This is another algorithm that can be performed on a quantum device and can benefit from quantum parallelism.

9. Measure the state of R1, reading out a single integer m. If you're lucky, this will be the last operation performed on the quantum device.

10. Back on a classical computer, use m to determine r, the period of the periodic function xa mod n.

11. Compute gcd(x(r/2)+1,n) as well as gcd(x(r/2)-1,n). One of these should be a useful factor of n, but if it isn't, or if the factor is 1 or n, you loop back to step 4.

So most of the computation is done on a classical computer. Specifically, the operations performed by NMR on the goo in the jar are: Load a two-slot register with a superposition of integer values; apply a couple of functions to the superpositions of values, using quantum parallelism; and read out results, causing the superposition of values to collapse to a single integer. Input, computation, output: There really is some justification for calling this a computer. We could even try to decide what design pattern the IBM researchers were using. No, I guess not.

But, even though the NMR technique used by the IBM researchers may be a dead end, maxing out at 10 qubits, their example of how to solve a real problem with real quantum computation does suggest what future quantum computers might be like. Probably when we have real quantum computers they will actually be hybrid machines (in fact, they'll have to be, since the user interface, at least, can hardly be nonclassical): hybrid computers with classical and quantum components. It'll be hard for us old-fashioned classically minded types not to think of these quantum components as the black boxes where the magic happens.

DDJ