### Friday, September 22, 2006

Van's Disruptors (No, not high powered weapons)

The October 2006 issue of Business 2.0 has a list of companies producing "disruptive" technology that could "reorder entire industries". Business 2.0 tends to focus on Internet companies, so I would say there's a bias to their conclusions. Instead of providing a summary of their picks, I would like to present my own picks, in no particular order.

Bigelow Aerospace - Ushering in the commercial space age
They are providing the framework for an entire new commercial industry by producing and launching space habitats. By providing an orbital destination, a new competitive landscape will be created, in which commercial launch vehicle companies can thrive.

Unfortunately, available launch services might be the only thing holding Bigelow back. I guess that's why Bigelow recently partnered with Lockheed Martin to explore using the Atlas V as a human-transport vehicle. Now all they need to do is partner with SpaceDev so that a viable capsule can be used like the Dreamchaser.

The photo above is from SpaceDev's website http://www.spacedev.com

Tesla Motors - Electric Cars ARE cool
The only thing keeping me from buying a hybrid alternative energy vehicle are cost-justification and style. Tesla has produced a car that looks cool and it PERFORMS. Now all I need is $100,000 to buy one. See video of the unveiling here. Statistics from their site: • 100% electric • 0 to 60 in about 4 seconds • 135 mpg equivalent • 250 miles per charge • about 1 cent per mile Flynn Research - Reinventing the electric motor According to their website and other sources, they have developed an electric motor that is up to 3.5 times as efficient as conventional electric motors. Unfortunately there is a lot on the net which associates this technology with anti-gravity devices and limitless "greater than unity" energy generation. From what I can tell however, Flynn has just challenged a status quo and found a fundamentally more efficient design (Parallel Path Magnetic Technology) to a device whose total numbers likely reach into the billions. Apparently the technology is using physics so basic that even a kid could understand it. Think of all the motors you own: vacuum cleaner, power tools, toys, . . . I would like to see a successful commercial application (maybe Tesla motors??) before I buy into this, but I believe the promise is huge. D-Wave Systems - Pioneering a new way of computing You might've heard how something known as quantum computing is the ultimate computing technique because of it's ability to compromise the encryption used in modern day information systems. Dr. Geordie Rose would tell you this reason is bogus (I don't know for sure but I think he would). The real killer app is in modelling Quantum systems and (more importantly to me) efficiently solving a class of problems known as NP-Complete problems. After reading Geordie's blog, it looks like this company has recently changed focus to solving NP-Complete problems. Since there are millions of software engineers out there, I think the question on most people's minds would not be how to build a quantum computer, but how to program one. My prediction is that the availability of quantum computers will fundamentally change the way people think, because it will bring a quantum way of thinking to the coal-miners of the information age. Consider a set of apples. One apple is green, the rest are red. We want to find the green apple: Classical search routine: for (int i = 0 to n) { if( Apples[i] == green) success(); } failure(); If things work out as I hope, for the D-Wave Systems Non-Deterministic search routine we could do something like this to find the green apple: int j = choice(1,n); if(Apples[j] == green) success(); failure(); The magic is in the function choice(). As programmers, we don't care how choice() picks the proper item. It just does. And if the classical search routine on a conventional computer takes an exponential amount of time, then the non-deterministic search routine takes a polynomial amount of time on the quantum computer. (The above example is not supposed to be Grover's algorithm which only provides quadratic speedup). According to the D-Wave blog, the level of guarantee of the run time is not yet 100%. I'm hoping that soon this type of algorithm runs with 100% certainty, and more importantly that I get to program it! One public company that has invested in D-Wave is Harris & Harris Group, Inc. (TINY). Boston Dynamics - "Dedicated to the Art and Science of How Things Move" I don't have a good opinion on a business case for this company. But their technology is absolutely amazing looking. Watch it here. Next-gen battery technology I'm not naming a specific company because my 2 picks here: EEStor and MIT both have too little information available on the net. EEStor (doesn't seem to have a website) was one of the Business 2.0 picks for disruptive technology. But here's a list of "facts" about their battery technology gleaned from various sources: • Battery is solid state and non-chemical • For powering cars, charges in 5 minutes, and good for 500 miles on$9 worth of electricty
• At least one company FeelGood cars (is publicly traded on Toronto Stock Exchange, ZNN) will incorporate EEStor technology by 2008.
• According to patents, battery is made of ceramic powder with a coating of aluminum oxide and glass (isn't that the same material for a flux capacitor? hehe).
MIT is also working on batteries, but the energy density isn't yet as promising as EEStor's. A good article on the MIT work is here. More technical information regarding the capabilities of MIT's carbon-based nanotube ultracapacitor is located here.

Stirling Energy Systems - Indsutrial strength solar energy collectors
If you want to go solar, use these. While silicon and other material-based technology based on the photoelectric effect is still developing, these guys are already producing a solar energy system that is up to 80% efficient.

In 2005 it contracted with Southern California Edison to install a 4,600-acre solar system that will generate 500 megawatts to power up to 250,000 homes. A compilation of related news stories is located here. I emailed this company about when they might go public. Here's an excerpt of the response: "We are still working to define what that timing will be for an IPO, but it is probably in the 2008 timeframe, when we are beginning initial installations of our first large solar power plants. It could, however, occur either slightly sooner or later." Sooner sounds good to me.

--Van

Some comments on quantum computers.

"efficiently solving a class of problems known as NP-Complete problems"

There is no evidence what quantum computers can solve NP-complete problems 'efficiently', i.e. in polynomial time.

http://arxiv.org/abs/quant-ph/0502072

"classical search routine on a conventional computer takes an exponential amount of time"

It takes polynomial amount of time: O(N). Grover's algorithm offers a quadratic speed-up: O(\sqrt(N)).

This is a great list. Some very cool companies; to my mind these types of efforts, that really stretch out to try to do something remarkable, are far too few and the "me too" wireless/web/etc. plays far too many. Great stuff.

Also to the previous poster: two things.

1. There actually is evidence that quantum computers can solve NP-complete problems in polynomial time (see quant-ph/0104129). There is also evidence to the contrary. It will probably turn out that the speed-up will be quadratic, not exponential, but this is by no means established...there are a lot of subtleties (instance dependence, choice of annealing schedules, effects of noise, etc.)

2. Searching an unsorted list takes O(N) for N elements, but for the types of problem referred to in van H.'s post, N is exponential in problem size. Take your favorite NP-complete problem size M, use your favorite exact algorithm, the number of elements that could be the right solution is N=a^M, so O(N)=O(a^M) which is exponential in time. This is related to the previous point also. Even if a QC gives quadratic speed-up, this takes O(N) -> O(\sqrt(N)) = O(a^(M/2)), effectively doubling the problem size you can solve with fixed resources (which is significant and valuable).

"There actually is evidence that quantum computers can solve NP-complete problems in polynomial time (see quant-ph/0104129)."

That's correct. I wouldn't describe it as a 'strong' evidence, though.

So let me rephrase:

Whether 'the real killer app' really is 'efficiently solving a class of problems known as NP-Complete problems' remains an open question.

"It will probably turn out that the speed-up will be quadratic, not exponential, but this is by no means established..."

I totally agree on this.

A quadratic speed-up is also a more precise characterization than "Quantum computers can be used to get approximate solutions to large NP-complete optimization problems _much more quickly_ than the best known methods running on _any_ supercomputer." http://dwavesys.com/optimization.php

"Even if a QC gives quadratic speed-up, this takes O(N) -> O(\sqrt(N)) = O(a^(M/2)), effectively doubling the problem size you can solve with fixed resources (which is significant and valuable)."

A quadratic speed-up certainly is a nice thing. Another question is whether such a speed-up is economically utilizable for a = 2 and M >= 1000.

This comment has been removed by a blog administrator.

This comment has been removed by a blog administrator.

To anonymous:

Thanks for the comment. You and Dr. Rose are most certainly smarter than me on this, so I won't try to join the debate on whether or not quantum computers will turn out to be true 100% non-deterministic machines.

I still believe even with quadratic speed-up it would be pretty exciting to see what programmers can come up with when they have a working quantum computer.

For example, when ENIAC came out, did any of the first programmers envision such programming/computing techniques as genetic algorithms, neural networks, or template metaprogramming? Or even the entirety of the internet? (That last link is a joke.)

My point is that whatever the hardware guys come up with, I am very hopeful that there will be some mind-warping possibilities for the software.

--Van

What a treat to have Dr. Rose post here! Thank you! I've never had the honor of meeting him, but I got a little insight by watching a presentation he gave at Stanford. You can see the video here. If you really want to keep informed about Dr. Rose's company (as well as his interest in heavy metal music ;) ), please check out his blog. I'll be sure to post any developments I hear about this exciting company in the future. It looks like they're gonna have a public demo of their technology by the end of this year.

By the way, another venture capital company funding D-Wave is Draper Fisher Jurvetson. If the freakishly genius Steve Jurvetson would invest in D-Wave, I probably would too. (At least he sounds smart.)

Regarding the example I provided, the non-deterministic algorithm is based on a non-deterministic machine model used frequently in the presentation of Cook's Theorem. This machine model supports all the decision structures provided in a procedural or imperative programming language. But in addition, it also provides the magic function "choice()" as well as "success()" and "failure()". Any program written using this model may be "compiled" into a boolean expression, or an instance of the satisfiability problem (SAT). The whole P=NP debate rests on whether or not any instance of SAT can be solved in polynomial time.

Anyway, as a programmer (from the near future), if I'm presented with a really tough problem, I might want to first pseudo-code a solution in the language of this non-deterministic machine model. By doing this, I've proven that the problem is at least in NP. This program can then be compiled to an instance of SAT. Furthermore, it turns out that any instance of SAT can be "compiled" into a Maximum Clique problem. It's my understanding that D-Wave is working on solving Maximum Clique problems. We'll find out this year!

--Van

Well I've been trying to find out more about Flynn Research and so emailed one of the contacts I found at this site. To my great surprise, I got this reply:

Van,

I researched this and discovered that the anonymous researcher is a 15 year old kid named Josh out of Florida. This is fantastic that a 15 year old kid did this as a science fair project. If a 15 year kid can validate PPMT what has been wrong with the rest of the adults out there??? PPMT has been around for at least 10 to 12 years and I have never seen a single researcher besides myself and a man named Tim Hartwood do a workup on this technology. Kinda sad don’t you think. I have been involved in this field for the past 15 years and have tried to stay on top of what is happening. I was aware of the kid out of Florida, but never read his research paper (Shame on me!!).

I have built the last device he shows in his report. The device is very difficult to get working properly, but also is very noteworthy once you get the switching timed out correctly. I wish him well.

Van, as far as updates go I just had a 45 minute phone conversation with Joe Flynn 2 days ago. I never mentioned this kid because I didn’t think that much about the importance of his science fair research. (Shame on me again.)

Flynn Research will be releasing information soon on the type 6 motor as well as possible other aspects of PPMT technology. The exact time is up to his lawyers and patenting status, corporation formation, ect.

I also hope to join Joe Flynn later this year designing microprocessor based controllers for his motors.

I hope this catches you up on things.

Best regards!

Michael Schuckel
MS Design

I do hope they succeed.

--Van