On Sat, Jul 22, 2023, 8:51 AM John Rose <[email protected]> wrote:
You don’t think the many-paths simultaneity can be leveraged to find short > algorithmic paths and/or circuits better than classical? > Yes, provided the computation is time reversible and you only read the qubits once. That works great for cracking crypto or modeling chemistry, but not so well for AGI because machine learning is one way. Studying Shor's and Grover's algorithms helps in understanding the power and limitations of quantum computers. For example, Grover's algorithms gives you a quadratic (but not exponential) speed up in inverting hashes like SHA-256 for Bitcoin mining or password cracking. It breaks AES-128 2^64 times faster than brute force key search in a known plaintext attack. It works as follows: 1. Initialize 129 qubits to a superposition of all 2^129 possible states. Call this state |s>. (This happens automatically). Recall that the state of n qubits is a unit vector in 2^n dimensions (a Hilbert space). Each component is a complex number, but we can ignore that for now and only consider the values 1 and -1. 2. Construct a logic circuit out of reversible gates like NOT and CNOT (CNOT has 2 inputs and 2 outputs and flips one qubit if the other is 1) that inputs a 128 bit key and one other qubit which it flips if the plaintext encrypts to the cipher text. This is possible to build because it is reversible. Running it twice restores the original state. 3. Flip all the qubits, or equivalently apply the operator 2|s><s| - I, where I is the identity matrix (with 2^129 1s along the diagonal and 0s everywhere else), |s> is the ket (column vector) of the initial state, <s| is the bra (row vector), and |s><s| is the outer product, yielding a matrix where each component is a product of a component from each vector. 4. Repeat steps 2-3 2^64 pi/4 times. Each step reflects the state vector across the hyperplane representing the (unknown) |key> dimension and then the hyperplane representing all the other dimensions. Each step amounts to a rotation of 2^-64 radians. Running the algorithm longer therefore rotates the state vector past the optimal solution. 5. Read the qubits, which will be the key with at least 50% probability. If not, repeat the algorithm until the key is found. Note that the speedup is not exponential, so AES-256 is still safe. AES-128 is still safe as long as we don't have quantum computers with error rates below 2^-64. Right now we have 70 qubit machines with 5% error rates. Shor's algorithm uses a quantum Fourier transform to speed up the discrete logarithm problem, which is used in Diffie-Hellman key exchange and is the critical step in factoring primes for RSA. The ECC variant used to protect Bitcoin private keys might be easier to crack because of the shorter key size. Right now we have we have working 10 qubit quantum computers that can factor 48 bit numbers using a different algorithm called QAOA, a huge leap over Shor's algorithm. They estimate RSA-2048 can be broken with 372 qubits and a few thousand gate operations. https://arxiv.org/abs/2212.12372 But before proposing quantum computing as a solution to AGI, understand how they work and what they can do. ------------------------------------------ Artificial General Intelligence List: AGI Permalink: https://agi.topicbox.com/groups/agi/Tb2574dcac5560d73-Mfc2fc3d88da4e0c528707ed5 Delivery options: https://agi.topicbox.com/groups/agi/subscription
