IAAP (I am a physicist). I do not work with lasers, but have taken a graduate level course in non-linear optics that primarily focused on lasers.
It is quite possible to damage a pilot's eyes at a range of a few miles, using only commercial laser systems. If done by competent individuals, it would probably involve a pulsed infrared laser (harder to detect, and the eye is more susceptible to near IR than to visible). A Nd:YAG laser (1064 nm) would be ideal.
Since a pulsed laser is used, there's no need for tracking the plane. A single 10-nanosecond pulse would be sufficient. At 10 - 20 pulses per second, you could just scan the sky in the area of the plane.
After reading the story, I did some rough calculations. For the above-mentioned laser, the laser beam would do damage (although likely not sufficient to totally blind the pilot) at ranges of up to two miles, and the beam would have a spot size several meters in diameter at that range. Obviously, with additional optics, range and spot size could be changed.
It seems to me that the laser could simply be mounted to a scope on a tripod (after some careful alignment), and that targetting by hand would work at least some of the time.
All this aside, I don't think the recent cases are anything to be worried about. More likely it's just a nutbar with a relatively weak visible laser (I assume the laser was in the visible range because the pilots reported it, and I doubt commercial planes are equipped to detect IR lasers). If it was someone serious, they'd be using IR lasers, and we wouldn't know until pilots started getting eye damage.
That said, the overall risk of plane crashes from this form of attack is low. If the airport and immediate area are kept secure (and they should be if only to guard against Stinger-style missile attacks), it's very unlikely someone with a commercial laser could get close enough to completely blind a pilot. Military or custom-built research lasers could blind from greater distances, but such systems are very finicky, and I can't see terrorists pulling that off.
Finally, I'd like to address a few points other people have brought up. If the polarization and angle of the beam are chosen correctly, virtually none will be reflected off the plane's window, and all will be transmitted (see Brewster's Angle). For modest laser powers, the damage to the retina will be localized to where the laser beam is imaged, leaving much of the pilot's vision intact. Bad for the pilot, but he could probably still land. For more intense beams, other damage mechanisms come into play (apparently for severe cases there is an actual popping sound perceived by the victim as the laser pulse creates a small shock wave inside the eye), and more of the victim's vision could be damaged.
Protective goggles aren't really an option, as they only protect against one wavelength. Attackers could then switch to a different type of laser (Ti:saph?). Combining goggles leads to virtually no light getting through.
Sloppy writing implies carelessness at best, ineptitude at worst.
Sometimes, sloppy writing is the rational way to go. I've been coming to the realization that writing careful, clear emails is a waste of time, because nobody reads them in any detail anyway.
For several months, my boss and I have been on different continents, communicating only by email. If I take the time to write her a detailed but succinct email, I'll often just get back a two-line response that makes it clear she didn't read half of what I wrote.
*Sigh*. Disney will ruin it--I don't think anything decent has come out of Disney in the past five or ten years, aside from the Pixar stuff. Does anyone know if Disney owns the rights to The Incredibles sequel? That would be really unfortunate...
Ah, but simulating things at a quantum level is exponentially hard. In other words, adding a single atom to your simulation doubles the complexity of the classical computation. Even if Moore's Law continues to hold, that means the size of the largest simulation we can handle grows only linearly with time.
The only solution is a quantum computer, for which the computational complexity grows linearly with the size of the simulation.
Disclaimer: I'm a graduate student doing research on quantum computing in optical lattices. I'm not affiliated with the group that published this article.
This result is quite exciting, because it demonstrates the feasibility of some of the techniques necessary for an optical lattice-based quantum computer. Imagine taking their 1-D lattice and turning it into a 3-D lattice, with about 30 atoms in each direction. That's a whole lot of qubits...
So what are the next steps? 1) A new means of addressing atoms (selecting one or two atoms on which to perform operations while excluding the rest) is necessary. Their magnetic gradient technique works fine for a small 1-D lattice, but it would likely be impractical for a large 3-D lattice (Maxwell's equation div B = 0 gives one major obstacle, which would require fancy tricks to overcome). 2) One and two-qubit gates need to be demonstrated using an appropriate addressing scheme. 3) Error correction, which would likely require quantum non-demolition measurements to check to see if an atom had been lost from a lattice site. Translation: we need to be able to measure if we've lost an atom from a lattice site, without disturbing the atom's state (i.e. measuring whether it's |0> or |1>). 4) Full-blown fault-tolerant computation.
My group plans to solve (1) using an addressable optical lattice. What that means is that the lattice spacing is sufficiently large that a laser can be focused on an individual atom (in 3-D, two lasers in orthogonal directions would be used). I'm currently doing simulations of one-qubit gates in this scheme.
That brings me to my question for slashdot: Some of the simulations I'll be doing (specifically, studying decoherence in the one and two qubit gates) will be very computationally intensive. They're also embarrassingly parallel, as they're essentially quantum Monte Carlo simulations. Would people be interested in a BOINC-based distributed computing project (a la SETI@home) to help develop quantum computers? If so, what kinds of things would help you get involved? Would you be interested in helping develop the software (it's C++)?
I probably won't be at that stage for another six months to a year, but it would be helpful to me to start planning now. I have just (last night) completed the core simulation engine, and would need to add code for decoherence, as well as adapt it to BOINC. The code will be GPL'd, of course.
We use an XServe G5 as a single sign-on and file server for a "lab" of about 14 FreeBSD and Windows XP machines. The computers are used as workstations (and occasionally for light numerical work) by theorists working on quantum information and quantum computation.
Macs seem to be quite popular among the quantum computing community. Ray Laflamme's group (U. of Waterloo and Perimeter Institute) uses them (although maybe they don't have an Xserve), and about 40% of the laptops at a recent quantum information conference I was at were PowerBooks.
Documentation. OS X Server 10.3 ("Panther Server") is nice, but there are just too many areas that are poorly documented. My setup time would have been a quarter what it was if they had really excellent documentation. It's surprising, because Apple's docs on the consumer side are quite good. A lot of Apple's market is relatively inexperienced admins in SOHO or educational settings, and more HOWTO-type documentation would be wonderful.
VPN setup. This one needs some serious help. I (and a lot of other people on Apple's OS X Server Discussion Board) have had a great deal of difficulty getting PPTP working in Panther Server. I also managed to stump Apple's Premium support with a problem with L2TP. Still waiting to hear back, more than a week later.
Firewall setup. The Panther Server GUI interface for setting up firewalls is somewhat broken. Server Admin times out on trying to load mildly complicated rule-sets (say, a group of twelve IP ranges with 15 ports open). The default configuration doesn't make use of ipfw's stateful capabilities, and doesn't block UDP packets. They could really have a better interface and a better default ruleset, or at least an option to set up some stateful rules via the GUI. The setup they have for XML editing of the GUI's port list is cool, though, as is the ipfw.conf setup.
Windows Services / SAMBA. SAMBA still has some bugs and issues which make it annoying to use as a replacement for a Windows-based PDC. Apple should help out the open source community here. In particular, find a good solution to the problem where visible.INI files show up in weird places in a user's roaming profile--having one of these suckers pop up upon login every time a user logs in is annoying. (This happens because SAMBA does not store the "Invisible System File" windows file attribute that would keep these files from being visible. There's a work-around but it's ugly and only partially effective). Also, more GUI-based control of security for Windows file sharing would be good--I don't want to have to dig into the bowels of samba just to learn how to disable LANMAN passwords.
Open Directory. Fix the bugs in Open Directory or Workgroup Manager that prevent entry of "City" (and certain other attributes) in user LDAP records. Set up a better means of storing contact information in the LDAP directory, and document how to configure Mac OS X clients to access it via Address Book.
Backup Solution. There are lots of third-party backup solutions out there for backing up an OS X Server, but none I completely trust to do a bare-metal restore and give me a bootable system. Carbon Copy Cloner? Had issues with it when backing up an iBook via Firewire, so I don't trust it. Rsync? Doesn't handle resource forks. RsyncX? Slower than rsync (too slow for network backup). This would probably be pretty simple for Apple to implement and integrate into Server Admin.
All in all, Panther Server is pretty good, and Tiger Server looks even better. I just hope Apple fixes these things so others are spared the trouble I went through.
...to break RSA. Specifically, I believe that Shor's Algorithm requires 3n qubits, where n is the number of bits of the number you're trying to factor. Multiply by a factor of five to allow some error correction, and you need about 15k qubits to crack 1024-bit RSA.
I work in the field (still an undergrad, but I'm doing some research), and I had the opportunity to meet Michael Nielsen a little while ago when he visited the Perimeter Institute and the University of Waterloo. Nielsen is one of the two authors of the book you mentioned. Out of curiousity, what university do you go to, Misanthropic?
Ah you know most people who use the pair key system of encryption never have to worry about whether primes are factorable or not..
I'm working more on the physics side of quantum computing, not the computer side, so I don't know quite as much about crypto as I'd like. I can see how it might be possible to have perfect forward security (which is what you're talking about) in a real-time two-way communcation scenario, but not in a one-way asynchronous situation like PGPed emails.
Can you elaborate? I couldn't find anything with a Google search.
Thank you. I'm glad someone finally pointed out that we already have a classical (as opposed to quantum) probabilistic algorithm for determining primality. Every other fool on this board is running around wearing his/her tin hat and shouting about RSA being defunct. All this does is push primality testing from the BPP complexity class into the P complexity class. It is significant in the sense that it weakens the argument for BPP being larger than P.
Of course, we also have a polynomial-time algorithm for prime factorization (Shor's Algorithm). It's just that it requires a quantum computer, which is difficult to build. So far, the biggest number factored is 15... 1024 bit keys will be safe for a while yet. I believe it's 15 - 20 years until they're broken, if Moore's Law holds for quantum computers in terms of maximum number of qubits possible (so far, it roughly has, but then, we're only at about 7 qubits).
To help celebrate wIndependence Day (or, perhaps more accurately, WinDependence Day), do we have just not be Windows users, or do we have to use Linux? If it's just about not using Linux, then somebody has already started promoting a similar idea.
Maybe Apple would team up with the Linux community on this one if the event was a little more inclusive. On the other hand, I think OS X and Linux are serious competitors, at least in the PPC world. I know my interest in Linux on PPC died when I saw the terminal in OS X and XDarwin...
In other words, if you're foolish enough to buy a Celine Dion CD, Apple won't help you if you contaminate your iMac with it.
I say, good on them.
BTW, it won't reck your firmware, that's just typical top-notch slashdot journalism fscking up the facts. It's just slightly tricky to eject the disc, and the computer won't boot (in OS 9--X is fine) until it's ejected.
are the way to go... I saw them advertised by an OEM a few years ago. Here's how they work:
The heat pipe contains a liquid/gas that changes phase around the operational temperature of the device you wish to cool. At the hot end of the pipe, the liquid evaporates, sucking up the
heat of vaporization. The vapor travels to cold end of the pipe, and condenses there, releasing heat. The inside of the pipe is specially-designed so as to use capilliary action to draw the liquid back to the hot end of the pipe. What all this does is give you a pipe that has an effective thermal conductivity many, many times better than a hunk of copper (which is already a damn good thermal conductor).
Presumably, you use these pipes to move heat away from the CPU towards the outer chassis of the laptop.
Looking inside my Apple PowerBook G4, I see things that look very much like pipes traveling away from the CPU to other areas of the laptop (areas which tend to get rather warm), and I assume these are the phase-change heat pipes I heard about a few years back. Whether Apple is the only company doing this, I don't know, but it is sure cool, pardon the pun. The fact that the G4 consumes less power is also a big help.
I'm now going to go off on a tangent, mentioning various aspects of physics that are barely relevant, but pretty damn cool. First of all, a bunch of people have suggested using the heat as a power source. While you can use temperature gradients as a power source (think thermocouples), it's damn unlikely to be practical here (the power harnessed would be trivia).
Second, I'd like to point out that heat dissipation is becoming an increasingly-important problem in CPU design. Although we're not there yet, there are theoretical limits on how efficient non-reversible computations can be, in a thermal sense. In other words, each time you manipulate a bit (to be really picky, each time you reset a bit), it must produce a certain amount of heat. This could be the hard limit that breaks Moore's Law for classical, non-reversible computers. The way around this is to use reversible gates (such as in quantum computing), which have no such minimum heat cost. For instance, the XOR gate can be replaced with the controlled-not (CNOT) gate, which is reversible. This would require a major reworking of how we build computers... But I digress... Suffice it to say, heat is a big problem, and it's only going to get worse.
I feel your pain. I bought my TiBook in November. I feel even worse for my friend who bought his a week or two ago, just missing the new model. I warned him it might happen...
I'm also pissed at the lack of support for IrDA. Why'd they include the port if they weren't going to support it?
The way it worked in this test program was a small monitor would gauge your speed (now that I think about it, another monitor guaging breaking habits could also be useful) such that if you were obeying the speed limits, you would get a discount on your insurance.
What a fucking moron you are. I bet you think it's great when pizza places offer free delivery, but a discount on pick-up orders. Don't you see there's no difference between offering a discount to those who choose option X (and of course raising prices overall), versus penalizing those who choose Y, without raising prices.
Also, basing insurance pricing on driving speed is only slightly less unfair than basing it on age and gender. Consider two drivers:
Driver A is a professional race-car driver, and, when he's driving his personal car (which is probably very well maintained, and chosen for optimal handling), he tends to go 5-10 mph over the limit.
Driver B is an octagenarian with mild Parkinson's, and a car almost as old as he is. He tends to drive 5 mph below the limit.
Who's safer? Who would you rather have on the road? Driver A has amazing reflexes, excellent situational awareness, and a well-handling car with good brakes. Driver B's reaction times are probably four times longer, and he probably can't remember the last time he had his brakes done.
This is, of course, an extreme example, but I think it illustrates how ridiculous it is to use an automated device collecting only one or two statistics to decide insurance rates.
A more moderate example: When weather and traffic conditions are good, and the road allows good visibility (no blind corners, etc.), I tend to drive a little over the speed limit. When conditions are bad, I slow down significantly. Contrast this with people who always drive the speed limit, even when the road is wet or icy, and you'll see that my driving habits are a lot safer.
For instance the energy it takes to mine uranium is huge - possibly more than you get from using it in your nuke, to say nothing of the plant construction and maintenance.
This is just one of those ridiculous lies propagated by the anti-nuke crowd. A pellet of uranium an inch long and half an inch in diameter produces almost as much energy as a ton of coal. If mining uranium is that costly, coal must be far, far worse. Yet, somehow, many civilizations did quite well (energy-wise) using coal for decades.
If Saddam is so fucking concerned about his citizens, why doesn't he allow the UN Weapons inspectors back? Many of the sanctions were imposed because he kicked them out a few years ago.
I remember before the Gulf War, when Iraq invaded Kuwait. Bonehead peaceniks like you said that we should impose sanctions, not go to war. Go to war we did, and the peaceniks protested and howled. But then, when Iraq started rebuilding its military and developing weapons of mass destruction, Clinton went the sanction route, and the peaceniks are crying out again.
So, what's it going to be? Sanctions or war? What the fuck are they supposed to do? Hand Saddam a Congressional Medal of Honour every time he invades a weaker neighbour or massacres some of his own citizens?
I heard some version of the story where the total amount involved was $900, and Jobs pocketed half, then split the other half with Woz. When Woz found out, he cried.
Hard to say if there's any truth in any of it, or just one of those persistent net legends.
Now, I know we're talking hypthetically, here, but my guess is that the MPAA wouldn't have the right to sue Jon, and they wouldn't try. Instead, they'd sue some organization (let's call it 2600) run by some guy (Emmanuel Goldstein, for our convenience), who was violating laws concerning the distribution of said programs.
...doesn't mean it's not there, does it? How confident are the makers of stegdetect that no steganographic images would slip past their program? Does their program simply work for all known steg. algorithms, or would it detect some or all kinds of new algorithms?
Also, if I was going to try to send a message via steganography, I wouldn't be doing it with images on Usenet. I'd make some useless personal homepage (god knows there are enough of those already, and nobody visits them), and put my steg. image on there. Or, I would use a more primitive kind of steganography--code words embedded in seemingly innocent messages. There's a hell of a lot more spam on usenet than images, so it would be better concealed that way.
No, a proof would not imply that the original classification as NP-complete was wrong (I assume you mean a proof that NP = P, which would likely take the form of finding a polynomial-time algorithm for an NP-complete problem). Re-read my definition of NP and NP-complete, and you'll see that nowhere do I state that an NP problem must not have a polynomial-time solution. The only additional requirement on NP-complete (as compared with NP) is that there exist a polynomial-time mapping from every problem in NP to that problem. Nothing requires that NP or NP-complete problems be "hard".
There's also no requirement that they be "easy", and, since nobody has found an "easy" NP-complete problem, we suppose (without any strong theoretical reason to do so) that NP != P. Now, we already know that P is contained in NP. If somebody were to find an "easy" solution to an NP-complete problem, it would mean that NP=P. NP-complete would still be a valid classification, although it wouldn't be nearly as interesting anymore (who cares if a problem is NP-complete if NP=P?).
In short, proving that NP=P wouldn't mean anybody screwed up (except all those suckers who trusted their secrets to crypto based on an unproven hypothesis).
The question itself, which was poorly phrased by the poster, is definitely very interesting, and is actually closely related to the subject of a talk I plan to give next year at the Canadian Undergraduate Physics Conference in Halifax.
Now, some people have been getting confused and saying that being in NP-complete only requires there to be a polynomial-time mapping from every problem in NP-complete, and that it does not imply a mapping from NP in general....
It doesn't surprise me any more when Slashdot displays large amounts of ignorance about non-computer topics, but I expected better for something like this. I've been skimming through the +2 and higher comments, and not a single poster has defined NP-complete correctly (this may have changed by the time you read this, but it was true when there were >50 comments at 2 or above).
Here's the correct definition of NP-complete:
To be in NP-complete, a problem must be in NP--that is, it must be a concrete decision problem, and have a polynomial-time verification algorithm (i.e., if somebody hands you a solution to the problem, you can verify that it's correct in polynomial time). Furthermore, there must be a polynomial-time mapping from every problem in NP (not just NP-complete) to your problem.
My source for this is Introduction to Algorithms, by Cormen, Leiserson, and Rivest (yes, that's THE Rivest of cryptography fame), which is part of the MIT Electrical Engineering and Computer Science Series.
Now, some people have been getting confused and saying that being in NP-complete only requires there to be a polynomial-time mapping from every problem in NP. This is an understandable mistake, since the way one usually proves a problem is in NP-complete is by finding a polynomial-time mapping from one NP-complete problem to the problem of interest (which must already have been shown to be in NP). However, since you already know that there are polynomial-time mappings from every problem in NP to the NP-complete problem, there is thus also a polynomial-time mapping from every problem in NP to your problem. The difference here is that efficiently solving an NP-complete problem means you can efficiently solve all NP problems, not just the other NP-complete ones.
The second big error--the one that boggles my mind--is that the poster seems to have confused O(n), which is linear time, with polynomial time. True, O(n) implies polynomial running time, but polynomial-time does not necessarily imply O(n)--you could have O(n^2), O(n^3)...
The third mistake is the implications of any polynomial-time solution to an NP-complete problem--even if it is O(n^1000). A few people here are claiming a polynomial-time solution would be irrelevant if the order of the polynomial was large (giving O(n^1000) as an example of large). For moderately large inputs (and we're really not talking that large), O(n^1000) is better than O(e^n). Taking the example of O(n^1000), n only has to be greater than 10,000 for O(n^1000) to beat O(e^n). Exponentials grow fast, people.
Finally, getting to implications, any polynomial-time solution to any NP-complete problem would instantly destroy public-key cryptography. Even if everybody immediately switched cryptosystems, the implications would be staggering, because someone could have archived all sorts of encrypted transactions, the contents of which are still sensitive. My understanding is that prime factorization is in NP, but not in NP-complete (not that this matters too much, as I explained earlier). Not sure about the math other forms of PK crypto are based on, but I suspect it's also NP.
On the plus side, protein folding simulation is suspected to be in NP (this may have been proven--not sure). If you could do protein folding simulations efficiently, it would make finding a cure to most diseases a hell of a lot easier (and we'd finally be able to figure out what the hell the human genome means).
A rethink on the air network strategy to produce lighter, smaller, more efficient aircraft which possibly fly a bit slower and take shorter 'hops' would bring Fuel Cell flight closer.
This would be a worthwhile trade off for a more environmentally sound and sustainable flight infrastructure.
Even more environmentally friendly would be if everyone just walked. I got news for you--transportation technology is based on getting people where they want to go fast and cheap. Many small planes on short flights means a lot more overhead, and a hell of a lot more fuel spent taking off and landing (the most inefficient parts of flight), not to mention longer travel times.
Slashdot Mirror
IAAP (I am a physicist). I do not work with lasers, but have taken a graduate level course in non-linear optics that primarily focused on lasers.
It is quite possible to damage a pilot's eyes at a range of a few miles, using only commercial laser systems. If done by competent individuals, it would probably involve a pulsed infrared laser (harder to detect, and the eye is more susceptible to near IR than to visible). A Nd:YAG laser (1064 nm) would be ideal.
Since a pulsed laser is used, there's no need for tracking the plane. A single 10-nanosecond pulse would be sufficient. At 10 - 20 pulses per second, you could just scan the sky in the area of the plane.
After reading the story, I did some rough calculations. For the above-mentioned laser, the laser beam would do damage (although likely not sufficient to totally blind the pilot) at ranges of up to two miles, and the beam would have a spot size several meters in diameter at that range. Obviously, with additional optics, range and spot size could be changed.
It seems to me that the laser could simply be mounted to a scope on a tripod (after some careful alignment), and that targetting by hand would work at least some of the time.
All this aside, I don't think the recent cases are anything to be worried about. More likely it's just a nutbar with a relatively weak visible laser (I assume the laser was in the visible range because the pilots reported it, and I doubt commercial planes are equipped to detect IR lasers). If it was someone serious, they'd be using IR lasers, and we wouldn't know until pilots started getting eye damage.
That said, the overall risk of plane crashes from this form of attack is low. If the airport and immediate area are kept secure (and they should be if only to guard against Stinger-style missile attacks), it's very unlikely someone with a commercial laser could get close enough to completely blind a pilot. Military or custom-built research lasers could blind from greater distances, but such systems are very finicky, and I can't see terrorists pulling that off.
Finally, I'd like to address a few points other people have brought up. If the polarization and angle of the beam are chosen correctly, virtually none will be reflected off the plane's window, and all will be transmitted (see Brewster's Angle). For modest laser powers, the damage to the retina will be localized to where the laser beam is imaged, leaving much of the pilot's vision intact. Bad for the pilot, but he could probably still land. For more intense beams, other damage mechanisms come into play (apparently for severe cases there is an actual popping sound perceived by the victim as the laser pulse creates a small shock wave inside the eye), and more of the victim's vision could be damaged.
Protective goggles aren't really an option, as they only protect against one wavelength. Attackers could then switch to a different type of laser (Ti:saph?). Combining goggles leads to virtually no light getting through.
References
Journal of Biomedical Optics 4(3), 337-344 (July 1999).
Big Sky Laser CFR-800 spec sheet
Sloppy writing implies carelessness at best, ineptitude at worst.
Sometimes, sloppy writing is the rational way to go. I've been coming to the realization that writing careful, clear emails is a waste of time, because nobody reads them in any detail anyway.
For several months, my boss and I have been on different continents, communicating only by email. If I take the time to write her a detailed but succinct email, I'll often just get back a two-line response that makes it clear she didn't read half of what I wrote.
Why bother?
*Sigh*. Disney will ruin it--I don't think anything decent has come out of Disney in the past five or ten years, aside from the Pixar stuff. Does anyone know if Disney owns the rights to The Incredibles sequel? That would be really unfortunate...
Perhaps Pixar can buy the rights back.
Ah, but simulating things at a quantum level is exponentially hard. In other words, adding a single atom to your simulation doubles the complexity of the classical computation. Even if Moore's Law continues to hold, that means the size of the largest simulation we can handle grows only linearly with time.
The only solution is a quantum computer, for which the computational complexity grows linearly with the size of the simulation.
Disclaimer: I'm a graduate student doing research on quantum computing in optical lattices. I'm not affiliated with the group that published this article.
This result is quite exciting, because it demonstrates the feasibility of some of the techniques necessary for an optical lattice-based quantum computer. Imagine taking their 1-D lattice and turning it into a 3-D lattice, with about 30 atoms in each direction. That's a whole lot of qubits...
So what are the next steps?
1) A new means of addressing atoms (selecting one or two atoms on which to perform operations while excluding the rest) is necessary. Their magnetic gradient technique works fine for a small 1-D lattice, but it would likely be impractical for a large 3-D lattice (Maxwell's equation div B = 0 gives one major obstacle, which would require fancy tricks to overcome).
2) One and two-qubit gates need to be demonstrated using an appropriate addressing scheme.
3) Error correction, which would likely require quantum non-demolition measurements to check to see if an atom had been lost from a lattice site. Translation: we need to be able to measure if we've lost an atom from a lattice site, without disturbing the atom's state (i.e. measuring whether it's |0> or |1>).
4) Full-blown fault-tolerant computation.
My group plans to solve (1) using an addressable optical lattice. What that means is that the lattice spacing is sufficiently large that a laser can be focused on an individual atom (in 3-D, two lasers in orthogonal directions would be used). I'm currently doing simulations of one-qubit gates in this scheme.
That brings me to my question for slashdot: Some of the simulations I'll be doing (specifically, studying decoherence in the one and two qubit gates) will be very computationally intensive. They're also embarrassingly parallel, as they're essentially quantum Monte Carlo simulations. Would people be interested in a BOINC-based distributed computing project (a la SETI@home) to help develop quantum computers? If so, what kinds of things would help you get involved? Would you be interested in helping develop the software (it's C++)?
I probably won't be at that stage for another six months to a year, but it would be helpful to me to start planning now. I have just (last night) completed the core simulation engine, and would need to add code for decoherence, as well as adapt it to BOINC. The code will be GPL'd, of course.
We use an XServe G5 as a single sign-on and file server for a "lab" of about 14 FreeBSD and Windows XP machines. The computers are used as workstations (and occasionally for light numerical work) by theorists working on quantum information and quantum computation.
Macs seem to be quite popular among the quantum computing community. Ray Laflamme's group (U. of Waterloo and Perimeter Institute) uses them (although maybe they don't have an Xserve), and about 40% of the laptops at a recent quantum information conference I was at were PowerBooks.
Documentation. OS X Server 10.3 ("Panther Server") is nice, but there are just too many areas that are poorly documented. My setup time would have been a quarter what it was if they had really excellent documentation. It's surprising, because Apple's docs on the consumer side are quite good. A lot of Apple's market is relatively inexperienced admins in SOHO or educational settings, and more HOWTO-type documentation would be wonderful.
.INI files show up in weird places in a user's roaming profile--having one of these suckers pop up upon login every time a user logs in is annoying. (This happens because SAMBA does not store the "Invisible System File" windows file attribute that would keep these files from being visible. There's a work-around but it's ugly and only partially effective). Also, more GUI-based control of security for Windows file sharing would be good--I don't want to have to dig into the bowels of samba just to learn how to disable LANMAN passwords.
VPN setup. This one needs some serious help. I (and a lot of other people on Apple's OS X Server Discussion Board) have had a great deal of difficulty getting PPTP working in Panther Server. I also managed to stump Apple's Premium support with a problem with L2TP. Still waiting to hear back, more than a week later.
Firewall setup. The Panther Server GUI interface for setting up firewalls is somewhat broken. Server Admin times out on trying to load mildly complicated rule-sets (say, a group of twelve IP ranges with 15 ports open). The default configuration doesn't make use of ipfw's stateful capabilities, and doesn't block UDP packets. They could really have a better interface and a better default ruleset, or at least an option to set up some stateful rules via the GUI. The setup they have for XML editing of the GUI's port list is cool, though, as is the ipfw.conf setup.
Windows Services / SAMBA. SAMBA still has some bugs and issues which make it annoying to use as a replacement for a Windows-based PDC. Apple should help out the open source community here. In particular, find a good solution to the problem where visible
Open Directory. Fix the bugs in Open Directory or Workgroup Manager that prevent entry of "City" (and certain other attributes) in user LDAP records. Set up a better means of storing contact information in the LDAP directory, and document how to configure Mac OS X clients to access it via Address Book.
Backup Solution. There are lots of third-party backup solutions out there for backing up an OS X Server, but none I completely trust to do a bare-metal restore and give me a bootable system. Carbon Copy Cloner? Had issues with it when backing up an iBook via Firewire, so I don't trust it. Rsync? Doesn't handle resource forks. RsyncX? Slower than rsync (too slow for network backup). This would probably be pretty simple for Apple to implement and integrate into Server Admin.
All in all, Panther Server is pretty good, and Tiger Server looks even better. I just hope Apple fixes these things so others are spared the trouble I went through.
...to break RSA. Specifically, I believe that Shor's Algorithm requires 3n qubits, where n is the number of bits of the number you're trying to factor. Multiply by a factor of five to allow some error correction, and you need about 15k qubits to crack 1024-bit RSA.
I work in the field (still an undergrad, but I'm doing some research), and I had the opportunity to meet Michael Nielsen a little while ago when he visited the Perimeter Institute and the University of Waterloo. Nielsen is one of the two authors of the book you mentioned. Out of curiousity, what university do you go to, Misanthropic?
Ah you know most people who use the pair key system of encryption never have to worry about whether primes are factorable or not..
I'm working more on the physics side of quantum computing, not the computer side, so I don't know quite as much about crypto as I'd like. I can see how it might be possible to have perfect forward security (which is what you're talking about) in a real-time two-way communcation scenario, but not in a one-way asynchronous situation like PGPed emails.
Can you elaborate? I couldn't find anything with a Google search.
Thank you. I'm glad someone finally pointed out that we already have a classical (as opposed to quantum) probabilistic algorithm for determining primality. Every other fool on this board is running around wearing his/her tin hat and shouting about RSA being defunct. All this does is push primality testing from the BPP complexity class into the P complexity class. It is significant in the sense that it weakens the argument for BPP being larger than P.
Of course, we also have a polynomial-time algorithm for prime factorization (Shor's Algorithm). It's just that it requires a quantum computer, which is difficult to build. So far, the biggest number factored is 15... 1024 bit keys will be safe for a while yet. I believe it's 15 - 20 years until they're broken, if Moore's Law holds for quantum computers in terms of maximum number of qubits possible (so far, it roughly has, but then, we're only at about 7 qubits).
To help celebrate wIndependence Day (or, perhaps more accurately, WinDependence Day), do we have just not be Windows users, or do we have to use Linux? If it's just about not using Linux, then somebody has already started promoting a similar idea.
Maybe Apple would team up with the Linux community on this one if the event was a little more inclusive. On the other hand, I think OS X and Linux are serious competitors, at least in the PPC world. I know my interest in Linux on PPC died when I saw the terminal in OS X and XDarwin...
In other words, if you're foolish enough to buy a Celine Dion CD, Apple won't help you if you contaminate your iMac with it.
I say, good on them.
BTW, it won't reck your firmware, that's just typical top-notch slashdot journalism fscking up the facts. It's just slightly tricky to eject the disc, and the computer won't boot (in OS 9--X is fine) until it's ejected.
Looking inside my Apple PowerBook G4, I see things that look very much like pipes traveling away from the CPU to other areas of the laptop (areas which tend to get rather warm), and I assume these are the phase-change heat pipes I heard about a few years back. Whether Apple is the only company doing this, I don't know, but it is sure cool, pardon the pun. The fact that the G4 consumes less power is also a big help.
I'm now going to go off on a tangent, mentioning various aspects of physics that are barely relevant, but pretty damn cool. First of all, a bunch of people have suggested using the heat as a power source. While you can use temperature gradients as a power source (think thermocouples), it's damn unlikely to be practical here (the power harnessed would be trivia).
Second, I'd like to point out that heat dissipation is becoming an increasingly-important problem in CPU design. Although we're not there yet, there are theoretical limits on how efficient non-reversible computations can be, in a thermal sense. In other words, each time you manipulate a bit (to be really picky, each time you reset a bit), it must produce a certain amount of heat. This could be the hard limit that breaks Moore's Law for classical, non-reversible computers. The way around this is to use reversible gates (such as in quantum computing), which have no such minimum heat cost. For instance, the XOR gate can be replaced with the controlled-not (CNOT) gate, which is reversible. This would require a major reworking of how we build computers... But I digress... Suffice it to say, heat is a big problem, and it's only going to get worse.
I feel your pain. I bought my TiBook in November. I feel even worse for my friend who bought his a week or two ago, just missing the new model. I warned him it might happen...
I'm also pissed at the lack of support for IrDA. Why'd they include the port if they weren't going to support it?
The way it worked in this test program was a small monitor would gauge your speed (now that I think about it, another monitor guaging breaking habits could also be useful) such that if you were obeying the speed limits, you would get a discount on your insurance.
What a fucking moron you are. I bet you think it's great when pizza places offer free delivery, but a discount on pick-up orders. Don't you see there's no difference between offering a discount to those who choose option X (and of course raising prices overall), versus penalizing those who choose Y, without raising prices.
Also, basing insurance pricing on driving speed is only slightly less unfair than basing it on age and gender. Consider two drivers:
Driver A is a professional race-car driver, and, when he's driving his personal car (which is probably very well maintained, and chosen for optimal handling), he tends to go 5-10 mph over the limit.
Driver B is an octagenarian with mild Parkinson's, and a car almost as old as he is. He tends to drive 5 mph below the limit.
Who's safer? Who would you rather have on the road? Driver A has amazing reflexes, excellent situational awareness, and a well-handling car with good brakes. Driver B's reaction times are probably four times longer, and he probably can't remember the last time he had his brakes done.
This is, of course, an extreme example, but I think it illustrates how ridiculous it is to use an automated device collecting only one or two statistics to decide insurance rates.
A more moderate example:
When weather and traffic conditions are good, and the road allows good visibility (no blind corners, etc.), I tend to drive a little over the speed limit. When conditions are bad, I slow down significantly. Contrast this with people who always drive the speed limit, even when the road is wet or icy, and you'll see that my driving habits are a lot safer.
For instance the energy it takes to mine uranium is huge - possibly more than you get from using it in your nuke, to say nothing of the plant construction and maintenance.
This is just one of those ridiculous lies propagated by the anti-nuke crowd. A pellet of uranium an inch long and half an inch in diameter produces almost as much energy as a ton of coal. If mining uranium is that costly, coal must be far, far worse. Yet, somehow, many civilizations did quite well (energy-wise) using coal for decades.
If Saddam is so fucking concerned about his citizens, why doesn't he allow the UN Weapons inspectors back? Many of the sanctions were imposed because he kicked them out a few years ago.
I remember before the Gulf War, when Iraq invaded Kuwait. Bonehead peaceniks like you said that we should impose sanctions, not go to war. Go to war we did, and the peaceniks protested and howled. But then, when Iraq started rebuilding its military and developing weapons of mass destruction, Clinton went the sanction route, and the peaceniks are crying out again.
So, what's it going to be? Sanctions or war? What the fuck are they supposed to do? Hand Saddam a Congressional Medal of Honour every time he invades a weaker neighbour or massacres some of his own citizens?
I heard some version of the story where the total amount involved was $900, and Jobs pocketed half, then split the other half with Woz. When Woz found out, he cried.
Hard to say if there's any truth in any of it, or just one of those persistent net legends.
Funny you don't mention Clinton, who was quite possibly the most corrupt president of the last century. Now who's biased?
Now, I know we're talking hypthetically, here, but my guess is that the MPAA wouldn't have the right to sue Jon, and they wouldn't try. Instead, they'd sue some organization (let's call it 2600) run by some guy (Emmanuel Goldstein, for our convenience), who was violating laws concerning the distribution of said programs.
...doesn't mean it's not there, does it? How confident are the makers of stegdetect that no steganographic images would slip past their program? Does their program simply work for all known steg. algorithms, or would it detect some or all kinds of new algorithms?
Also, if I was going to try to send a message via steganography, I wouldn't be doing it with images on Usenet. I'd make some useless personal homepage (god knows there are enough of those already, and nobody visits them), and put my steg. image on there. Or, I would use a more primitive kind of steganography--code words embedded in seemingly innocent messages. There's a hell of a lot more spam on usenet than images, so it would be better concealed that way.
No, a proof would not imply that the original classification as NP-complete was wrong (I assume you mean a proof that NP = P, which would likely take the form of finding a polynomial-time algorithm for an NP-complete problem). Re-read my definition of NP and NP-complete, and you'll see that nowhere do I state that an NP problem must not have a polynomial-time solution. The only additional requirement on NP-complete (as compared with NP) is that there exist a polynomial-time mapping from every problem in NP to that problem. Nothing requires that NP or NP-complete problems be "hard".
There's also no requirement that they be "easy", and, since nobody has found an "easy" NP-complete problem, we suppose (without any strong theoretical reason to do so) that NP != P. Now, we already know that P is contained in NP. If somebody were to find an "easy" solution to an NP-complete problem, it would mean that NP=P. NP-complete would still be a valid classification, although it wouldn't be nearly as interesting anymore (who cares if a problem is NP-complete if NP=P?).
In short, proving that NP=P wouldn't mean anybody screwed up (except all those suckers who trusted their secrets to crypto based on an unproven hypothesis).
The question itself, which was poorly phrased by the poster, is definitely very interesting, and is actually closely related to the subject of a talk I plan to give next year at the Canadian Undergraduate Physics Conference in Halifax.
Pardon me, the fourth paragraph should read:
Now, some people have been getting confused and saying that being in NP-complete only requires there to be a polynomial-time mapping from every problem in NP-complete, and that it does not imply a mapping from NP in general....
It doesn't surprise me any more when Slashdot displays large amounts of ignorance about non-computer topics, but I expected better for something like this. I've been skimming through the +2 and higher comments, and not a single poster has defined NP-complete correctly (this may have changed by the time you read this, but it was true when there were >50 comments at 2 or above).
Here's the correct definition of NP-complete:
To be in NP-complete, a problem must be in NP--that is, it must be a concrete decision problem, and have a polynomial-time verification algorithm (i.e., if somebody hands you a solution to the problem, you can verify that it's correct in polynomial time). Furthermore, there must be a polynomial-time mapping from every problem in NP (not just NP-complete) to your problem.
My source for this is Introduction to Algorithms, by Cormen, Leiserson, and Rivest (yes, that's THE Rivest of cryptography fame), which is part of the MIT Electrical Engineering and Computer Science Series.
Now, some people have been getting confused and saying that being in NP-complete only requires there to be a polynomial-time mapping from every problem in NP. This is an understandable mistake, since the way one usually proves a problem is in NP-complete is by finding a polynomial-time mapping from one NP-complete problem to the problem of interest (which must already have been shown to be in NP). However, since you already know that there are polynomial-time mappings from every problem in NP to the NP-complete problem, there is thus also a polynomial-time mapping from every problem in NP to your problem. The difference here is that efficiently solving an NP-complete problem means you can efficiently solve all NP problems, not just the other NP-complete ones.
The second big error--the one that boggles my mind--is that the poster seems to have confused O(n), which is linear time, with polynomial time. True, O(n) implies polynomial running time, but polynomial-time does not necessarily imply O(n)--you could have O(n^2), O(n^3)...
The third mistake is the implications of any polynomial-time solution to an NP-complete problem--even if it is O(n^1000). A few people here are claiming a polynomial-time solution would be irrelevant if the order of the polynomial was large (giving O(n^1000) as an example of large). For moderately large inputs (and we're really not talking that large), O(n^1000) is better than O(e^n). Taking the example of O(n^1000), n only has to be greater than 10,000 for O(n^1000) to beat O(e^n). Exponentials grow fast, people.
Finally, getting to implications, any polynomial-time solution to any NP-complete problem would instantly destroy public-key cryptography. Even if everybody immediately switched cryptosystems, the implications would be staggering, because someone could have archived all sorts of encrypted transactions, the contents of which are still sensitive. My understanding is that prime factorization is in NP, but not in NP-complete (not that this matters too much, as I explained earlier). Not sure about the math other forms of PK crypto are based on, but I suspect it's also NP.
On the plus side, protein folding simulation is suspected to be in NP (this may have been proven--not sure). If you could do protein folding simulations efficiently, it would make finding a cure to most diseases a hell of a lot easier (and we'd finally be able to figure out what the hell the human genome means).
A rethink on the air network strategy to produce lighter, smaller, more efficient aircraft which possibly fly a bit slower and take shorter 'hops' would bring Fuel Cell flight closer.
This would be a worthwhile trade off for a more environmentally sound and sustainable flight infrastructure.
Even more environmentally friendly would be if everyone just walked. I got news for you--transportation technology is based on getting people where they want to go fast and cheap. Many small planes on short flights means a lot more overhead, and a hell of a lot more fuel spent taking off and landing (the most inefficient parts of flight), not to mention longer travel times.