# Do Hidden-Variable models have a large (computational) complexity?

Taking hidden variables to mean an underlying dynamics characterised by some hidden variable $\lambda$, which characterises a definite state of a system at any given time, whilst reproducing the statistical predictions of a quantum mechanics. Since such a model is, by construction, classical does that necessarily mean problems that are soluble by a quantum computer in polynomial time would, in practice, have a large complexity should Hidden-Variables be true as it cannot take advantage of superposition and interference? For example should a large scale quantum computer be developed, tasked, using Shor's algorithm, with factorising large primes actually find the problem as difficult as a classical computer?

• If QM is correct, then if there are hidden variables, the hidden variable theory has to be non-local. All the weirdness of QM will still be there, regardless of the hidden variables, because QM will remain unmodified. Now, if QM is inaccurate, then the story will be different. – user126422 May 9 '17 at 12:37
• I agree that a valid hidden variable theory would have to reproduce the observed quantum weirdness. But, take for example n entangled Qubits this corresponds to a state characterised by 2^n complex numbers, surely an algorithm designed to take advantage of interference due to superposition, would in practice have on the order 2^n more calculations to do if in actuality hidden variables were specifying a single state for the Qbits? – HiddenVariable May 9 '17 at 15:51