a perspective on mathematics, the pattern, and the abstract

Posts tagged: physics

Grover’s quantum search algorithm

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.

The nature of this algorithmic speed up is illustrated in a quite profound way by David Deutsch in "Grover’s Search Algorithm":

Imagine some future quantum computer that is performing Grover’s search algorithm with a processing speed capable of performing 10

^{8}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 = 10^{30}entries looking for a single unique entry. How long will it take? Well, it would require √N = 10^{15}computational steps, which at a rate of 10^{8}steps per second, would take 10^{7}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 10^{8}computational steps per second. It would take N/2 = 5×10^{29}steps and thus require 5 × 10^{21}seconds, or very nearlythe 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 10^{15}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 10^{30}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!

Quantum computers and the Hamiltonian of the multiverse

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.

Super-kamiokande Cherenkov detector, near the village of Higashi-Mozumi, Gifu, Japan.

(via sneakystratuses)

Source:
grumble-grumble

High-res
Notes: 55
8/23/11 — 2:01pm
Filed under:
#Science
#physics
#particle detector
The universality of quantum computation, and its implications

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.

Quantum theory, the Church-Turing principle, and the universal 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.

Quantum computers and 2^N

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), 2^{N} parameters are needed to describe the state space completely. The thing is, for large enough values of N (greater than 4), 2^{N} > 6N. Moreover, 2^{N} 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 2^{2}=4 coins on it. Then stack 2^{3}=8 coins on the third square and continue in this manner stacking 2^{N} coins on the Nth square. The last square will have 2^{64} = 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×10^{13} 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.

Black Hole hums a B♭

There exists a supermassive black hole located in the Perseus galaxy cluster 250 million light years from Earth that is emitting sound waves with a frequency of about 3x10^(-14) Hz. This corresponds to one wave oscillation every 10 million years, with a wavelength of about 1 light year. Musically speaking, this note would be close to a B flat 57 octaves below middle C!

Despite being located so far from us, the sound waves coming from the black hole manage to travel *hundreds of thousands* of light years from their source. Moreover, the lower limit of human hearing is around 20 Hz making the black hole’s sound some *million billion* times lower than what we can hear.

These sound waves could solve the mystery of why trillions of stars are not forming in this gaseous region, since the energies involved in these sound waves may be responsible for keeping the regions around the black hole hot enough to prevent star formation. If so, this black hole’s cosmic drone would remain constant for about 2.5 billion years!

The animation below zooms into the cluster revealing the black hole (central white spot) with its bipolar jets that are creating the two cavities, which are each 50 thousand light years wide. The sound waves then propagate into space from the edges of these cavities.

Source:
chandra.harvard.edu

Notes: 123
8/7/11 — 1:06pm
Filed under:
#science
#astrophysics
#space
#GIF
#animation
#physics
#order of magnitude
Logicians on safari

Some cute examples of computability theory applied to specific problems.

- We now know that, if an alien with enormous computational powers came to Earth, it could prove to us whether White or Black has the winning strategy in chess. To be convinced of the proof, we would
nothave to trust the alien or its exotic technology, and we wouldnothave to spend billions of years analyzing one move sequence after another. We’d simply have to engage in a short conversation with the alien about the sums of certain polynomials over finite fields.- There’s a finite (and not unimaginably-large) set of boxes, such that if we knew how to pack those boxes into the trunk of your car, then we’d also know a proof of the Riemann Hypothesis. Indeed,
everyformal proof of the Riemann Hypothesis with at most (say) a million symbols corresponds to some way of packing the boxes into your trunk, and vice versa. Furthermore, a list of the boxes and their dimensions can be feasibly written down.- Supposing you do prove the Riemann Hypothesis, it’s possible to convince someone of that fact,
without revealing anything other than the fact that you proved it. It’s also possible to write the proof down in such a way that someone else could verify it, with very high confidence, having only seen 10 or 20 bits of the proof.

This article by Scott Aaronson is an interesting read! Here’s another example:

It would be great to prove that RSA is unbreakable by classical computers. But every known technique for proving that would, if it worked, simultaneously give an algorithm forbreakingRSA! For example, if you proved that RSA with an n-bit key took n^{5}steps to break, you would’ve discovered an algorithm for breaking it in 2^{n^1/5}steps. If you proved that RSA took 2^{n^1/3}steps to break, you would’ve discovered an algorithm for breaking it in n^{(log n)^2}steps. As you show the problem to be harder, you simultaneously show it to be easier.

And an excerpt on the relevance of these examples:

So what are they then? Maybe it’s helpful to think of them as “quantitative epistemology”: discoveries about the capacities of finite beings like ourselves to learn mathematical truths. On this view, the theoretical computer scientist is basically a mathematical logician on a safari to the physical world: someone who tries to understand the universe by asking what sorts of mathematical questions can and can’t be answered within it. Not whether the universe is a computer, but what kind of computer it is! Naturally, this approach to understanding the world tends to appeal most to people for whom math (and especially discrete math) is reasonably clear, whereas physics is extremely mysterious.

In my opinion, one of the biggest challenges for our time is to integrate the enormous body of knowledge in theoretical computer science (or quantitative epistemology, or whatever you want to call it) with the rest of what we know about the universe. In the past, the logical safari mostly stayed comfortably within 19th-century physics; now it’s time to venture out into the early 20th century. Indeed, that’s exactly why I chose to work on quantum computing: not because I want to build quantum computers (though I wouldn’t mind that), but because I want to know what a universe that allows quantum computers is like.

Originally, in the Newtonian formulation of classical mechanics, equations of motion were determined by summing up vector forces (à la free body diagrams). Is there a different way to find the equations of motion?

In place of drawing a free body diagram, we can represent a system more rigorously by describing its configuration space. The

configuration space(often denoted Q) of a system is a mathematical space (a differential manifold) where every point in the space represents a particular state or configuration of the system. A curve drawn through a configuration space, then, represents the evolution of a system through a sequence of configurations.Consider a rod along which a pendulum can slide. We need two numbers to describe the state of this system: the angle of the swinging pendulum and the position of the pendulum’s base along the rod. These two numbers are

generalized coordinatesfor our system. Just like a traditional, linear vector space has a coordinate basis (likex, y,andz), our configuration space can use our generalized coordinates as a basis; let’s choose to name the position on the rodxand the angle of the pendulumφ. Sincexcan take any real value andφcan take any value from 0 to 2π (or 0 to 360^{o}, if you like), thexdimension can be represented by a line (R^{1}) and theφdimension by a circle (or a one-sphere, S^{1}). When we combine these dimensions, our new space — the configuration space of this system — is shaped like an infinite cylinder, R^{1}x S^{1}. Just imagine connecting a circle to every point on a line… or, conversely, a line to every point on a circle.The general process of examining a system and the constraints on its movement is a standard first step for solving mechanics problems analytically. After accounting for the constraints on a system, the ways a system can vary are called the

degrees of freedom. Their count is often represented by the variables. Notice:s= dim(Q).Now that we’ve represented the configuration of our system, we need to talk about the forces present. There are several different ways that we can set up scalar fields on our configuration manifold that represent quantities related to the energy of the system. The simplest to deal with is often the

Lagrangian, L = T - V = (Total kinetic energy) - (Total potential energy). Some fancy mathematics (a.k.a. calculus of variations) shows that when we define the Lagrangian in terms of our coordinates and their time derivatives, we can easily derive the equations of motion using theEuler-Lagrange equation.For more complicated systems, configurations spaces may look different. A double pendulum (a pendulum on a pendulum) would have the topology S

^{1}x S^{1}= T^{2}, the torus (as pictured). Many systems will have higher dimensions that prevent them from being easily visualized.

Exercise left to the reader: the Lagrangian explicitly takes the time derivatives of the coordinates as arguments; information about the velocities of the system is needed to derive the equations of motion. But this information isn’t included in Q, so Lagrangian dynamics actually happens on TQ, the tangent bundle to Q. This new manifold includes information about how the system changes from every given configuration; since it needs to include a velocity coordinate for each configuration coordinate, dim(TQ) = 2s. TQ is also called Γ_{v}, the velocity phase space. T*Q, the cotangent bundle to Q, is the dual of TQ, and is traditionally just called the phase space, Γ; this is where Hamiltonian mechanics takes place.

Source:
sayitwithscience

High-res
Notes: 74
7/25/11 — 4:55pm
Filed under:
#math
#science
#physics
#space
Calabi-Yau manifold

A spinning 3D model of the 6-dimensional Calabi-Yau manifold. This manifold has been shown by string theory to be the topological shape of extra, curled-up dimensions on the Planck-scale at every point in the universe. It is the extra dimensions of this shape that allow the strings to “wiggle” in the necessary ways to represent all the fundamental particles predicted by the Standard Model. The holes in the manifold are thought to correspond to the number of fundamental particles, which would suggest a deeper meaning to string theory [i.e. not just a mathematical construct].

A droplet of glycerol coalescing in silicone oil while subjected to strong electric fields exhibits a whip-like instability reminiscent of fireworks. Check out videos of the phenomenon or see the paper for more information. Happy Independence Day to our American readers!

For more fun, holiday-themed high-speed video, check out PopSci’s fireworks videos.

Among the many ramifications of quantum computation for apparently distant fields of study are its implications for the notion of mathematical proof. Performing any computation that provides a definite output is tantamount to proving that the observed output is one of the possible results of the given computation. Since we can describe the computer’s operations mathematically, we can always translate such a computation into the proof of some mathematical theorem. This was the case classically too, but in the absence of interference effects it is always possible to keep a record of the steps of the computation, and thereby produce (and check the correctness of) a proof that satisfies the classical definition - as “a sequence of propositions each of which is either an axiom or follows from earlier propositions in the sequence by the given rules of inference”. Now we are forced to leave that definition behind. Henceforward, a proof must be regarded as a process — the computation itself — for we must accept that in future, quantum computers will prove theorems by methods that neither a human brain nor any other arbiter will ever be able to check step-by-step, since if the ‘sequence of propositions’ corresponding to such a proof were printed out, the paper would fill the observable universe many times over.

- Deutsch, Ekert, and Lupacchini

"Machines, Logic and Quantum Physics"

Source:
xxx.lanl.gov

Notes: 6
6/24/11 — 4:04pm
Filed under:
#David Deutsch
#logic
#math
#order of magnitude
#physics
#quantum computation
#wisdom
#papers