Are there "quantum calculations" that can make a quantum system take as long as an average supercomputer to solve?

Are there "quantum calculations" that can make a quantum system take as long as an average supercomputer to solve?

Yes. The complexity class QMA is the quantum analogue of NP, so "QMA-complete" problems are thought to have exponential time complexities on quantum computers. Since QMA is a subset of PSPACE problem (whether it's a strict subset is unknown), which are well studied in classical computing, all PSPACE-complete problems are hard to solve on a quantum computing. For example, Super Mario Bros. would be difficult for a quantum computer to solve.

Also, will quantum computers make cryptocurrency obsolete?

Quantum computers can solve most types of classical encryption in polynomial time because they're usually based on NP-complete problems and quantum computers can factor numbers in polynomial time. So cryptocurrency would need to adopt a "quantum proof" cryptography standard.

Is it possible the government already has quantum computers but hasn't revealed them to keep the advantage?

Almost certainly no. The vast majority of research in quantum information and computing is done in university settings where research is peer reviewed and published, with some exceptions (Google, Lockheed Martin, etc.), although much of this research is also published. We're also probably at least a decade away from making scalable qubit implementations suitable for complex computations. As of 2012, the most complex calculation ever done on a quantum computer was factoring 15=5x3 (with 50% accuracy).

/r/askscience Thread