I don't quite think my lawnmower is boolean complete.

And while quantum computing may be expressible algorithmically (dunno, your claim, not mine), that doesn't mean all of quantum physics is.

A quantum computer is definitely not a plain old Turing machine. The only memory in a Turing machine is the tape; the tape head itself is just a list of deterministic instructions, and that tape head itself is stateless.

A plain old Turing machine can't even handle randomness. To extend it to randomness, you need a probabilistic Turing machine, where the instructions take the form of stochastic matrices. A stochastic matrix is just a statistical truth table.

But a quantum computer cannot even be a probabilistic Turing machine, because of the way operators compose.

In both a plain old Turing machine and a probabilistic Turing machine, operators that occur at different moments of time are independent of one another. The NOT operator flips a bit. If I apply the NOT operator once, and then later apply it again, the outcome is the same: it flips the bit. Probabilistic computers can have stochastic operators, like let's call one COIN which outputs a 50%/50% distribution for the bit for both inputs 0 and 1, and so whatever comes in, randomness comes out. If we apply the COIN operator, and later apply it again: the effect is the same.

Quantum computers don't work like that, because operators compose differently. The quantum mechanical equivalent of the COIN operator is called the Hadamard, sometimes represented just with the letter H. If we apply H one time, it has the effect of flipping the bit at complete random, just like COIN. However, if we apply H twice in a row, the second time has the effect of deterministically moving the bit back to whatever value it had before the first H.

That is only possible if the operators, that occur at different moments in time, are not independent of one another. The second H behaves differently from the first because it comes after the first. Where it is situated in the circuit, in relation to everything before it, plays a role in determining its behavior.

There are only two explanations for this, and both violate the principles of both a plain old Turing machine and a probabilistic Turing machine.

1. The simplest explanation, although the most controversial (because people prefer more extraordinary explanations), is just that the operators do indeed just change their behavior based upon what comes before them in the circuit. That means that the only thing that fundamentally sets quantum information apart from classical information is a kind of past-dependence in the behavior of the operators. That's not something either kind of Turing machine mentioned thus far does. Operators have no awareness of the history of previous operators.

2. The more extraordinary explanation is to assume that there is no past-dependence, because there is a memory. If you remember the past, then the memory is in the present, and so the dependence becomes a present-dependence. However, this memory must be exponentially large for it to work: 2^n complex numbers for n qubits. If you have 300 qubits, that is 2^300 complex numbers, which is a memory greater than the number of atoms in the observable universe. The memory also cannot exist anywhere because it is too large to meaningfully assign it coordinates in physical space. This is how most people conceive of quantum computers, where the memory is held in an abstract invisible ψ that exists nowhere, but this also is not a Turing machine because the tape head itself is memoryless.

The distinction between #1 and #2 is between a non-Markovian model and a hidden Markov model. The Markov assumption is the idea that the system's evolution only depends upon the present state of the system. Dropping that assumption makes it non-Markovian, so there is a past-dependence. You can get rid of this past dependence if you assume the system keeps a memory, but that memory is invisible, and thus these are called hidden Markov models. Most people interpret quantum systems in general in terms of a hidden Markov model with an utterly enormous invisible memory represented by ψ. (Indeed, if ψ represents something continuous, like the position of a particle in physical space, then the memory literally becomes infinitely large!)

Either way, a Turing machine is neither a hidden Markov model (the tape head itself holds no memory and is stateless; only the tape holds data) nor is it non-Markovian. A probabilistic Turing machine is explicitly Markovian.

Of course, you could define a new kind of Turing machine, and they exist: a quantum Turing machine. But that is definitely not a plain old Turing machine.

(That being said, I don't am not agreeing with the other person, as I don't even believe "consciousness" is a meaningful concept. I am merely saying that quantum computing is definitely not a plain old Turing machine.)