While physicists search to find ways to build quantum computers, there is little evidence on how useful these machines will be. The computational complexity theory has come to bear on this question.
To date, there has been some success in building quantum computers with a small number of quantum bits (qubits). As there are many issues to overcome before a large-scale quantum computer could become a reality, an obvious question comes to mind: Can such a machine be built?
Further details: A complexity theorist's view of quantum computing