You just need millions of computers, millions of petabytes of net traffic and a lot of time to have the same index as Google. Easy.
For example, look at how useless Bing is. And that's Microsoft!
Prediction: some near-future Snowden document release will catapult DuckDuckGo or some other privacy-oriented search alternative into the limelight in a hockeystick curve growth kind of way. Maybe something that proves the NSA is firehose sharing de-anonymised Google/Bing search data with HealthCare Companies or the Insurance Industry or the IRS, and that there's widespread punitive action going on based on simplistic or poorly thought out responses to people's search history (people being denied health insurance because they did a few too many Google searches when their mother was diagnosed with cancer, or car insurance rates being raised across the board for people who search wine labels online...) All of a sudden someone who's "good enough" at search, but has TOR hidden service endpoints and nothing associated with them that comes under Five Eyes legal jurisdictions is going to look worthwhile switching to.
If some revelation like that were to happen, people would be outraged, they'd demand regulation, and meanwhile they'd continue to use Google/Bing; maybe some would switch to Incognito windows, but that's about it, in my opinion.
What if you build it like a distributed network focusing on anonymity / less centralization / less advertisement. Of course, it will be a completely different business then google, but this kind of search competition could quickly destroy google business.
Of course, crawling, indexing and distributing billions of URL's is not an easy job, I don't say that it can be done by someone over the weekend, but you don't have to be Microsoft at all to be able to do it.
Big companies like Google has a big inertia. Google built a complete industry (the advertising) over their centralized search system, which is very hard to be changed. This is why they are very vulnerable.
Attempting to compete with Google is akin to creating a new, marginally better implementation of a really widespread standard and attempting to market it: nobody is going to use it.
But far less if you don't personalize everything?