3 ms·

To do this you need uncountable turing machines, and that set isnt a computable function. Hilbert space is infinite-dimensional and real-valued. QM says that

To do this you need uncountable turing machines, and that set isnt a computable function. Hilbert space is infinite-dimensional and real-valued. QM says that there is no `rand(seed)`, rather there is only `rand()` that is what "no hidden variables" means. If you want to do `rand(s) forall s`, that "forall" requires real numbers -- and then you're out-of-luck on computability.

tsimionescu 5y ago
I would first note that you can keep arguing with me all you want, but it is well known and commonly practiced that a Turing machine such as a digital computer can simulate a Quantum Computer or Quantum System to arbitrary precision, given sufficiently large but finite time. There are even cloud services offering such simulation capabilities, such as Amazon Braket [0]. The simulations take exponential time to run a linear time quantum algorithm, but they will produce the same result as a QC would (after enough sampling of the QC results). > Hilbert space is infinite-dimensional and real-valued. Infinite-dimensional Hilbert state spaces are a useful mathematical model, but they are not physical. Physical systems have finite elements and thus finite state spaces. We could argue that space itself is infinitely divisible, so that we need infinite-dimensional state spaces to represent the infinite possible positions of a particle, but this is not a physical concern, as it is impossible to differentiate in finite time two states that only differ in an infinitesimal position change - so, we are free to choose some minimal unit of length (say, one over Graham's number of the Planck length) and get a finite-dimensional state space. Crucially, for any amount of time and for any sensitivity of instruments, we can always choose some such unit and ensure that our results will not be distinguishable with those measurement instruments within that amount of time. > QM says that there is no `rand(seed)`, rather there is only `rand()` that is what "no hidden variables" means. QM says no such thing, though many interpretations do. Still, that is exactly why I chose rand(), not rand(seed) in my example, so I'm not sure why you're bringing this up. rand(seed) is a deterministic computation, rand() is a non-deterministic computation. > If you want to do `rand(s) forall s`, that "forall" requires real numbers -- and then you're out-of-luck on computability. This is not what I was proposing. I was proposing a Turing machine + perfectly random rand() as the simulation of a random world. Even this is not necessary if you believe in the MWI, where the whole universe actually evolves perfectly linearly and deterministically from a fixed initial state, with no randomness of any kind. This interpretation is perfectly compatible with all observations of QM, if we also add the postulate that observers can only observe one state at a time (the one they are entangled with). Even without going there, the construction I proposed earlier, where we essentially select enough real numbers to satisfy any possible measurement device leads to such that our computable set is indistinguishable in practice from the infinite uncomputable set we started with still applies. In general, there is no (known) way to introduce infinity into empirical science - it is a priori impossible to distinguish, in finite time, between an arbitrarily large but finite quantity, and a truly infinite quantity. [0] https://aws.amazon.com/braket/ https://aws.amazon.com/braket/
- mjburgess 5y ago
  A quantum computer is just a computer. Yes, a turing machine can simulate a QC. A QC doesnt use any special quantum properties in its computation. The "quantum" part should really be read more about its storage system than its computation, ie., its mostly about how its input states are prepared. That's neither here nor there though. A myriad of other issues exist. The uncertainty principle precludes "in any world", infinitely precise measurement. Thus chaotic systems, at least of a large time horizon, arent deterministic. A chaotic system is one in which "insignificant digits" in the input determine "significant digits" in the output. You need very very very low digit precession in inputs the longer the time horizon. This gets beyond the uncertainty principal. You can run as many turing machines as you like (necessarily, uncountably many to be consistent with QM). But you cannot escape the problem. The best theories of physics are extremely far away from "effective computation". They are phrased actively hostile to it. And you have to completely revise physics to make it even half-plausible. It's a project which is barely stated, and a long way from finished. It seems, indeed, a little doomed to failure. Properties that physics uses day-in-day-out posses the trivial infinities of geometry; and the trivial randomness of uncountable ensembles etc. -- to claim that physics states that reality is a computer is bizarre.
  - tsimionescu 5y ago
    A QC absolutely uses quantum properties in its probabilistic computation (the complex-valued probabilities of its qbits and their entanglement). A QC can also perfectly represent the state of a quantum system (until you want to measure its output, of course). The laws of physics are known to be computable. Quantum Mechanics is one of the easiest to prove this for, since it is based on simple linear transforms! (Thermodynamics and GR are more complex, but still computable). I have no idea why you believe differently. A chaotic system requires arbitrary precision in the input measurements to be able to predict arbitrarily precisely its state after arbitrarily many steps. But, crucially, it does not require infinite precision in the input unless you want to predict its state with infinite precision (non-goal) or after infinite time (also a non-goal). The uncertainty principle is also irrelevant. The uncertainty principle has to do with measurement of classical properties. Conversely, the wave function of a system is precise, not fuzzy. It's only in measuring properties of the wave function that we reach uncertainty or probability at all. So, a computer can precisely compute the simple linear evolution of the wave function, according to the Schrodinger equation, which is what the universe itself is doing. The result of this computation is a complex value. You can then apply the Born rule to this result to get the probability of your system being in a particular state after following the simulated evolution, just as you would for a real quantum mechanical system. We do this kind of quantum simulation every day with great success, with a countable number of classical computers (typically 1), though it is only tractable for very very simple systems. The results don't typically differ in any perceivable way from the actual experiment.

tsimionescu 5y ago

I would first note that you can keep arguing with me all you want, but it is well known and commonly practiced that a Turing machine such as a digital computer can simulate a Quantum Computer or Quantum System to arbitrary precision, given sufficiently large but finite time. There are even cloud services offering such simulation capabilities, such as Amazon Braket [0]. The simulations take exponential time to run a linear time quantum algorithm, but they will produce the same result as a QC would (after enough sampling of the QC results). > Hilbert space is infinite-dimensional and real-valued. Infinite-dimensional Hilbert state spaces are a useful mathematical model, but they are not physical. Physical systems have finite elements and thus finite state spaces. We could argue that space itself is infinitely divisible, so that we need infinite-dimensional state spaces to represent the infinite possible positions of a particle, but this is not a physical concern, as it is impossible to differentiate in finite time two states that only differ in an infinitesimal position change - so, we are free to choose some minimal unit of length (say, one over Graham's number of the Planck length) and get a finite-dimensional state space. Crucially, for any amount of time and for any sensitivity of instruments, we can always choose some such unit and ensure that our results will not be distinguishable with those measurement instruments within that amount of time. > QM says that there is no `rand(seed)`, rather there is only `rand()` that is what "no hidden variables" means. QM says no such thing, though many interpretations do. Still, that is exactly why I chose rand(), not rand(seed) in my example, so I'm not sure why you're bringing this up. rand(seed) is a deterministic computation, rand() is a non-deterministic computation. > If you want to do `rand(s) forall s`, that "forall" requires real numbers -- and then you're out-of-luck on computability. This is not what I was proposing. I was proposing a Turing machine + perfectly random rand() as the simulation of a random world. Even this is not necessary if you believe in the MWI, where the whole universe actually evolves perfectly linearly and deterministically from a fixed initial state, with no randomness of any kind. This interpretation is perfectly compatible with all observations of QM, if we also add the postulate that observers can only observe one state at a time (the one they are entangled with). Even without going there, the construction I proposed earlier, where we essentially select enough real numbers to satisfy any possible measurement device leads to such that our computable set is indistinguishable in practice from the infinite uncomputable set we started with still applies. In general, there is no (known) way to introduce infinity into empirical science - it is a priori impossible to distinguish, in finite time, between an arbitrarily large but finite quantity, and a truly infinite quantity. [0] https://aws.amazon.com/braket/ https://aws.amazon.com/braket/

mjburgess 5y ago
A quantum computer is just a computer. Yes, a turing machine can simulate a QC. A QC doesnt use any special quantum properties in its computation. The "quantum" part should really be read more about its storage system than its computation, ie., its mostly about how its input states are prepared. That's neither here nor there though. A myriad of other issues exist. The uncertainty principle precludes "in any world", infinitely precise measurement. Thus chaotic systems, at least of a large time horizon, arent deterministic. A chaotic system is one in which "insignificant digits" in the input determine "significant digits" in the output. You need very very very low digit precession in inputs the longer the time horizon. This gets beyond the uncertainty principal. You can run as many turing machines as you like (necessarily, uncountably many to be consistent with QM). But you cannot escape the problem. The best theories of physics are extremely far away from "effective computation". They are phrased actively hostile to it. And you have to completely revise physics to make it even half-plausible. It's a project which is barely stated, and a long way from finished. It seems, indeed, a little doomed to failure. Properties that physics uses day-in-day-out posses the trivial infinities of geometry; and the trivial randomness of uncountable ensembles etc. -- to claim that physics states that reality is a computer is bizarre.
- tsimionescu 5y ago
  A QC absolutely uses quantum properties in its probabilistic computation (the complex-valued probabilities of its qbits and their entanglement). A QC can also perfectly represent the state of a quantum system (until you want to measure its output, of course). The laws of physics are known to be computable. Quantum Mechanics is one of the easiest to prove this for, since it is based on simple linear transforms! (Thermodynamics and GR are more complex, but still computable). I have no idea why you believe differently. A chaotic system requires arbitrary precision in the input measurements to be able to predict arbitrarily precisely its state after arbitrarily many steps. But, crucially, it does not require infinite precision in the input unless you want to predict its state with infinite precision (non-goal) or after infinite time (also a non-goal). The uncertainty principle is also irrelevant. The uncertainty principle has to do with measurement of classical properties. Conversely, the wave function of a system is precise, not fuzzy. It's only in measuring properties of the wave function that we reach uncertainty or probability at all. So, a computer can precisely compute the simple linear evolution of the wave function, according to the Schrodinger equation, which is what the universe itself is doing. The result of this computation is a complex value. You can then apply the Born rule to this result to get the probability of your system being in a particular state after following the simulated evolution, just as you would for a real quantum mechanical system. We do this kind of quantum simulation every day with great success, with a countable number of classical computers (typically 1), though it is only tractable for very very simple systems. The results don't typically differ in any perceivable way from the actual experiment.