Could please someone give a layman's explanation for this bombshell?
> Assume I hide a ball in a cabinet with a million drawers. How many drawers do you have to open to find the ball? Sometimes you may get lucky and find the ball in the first few drawers but at other times you have to inspect almost all of them. So on average it will take you 500,000 peeks to find the ball. Now a quantum computer can perform such a search looking only into 1000 drawers. This mind boggling feat is known as Grover’s algorithm.
If 999,000 drawers are left unopened, how can the algorithm guarantee that the ball will be found?
Disclaimer: I do not know much about quantum computation, but got interested in it only very recently. I'll give you my understanding, take it with a grain of salt.
AFAIU, Grover's algorithm is not really an algorithm of search of unstructured data, like phone book, but rather a quantum algorithm for inverting a function. The way it is related to search is that you have to have a computable function f such that f(x)=1 if 'x' is one of the million 'boxes' and f(x)=0 otherwise. Your goal is to find that one 'x' (assumption being, of course, is that 'f' is not easily inversible).
How would traditional computer solve the problem - by going through all x's and once f(x)=1, you have your x.
The power of quantum computer is that the state of the quantum computer is the quantum superposition of many classic states. As such quantum computer may perform a computation of 'f' at the superposition of many 'x's at one and get a superposition of function results (that can be measured with a certain degree of uncertainty)
The algorithm essentially goes through superpositions narrowing sets of possible candidate x's pretty fast. Algorithm is inherently probabilistic but the point is that you can converge to x that is your correct x with a high degree of certainty in a (relatively) small amount of steps.
If anyone has more qualified explanation to offer I will be happy to stand corrected.
"AFAIU, Grover's algorithm is not really an algorithm of search of unstructured data, like phone book, but rather a quantum algorithm for inverting a function."
Grover's search algorithm works both for inverting a function and for database search. But if you want to use it for database search, then your database needs to be accessible in coherent superposition, i.e., in some sort of "quantum RAM." For many problems, this probably does not make sense.
The 'database' is not really a database in the sense that it stores a list of things. Instead the database is like a predicate p(x) where x ranges over some finite set (you can assume that this set is just 0..N). So if p(x) really has to search a database to determine whether x is the one you want, then the algorithm doesn't work. It is assumed that executing p(x) is fast. Classically you'd have to call the predicate on each of 0..N to find the x for which p(x) = 1. In a quantum computer you can start with a superposition of all states 0..N (think probability distribution over 0..N), and by cleverly applying a quantum analog to a predicate p in Grover's algorithm you can change this probability distribution so that the x for which p(x) is true gets more and more likely (i.e. more and more probability mass). This probability mass increases fast enough that on average you need O(sqrt(N)) steps to find the x that satisfies p(x).
Thanks for asking this question so I didn't have to.. this sounds so interesting but its a bit hard to grasp not having a science background in this field
I feel compelled to point out (as is done here http://michaelnielsen.org/blog/quantum-computing-for-everyon...) that it is possible that no such explanation exists. My understanding is that most people doing theoretical research in quantum computing don't need to have intuitive explanations for their results, since the calculations work themselves out. This is a depressing but honest observation.
I found quantum mechanics courses very frustrating for exactly this reason, especially in grad school, when the calculations became especially dense and the rationale impenetrable (I have since left physics). Occasionally there would be some little gem of insight into a particular phenomena where the result could be explained in a clear way, but the default approach was to just "do the calculation".
I can't explain exactly how a quantum computer works (because I don't understand it myself) but I will say that the reason the kind of analogy given above might make sense from a quantum mechanical perspective is that the state of the system and the operations that mutate the state have semantics different from classical computers. In particular, the state of the system is given by a bunch of complex numbers, which you can think of as a collection of arrows on the plane. The length and direction that these arrows are pointed in determines the probability for a bit having a particular sign. For example if an arrow is aligned more east-to west the measured classical bit will more likely be a 1, whereas if it is aligned north to south, the bit will tend to be a zero. The tricky part comes when one tries to consider how the state changes in time when subject to some operations. Fundamental particles like electrons or photons are "indistinguishable", which is to say that there are no properties intrinsic to a particular particle that allow one to distinguish it from another such particle of the same type. The result is that the arrows describing our bits (which we can think of as fundamental particles) become coupled, or entangled. Unlike classical operations on bits which one can construct by composing operations of single bits separately, quantum operations mutate the state of the whole system, which affects all the directions of our arrows (and thus the probability for realizing a measured classical state) simultaneously, so long as this entanglement can be maintained. The logic of how these arrows mutate is the complicated part, but this is how the quantum computer achieves its properties. [deleted a long and ultimately unhelpful explanation].
"My understanding is that most people doing theoretical research in quantum computing don't need to have intuitive explanations for their results, since the calculations work themselves out."
I don't believe this. Maybe your classical intuition is wrong, but that doesn't mean you can't develop a quantum intuition. Quantum theory is just a natural generalization of probability theory (with "list of probabilities adding to one" replaced by "list of amplitudes whose squares add to one"), so particularly for anyone who thinks much about randomized algorithms the intuition is very similar.
It's an interesting question: how those who work on quantum algorithms think about quantum algorithms. As someone who worked on quantum algorithms for many years, the interesting intuition that I developed was not what made quantum algorithms tick, but more along the lines of "when is a method likely to NOT yield a quantum speedup." That is I found I could pretty quickly tell when I was doing something that had a nice classical analogy and was therefore doomed to failure. Classic examples where when your intuition about why you might get a speedup involved exploring an exponentially large solution space without some reason that interference could be used to help dig out the interesting parts of the global superposition you created.
An interesting example of how one discovers a quantum algorithm is the story of the NAND tree algorithm (See http://www.scottaaronson.com/blog/?p=207 for a nice explanation.) Quite literally the quantum algorithm was discovered by thinking about interference of particles hoping around, combined with physicists uncanny ability to calculate scattering cross sections. Crazy stuff!
Google Analytics seems somehow less harmful than AdSense. Almost every big website has some kind of analytics running. I assume that GA data isn't sold to advertisers, but I'm not sure.
> "I mean, I literally don't think there's anything to be learned from other people's stuff."
That is exactly what happened with Color, which Nguyen never even bothered to test. "I'm not here to practice. I'm here to play," says Nguyen[...]
That pull quote blew me away. This guy comes across as totally arrogant, plain and simple. Even Steve Jobs, who Nguyen apparently worships, got inspiration from other people's products. If nothing else, this article is a great warning against ever working for this guy.
I'm naive when it comes to anything related to VC's and funding, but I'm pretty sure if I had a ton of money to invest, it wouldn't be anywhere near someone like that. Even after reading the article, I don't think I fully understand why he can secure funding so easily.
VCs know that most of their investments aren't going to pan out. When they evaluate companies, they aren't worrying about whether they'll fail. Even the good companies fail. What the VCs are worried about is that they're going to say no to Facebook, and then have to explain 5 years from now how the fuck they possibly could have said no to Facebook.
What that seems to mean is that if you:
* have a persona that at least superficially seems driven, ambitious, likely to succeed, and
* you tell a convincing story about a market that might experience explosive growth, and
* you have any kind of track record of any sort to make it hard to write you off as a total bozo, and
* you have some sales skill, so you can manage the pitch process and create pressure to VC firms, then
you're probably fundable even if you think testing means "practicing instead of really playing".
These kinds of pitches seem very different from the kinds of things people write in Show-HN: postings. In particular, these pitches aren't meant to be reasonable.
This is way more of a response than you were looking for; sorry, I just had to get this out, since all I can think of when I read about Color is how good an illustration it is of VC cliches.
That is why VCs never really say no, because if you do start turning into the next Facebook in the months after you meet them, they want to be able to come back and say 'ye, remember us, sure, we would love to invest!'
I had this happen to me first hand, more than once. When raising money ~5 years ago a high profile VC stopped replying to my emails. Around 2 years later when I was associated with a high-profile project he emailed me out of the blue and asked me up to lunch. As we sat down with coffee, I said to him 'I haven't talked to you in a while, this whole time I thought you thought that I suck'. He laughed and said 'ye we decided not to invest in that'.. urgh. I found it funny and we talked about VCs not saying no for the first 10 minutes.
I continued to make light of it and at the end of that meeting after talking about a number of projects, I said 'I will take 7 days of no email as a no'.
I think what he's saying is that if you can act like this guy does, you can probably make a lot of money without ever having a decent shot at providing the value. And that VCs will continue paying you for the act.
Or he could be saying that if you can come up with a move clever way of investing that avoids projects like these you may be able to be a better VC firm than the ones that currently exist.
Let me sketch the exploit, assuming you are not that guy.
Find someone who has done more than one highly impressive thing, prefereably in approximately the same line, who seems high energy and sociable. If they have anything resembling sales experience that's a big plus. One of the best hunting grounds will be in and around universities, as they're full of people with not much money and confidence that's higher than is justified, and some of them will be much more impressive than their age mates. Find one.
Harvest startup ideas by say, looking at previous Show HN posts, or doing a Madlib generator on the Crunchbase DB for X of Y, and look for something that you can build a good story about explosive growth around, or have what you think is a good idea already.
Sell your ambitious young go-getter on your idea, or on you, somehow, and start pitching VCs with your incredible story of wild growth and fantastic riches. Meanwhile iterate on your idea. Pivot if it looks like a good idea, and hope and pray for growth while pitching VCs all the freaking time.
Basically, have an idea that could conceivably grow explosively and have a business guy with previous record of Impressiveness, capacity to Believe in your Great Idea, and the ability to Sell Stuff, including your Awesome Idea.
If you are that guy, and you can program your own mockup and iterate you might be able to get into YC as a single founder.
I would appreciate a much expanded version of what you just said. I am aware that Poe's Law states more or less that no parody is so extreme that it cannot be taken seriously by at least one person in the faction the author is atempting to parody.
I always felt that extremeness (extremity?) is not necessary in the statement of Poe's Law but I could never find a good example. What you said sounded like a mockery of the YC process, but I'm not sure. The 2 have something in common... attention to detail? (Poe's Law: the parody and the parodied are both outrageous in their own ways.) In light of your discovery, I might restate Poe's Law thusly: no parody can be so ardent that it cannot be mistaken for what it parodies. What do you think about punctuation to indicate the state of being serious?
I think that punctuation to indicate seriousness/sarcasm would never catch on because it would interfere with deniability, deliberate obscurity, signalling and (im)plausible deniability.
I wasn't really joking at all with my description. I mean there are almost certainly groups that fit that description perfectly among YC alumni.
The halo created around some of the people that exhibit the qualities you mention is a really powerful motivator.
The only thing I would add is the fact that you have to know all the players and all the buzz and buzz words.
You don't want to say "no I don't know who Fred Wilson is or who Mike Arrington or PG is etc. Or you're not up on what's going on in the startup community. (Which could happen with someone who has a killer track record from a different industry.) In other words you know the lay of the land.
I might suggest cough having the players know you. There's a famous line in Chicago politics: "Don't be sent by nobody" (An apocryphal applicant, on asking for a job at a local politician's office, was asked "Who sent you?" "Nobody." "Kid, one piece of advice: don't be sent by nobody.")
PG, this is only tangentially related, but I've noticed you quite often use phrases like "starting a startup".
Considering you're an excellent writer, I figured you must have a reason for employing redundancy. Is there a reason you don't say "starting a business" or "starting a company"?
Because I'm writing specifically about how to start a startup and only incidentally about how to start a business. The redundancy is phonetic, not semantic.
If someone had told me his work had been done by a devoted team of a dozen people, I'd still be tremendously impressed that only twelve people managed to accomplish so much. The fact that it's one man? It's chilling.
Try looking at things another way—he's generously provided us all with an incredible foundation upon which to build our own things. After having read a few of his essays, I certainly feel changed.
> But I think it’s curious that Facebook has reacted so strongly to Google+: for such a small network (relatively) they seem quite afraid of it, going to the point of trying to match all of its innovations.
Why is this curious?
A giant, appallingly successful company (believed by many to be "the internet") launched a beautifully designed, direct competitor to your only product. They promote their competing product on every webpage they own, and they have gone so far as to stake employee compensation on the success of their competing product.
Why on Earth wouldn't Facebook be afraid? Why wouldn't they react strongly?
This post fails to support its titular claim: that Facebook is "stumbling" all over itself. Normal, ad-clicking, non-social-media-expert users love Facebook. They love being connected, and they love broadcasting to world. Facebook is stumbling only once those users leave.
Really hard to say. We started experimenting with the idea back in March, but didn't start putting fulltime nights into it until August. I'd say a little over a thousand man-hours over the span of 6 months, but I may be well off the mark.
It was a fruitful experience and if we want to count in the hours of reading and studying that this project has spawned, it would be much more than that.
Anyways, the real question is "how much did it cost?":
$1600+ in sushi dinners! :)
Also, do you think the "Built with" blurb at the bottom adds value to the site? I know I think it's cool when I see stuff like that, but I can't imagine a non-developer caring.
I don't think it adds value, but meh, I just added it and forgot about it honestly haha.
Basically, I wanted to originally create a documenting system to track bugs, so that is where the idea originally came from. I was basically trying to find a good domain, and dcmntr.com was available.
The way I remember it is to just spell 'documenter' without any vowels
> Assume I hide a ball in a cabinet with a million drawers. How many drawers do you have to open to find the ball? Sometimes you may get lucky and find the ball in the first few drawers but at other times you have to inspect almost all of them. So on average it will take you 500,000 peeks to find the ball. Now a quantum computer can perform such a search looking only into 1000 drawers. This mind boggling feat is known as Grover’s algorithm.
If 999,000 drawers are left unopened, how can the algorithm guarantee that the ball will be found?