In this iterated function system, a Möbius transformation is applied in succession to the white circle yielding the blue and yellow circles. The characteristic constant of the transformation remains fixed, but the radius of the white circle is decreased in each frame of the animation.
More IFS here
GIF source: Java app
There is a useful quantum algorithm for quantum computers discovered by Lov Grover which pertains to the problem of searching large unstructured databases. Think of this problem as having to search through a large list or table of entries (like names and phone numbers) trying to find one particular entry. Like the factoring problem, the best a classical computer can do in searching a large unstructured database for a particular item is to proceed by brute force and exhaust all the possibilities. Grover’s search algorithm, though it does not provide an exponential speedup as in the case of factoring large integers, offers a quadratic speedup in searching such databases. However, this still has practical benefits.
Consider a database consisting of N entries that needs to be searched through. It can be shown that the best known classical algorithms, on average, can find a given entry in N/2 computational steps. On the other hand, Grover’s algorithm allows this to be accomplished in √N steps on a quantum computer.
As an illustration, imagine some future quantum computer that is performing Grover’s search algorithm with a processing speed capable of performing 108 computational steps per second—a realistic processing speed for classical computers. Suppose it is engaged in a particularly arduous search through a space of N = 1030 entries looking for a single unique entry. How long will it take? Well, it would require √N = 1015 computational steps, which at a rate of 108 steps per second, would take 107 seconds, or about 4 months. Though this may seem like a long time, let us calculate how long it would take a classical computer to search through the same database with the same processing speed of 108 computational steps per second. It would take N/2 = 5×1029 steps and thus require 5 × 1021 seconds, or very nearly the age of the universe (13.7 billion years)! That is the size of the practical benefit of the quantum search algorithm over the classical. In general, the larger the search is, the larger the gain the quantum computer has over the classical.
The theoretical implications of these algorithms are even more mind-boggling, because of the way quantum computers work. In the example of Grover’s search algorithm, the quantum computer is not just doing 1015 computational steps in parallel, which can be mimicked classically by making all the computers on Earth work on nothing but this problem. The quantum computer is doing 1030 possible computations in parallel every time a computational step is invoked. If all the silicon in the whole of our planet were made into microchips, and they were all set performing different computations, there would still be fewer distinct computations going on in that giant parallel computer than there would be in a single quantum computer performing Grover’s algorithm. That is a measure of the complexity, structure, and the process that exists in ordinary matter just beyond our perception since quantum processes are, of course, going on all the time everywhere. In a quantum computer, some small part of nature’s complexity is put to good use!
What is the Hamiltonian of the whole multiverse? Traditionally, fundamental physics has been about what types of systems exist in nature, what their observables are, and what their Hamiltonians are. That’s what elementary particle physicists call the theory of everything, but there is another way of looking at what is elementary or fundamental. Instead of asking what types of Hamiltonian are found in natural systems, which means what sorts of changes can occur in elementary systems over an infinitesimal time, one could go all the way to the bottom line and ask which transformation can be realized in nature by some quantum system evolving for some time and which cannot. The short answer is all changes, in which observables of the system undergo unitary evolution with every observable undergoing the same transformations so as to preserve their algebra, can occur in nature and nothing else can. Every unitary matrix is the evolution matrix for some quantum system evolving over some time. Or at least we think it is, because it turns out that the vast majority of these possible evolutions can only be realized in a very special type of physical system: a universal quantum computer. They don’t occur naturally because they require a complex computer program to bring them about. So, here is a fascinating situation. In terms of Hamiltonians the laws of physics are very finely tuned. The multiverse has its Hamiltonian and subsystems of the multiverse only have very special Hamiltonians. Most Hermitian matrices cannot be realized in nature as Hamiltonians. But when we ask a slightly different question: which unitary evolution operators can be realized in nature? The answer is all of them if a universal quantum computer can exist. This special type of object, the universal quantum computer, in a sense contains within itself all the diversity of nature. No other system does, except perhaps systems that are capable of constructing a universal quantum computer. Suddenly we find ourselves unavoidably playing a role at the deepest level of the structure of physical reality.
The set of all possible motions of a universal quantum computer includes accurate images of all possible motions of all physical objects. That the laws of physics permit this ‘universal object’ is clearly a profound feature of them, but still an elusive and controversial one.
This is a link to a video where David Deutsch talks about the universality of quantum computation, which is the property that a certain quantum computer can simulate any other quantum computer.
David Deutsch is considered to be the father of quantum computation because in 1985 he published a paper which laid down the theoretical foundations for the field. Here is the abstract:
It is argued that underlying the Church-Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means’. Classical physics and the universal Turing machine, because the former is continuous and the latter discrete, do not obey the principle, at least in the strong form above. A class of model computing machines that is the quantum generalization of the class of Turing machines is described, and it is shown that quantum theory and the ‘universal quantum computer’ are compatible with the principle. Computing machines resembling the universal quantum computer could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine. These do not include the computation of non-recursive functions, but they do include ‘quantum parallelism’, a method by which certain probabilistic tasks can be performed faster by a universal quantum computer than by any classical restriction of it. The intuitive explanation of these properties places an intolerable strain on all interpretations of quantum theory other than Everett’s. Some of the numerous connections between the quantum theory of computation and the rest of physics are explored. Quantum complexity theory allows a physically more reasonable definition of the ‘complexity’ or ‘knowledge’ in a physical system than does classical complexity theory.
This paper concludes with the following remark:
To view the Church-Turing hypothesis as a physical principle does not merely make computer science a branch of physics. It also makes part of experimental physics into a branch of computer science.
The existence of a universal quantum computer implies that there exists a program for each physical process. In particular, quantum computers can perform any physical experiment. In some cases this is not useful because the result must be known to write the program. But, for example, when testing quantum theory itself, every experiment is genuinely just the running of a quantum computer program.
Quantum computers raise interesting problems for the design of programming languages, which I shall not go into here. From what I have said, programs exist that would (in order of increasing difficulty) test the Bell inequality, test the linearity of quantum dynamics, and test the Everett interpretation. I leave it to the reader to write them.
This video zooms in on the oldest galaxies of our universe some 13+ billion light years away.
The quantum computing model is inherently probabilistic. When an algorithm is successfully run on a quantum computer, the output corresponding to the answer to some problem may not always be correct. Instead, we demand that the algorithm gives the correct solution with a probability greater than 1/2. If this is the case, then simply repeating the algorithm multiple times will eventually yield an answer that will be correct with high probability. This is a just a consequence of the Chernoff bound in probability theory. Chris Lomont gives an example of this in The Hidden Subgroup Problem: Review and Open Problems:
Thus the majority is wrong very rarely. For example, we will make most algorithms succeed with probability 3/4 … Although it sounds like a lot, taking 400 repetitions of the algorithm causes our error to drop below 10-20, at which point it is more likely our computer fails than the algorithm fails. And since the algorithms we are considering are usually exponentially faster than classical ones, there is still a net gain in performance. If we do 1000 runs, our error drops below 10-55, at which point it is probably more likely you’ll get hit by lightning while reading this sentence than the algorithm itself will fail.
Simulating quantum systems using classical computers is hard to do because of the size and complexities of quantum systems. To describe a single particle in a classical system, you would need 6 different parameters: one for each of the 3 directions of motion and another 3 for the velocities of the particle in each of these directions. So for a system consisting on N particles, one would need 6N different parameters to completely specify the state space of the system.
On the other hand, due to the superposition principle and the linearity of quantum mechanics, to describe the simplest quantum system consisting of N quantum particles (or qubits), 2N parameters are needed to describe the state space completely. The thing is, for large enough values of N (greater than 4), 2N > 6N. Moreover, 2N grows exponentially faster than 6N as N increases. In essence, this is one of the main reasons why quantum computers would be able to outperform their classical counterparts.
Here is an example illustrating how large and how quickly exponential behavior like this can grow.
Suppose you have a chess board and a lot of coins. There are 64 spaces in total on the board. Start in one corner and place 2 coins on that square. Move to the next square and stack 22=4 coins on it. Then stack 23=8 coins on the third square and continue in this manner stacking 2N coins on the Nth square. The last square will have 264 = 18,446,744,073,709,551,616 coins stacked on top of each other.
How high do you think this stack would be?
It would stretch further than the distance from Earth to the Moon (400,000 kilometers), further than than the distance from the Earth to the Sun (150 million kilometers), and would be able to reach the next closest star Proxima Centauri (about 4.2 light-years or 3.97×1013 kilometers)!
There are many problems out there that require computers to use resources that grow exponentially like in this example. It has been difficult to say whether or not classical computers could even compute fast enough to make them practical problem solvers in this case, but we do have reasons to believe that quantum computers may be able to help out in this regard.
An ideal rotation around the point at infinity in the disc and upper half plane model of the hyperbolic plane
