On Fri, Jul 14, 2023, 9:03 PM James Bowery <[email protected]> wrote:
> https://www.mdpi.com/1099-4300/25/5/763 > It's an interesting paper that helped me understand quantum computing a little better. Recall that the state of a quantum computer with n qubits is described by a unit vector in a 2^n dimensional space (a Hilbert space). The only allowed operations are rotations (unitary), which are time reversible. Copying, AND, and OR are not allowed, but swap, NOT, and controlled NOT are allowed as long as the number of inputs and outputs of each gate are the same. You can read the state only once. The result is one of the possible 2^n bit strings with probability equal to the square of the magnitude of the unit vector in that dimension, after which the state is destroyed. For example, the 4 dimensions of a 2 qubit system would be labeled |00>, |01>, |10>, |11>. A NOT operation flipping the first bit would actually be a 90 degree rotation in the |00>, |10> plane from (1,0,0,0) to (0,0,1,0). You can have partial rotations like a 45 degree Hadamard gate resulting in (.707,0,.707,0), which would read as a coin flip on the first qubit. What the authors did was define quantum algorithmic complexity of a bit string as the minimum number of quantum operations needed to compute the string. Unlike ordinary algorithmic complexity, this is computable because quantum circuits, a subset of Boolean circuits, always halt. My interpretation of what they found empirically is that a random bit string has an average complexity of about 6 2-input gates or 4 3-input gates drawn from a minimum universal set of gates. A gate set is universal if you can construct any function from it. For example, in Boolean logic, 2 input NAND is universal. In quantum computing, the 2 input set {NOT, CNOT} and 3 input set {CCX} (or Toffoli) gate are both universal. A CNOT gate flips one qubit if the other is 1. A CCX gate flips one qubit if the other two are both 1. Their result implies that quantum complexity is not useful for induction. The Kolmogorov complexity of a string of n identical bits is log n plus a language dependent constant. But the Boolean and quantum complexities are both O(n), one gate for each output bit. The quantum complexity of a random string increases from n to O(n log n) since it takes log n bits to specify each of the ~12n gate inputs. Occam's Razor depends on input being compressible to predict future inputs. Boolean logic, and by implication, quantum computing, cannot compress. The result is helpful by giving one more reason why quantum computing is not the path to AGI. Quantum computing is often misunderstood as computing an exponential set of paths in parallel, when for most purposes it is actually weaker than classical computing. Leveraging the power of quantum computing depends on arranging the computation so that the components of the unit vector reinforce for a subset of the qubits, like in computing the quantum Fourier transform for Shor's or Grover's algorithms for cracking crypto. But it doesn't solve NP complete problems in polynomial time or anything like that. The brain is not a quantum computer. Neural networks, and learning in general, are not time reversible. ------------------------------------------ Artificial General Intelligence List: AGI Permalink: https://agi.topicbox.com/groups/agi/Tb2574dcac5560d73-M638314d8d4ae2d29c924c5dc Delivery options: https://agi.topicbox.com/groups/agi/subscription
