Hundreds of years, if it's possible at all. There are several main technologies that are on display in a holodeck, some of which we are closer to and some of which we are further away from.
The most obvious, of course, is the holograms themselves. They must be free standing and able to move around in a 3D space to meet the requirements. We have basic holography technology at the moment, but the way it works would be utterly useless in this context; currently, it works by recording how light scatters off of an object and then reconstructing that light by bouncing a programmed laser off of a rapidly rotating mirror.
That means that the hologram is not free standing, cannot easily move and is limited to pre-recorded images, none of which are issues for the holodeck. So we'd need to essentially start again and take a whole new approach to holography to achieve this.
The second important piece of technology, and arguably the most 'impossible' is the technology to make the holograms solid. I believe this is explained in the show as being some sort of force-field, similar to the shields around the ship, but I could be wrong. Regardless, it would take something similar to that, that could move and be deformed anywhere in the room.
This is definitely in the realms of technology that is unimaginable to us how it could work. If it is possible at all, it isn't technology we're likely to see within the next hundred years. This is an iPhone, and we haven't had Alexander Graham Bell yet. There is a potential, however, that the answer to this problem could solve the previous one, as it might allow projection onto these surfaces, or these surfaces themselves might be able to reflect light in the right ways.
There are two other pieces of technology on display within a holodeck that we don't have yet, but arguably aren't necessary for the 'basic' holodeck experience.
The first of these is very advanced A.I., including speech recognition and the ability to judge to safety of a situation. In the holodeck, the 'characters' react seamlessly and in a very human like way to the actions of the players, easily passing the Turing test and giving every impression of genuine intelligence.
This is something we're moving towards, however, and while we're a decent way off of the level we would require for a holodeck, we're likely to get there before we develop some of the other pieces of technology needed.
As such, I don't really see this as being too much of a barrier to the holodeck's development. We also probably wouldn't need it to be as good as it is on The Next Generation for it to be an enjoyable experience. It's probably the easiest to develop, or at least the piece of technology we're closest to having.
The second, and probably the most 'impossible' of all the technologies here, is the replicator technology on display. Within the holodeck, some smaller items aren't holograms, and are instead replicated, creating real versions of the items. This has been demonstrated by a character eating an apple, or similar. This is done, I believe, just to add that little extra level of intractability, where even the advanced holographic technology couldn't recreate the experience.
Tea. Earl Grey. Hot.
Again, this is technology that we cannot even imagine how it might work, and is at the level of appearing magical to us. We have not achieved anything that we think of as being a beginning on the road to this technology. It might even violate some laws of physics as we understand them today, and as such is likely something that is hundreds to thousands of years in the future. Fortunately for us, it isn't strictly needed for a holodeck, though it does improve the experience.
About the author: Matt Sutton, I have spent too much time thinking about Star Trek
Technologically, how far away are we from creating a "holodeck" ala "Star Trek: The Next Generation"? originally appeared on Quora. You can follow Quora on Twitter, Facebook and Google+.