Exploring the Significance of Quantum Computing
Delve into the fundamental disparities between classical and quantum computing, examining the probabilistic nature of computations, illustrated with examples like the Miller-Rabin primality test. Discover how quantum computing revolutionizes memory configurations and probability vectors, offering a glimpse into the evolution of computational techniques over time.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Quantum Computing: A Ridiculously Brief Motivation Frederic Green CS201 Clark University Spring 2023
Here is a summary of the main differences between classical and quantum computing We start with classical probabilistic computation. Example: Miller-Rabin primality test. Very roughly (!) stated: To determine if n is prime: Randomly generate a bunch of numbers m < n. Check that mk = 1 (mod n), or -1, for certain (carefully chosen!) k. If so, return TRUE, else FALSE. As we generate more and more bits of m, the number of possible configurations of memory increases exponentially. But the right answer is obtained with very high probability. 2
A picture of this process: time possible configuration of memory (only one when we start out) 3
t=0 4
t=1 5
t=2 6
t=3 7
2|n| |n| 8
Desired configurations 2|n| m |n| 9
Interpretation: At any step of the computation, memory can be in any one of a large number of configurations. Each configuration occurs with a certain probability; represent this set of probabilities as a vector (2n components for n bits). The vector of probabilities evolves over time according to a certain set of rules determined by the algorithm. 10
Vector of probabilities t=0 11
Vector of probabilities t=1 12
Vector of probabilities t=2 13
Vector of probabilities t=3 14
Vector of probabilities t=4 15
The tree representation is a little misleading: many configurations t=3 16
The tree representation is a little misleading: can lead to one t=4 17
...but this clarifies whats happening: i j = prob that j leads to i Let Then i.e., matrix multiplication! .....to sum up: 18
Evolution of probabilities (classical formulation): Let v(t) = vector of probabilities at time t. vi(t) = probability that we are in configuration i at time t. We have seen that v(t) evolves linearly. I.e., there is a matrix M such that, v(t+1) = Mv(t) Mi j is simply the probability that configuration j yields configuration i. So (of course!) Mi jis a real number in [0,1]. M must leave ivi(t)invariant (prob s sum to 1). 19
Evolution of probabilities (quantum formulation): Let v(t) = vector of probability amplitudes at time t. vi(t) is a complex number whose square norm |vi(t)|2= probability that we are in configuration i at time t. As in the classical case, v(t) evolves linearly. I.e., there is a matrix U such that, v(t+1) = Uv(t) Ui jis acomplex numberwhose norm squared is the probability that configuration j yields configuration i. So (of course!) Ui jis not necessarily a real number in [0,1]. U must leave i|vi(t)|2invariant (prob s sum to 1). Hence U is unitary: UU = 1. 20
Once again: 21
Evolution of probabilities (classical formulation): Let v(t) = vector of probabilities at time t. vi(t) = probability that we are in configuration i at time t. We have seen that v(t) evolves linearly. I.e., there is a matrix M such that, v(t+1) = Mv(t) Mi j is simply the probability that configuration j yields configuration i. So (of course!) Mi jis a real number in [0,1]. M must leave ivi(t)invariant (prob s sum to 1). 22
Evolution of probabilities (quantum formulation): Let v(t) = vector of probability amplitudes at time t. vi(t) is a complex number whose square norm |vi(t)|2= probability that we are in configuration i at time t. As in the classical case, v(t) evolves linearly. I.e., there is a matrix U such that, v(t+1) = Uv(t) Ui jis acomplex numberwhose norm squared is the probability that configuration j yields configuration i. So (of course!) Ui jis not necessarily a real number in [0,1]. U must leave i|vi(t)|2invariant (prob s sum to 1). Hence U is unitary: UU = 1. 23
Measurement After the computation has evolved, we may measure the configuration. The matrix U, applied to the initial configuration, determines the probability that we end up in any given configuration. Once the bits of the configuration have been measured, they will retain their measured value until acted on again ( collapse of the wavefunction ). 24
WHY? Don t ask! 25
Consequences Configurations can actually cancel! Because of unitarity, quantum computation is reversible! 26
t=0 27
t=1 28
Cancel t=2 29
Cancel t=3 30
t=4 31
Left with exactly what we want! (we hope!) t=4 32
