I think the battle to promote the use of quantum computers is rendered even more difficult by the fact that their raison d'être of "being faster than classical

I think the battle to promote the use of quantum computers is rendered even more difficult by the fact that their raison d'être of "being faster than classical computers" requires one to further develop the existing field of complexity analysis for classical computers. Indeed, it's difficult to fairly compare the gate/oracle-based complexity of quantum computers to the iterations/multiplications/etc-based complexity of classical computers, especially if we don't know their complexity in the first place [1]! [1] - Recently, there has been interest in the complexity analysis of deep learning NNs: https://arxiv.org/abs/1811.03962 https://arxiv.org/abs/1811.03962 Further Reading: * Church-Turing Thesis for quantum computers - https://quantumcomputing.stackexchange.com/questions/6088/what-precisely-is-the-quantum-extended-church-turing-thesis https://quantumcomputing.stackexchange.com/questions/6088/wh... * Quantum Turing Machine - https://en.wikipedia.org/wiki/Quantum_Turing_machine https://en.wikipedia.org/wiki/Quantum_Turing_machine