2.5. quantumÂ¶
Some very limited notes on quantum computing
what does physics tell us about the limits of computers?
NP  can check soln in polynomial time
NPhard  if solved, solves every NP
NPcomplete  NP hard and in NP
churchturing thesis \(\implies\) turing machine polynomial time should be best possible in the universe
physics could allow us to do better than a turing machine
examples
glass plates with soapy water  forms minimum steiner tree
can get stuck in local optimum
ex. protein folding
ex. relativity computer
leave computer on earth, travel at speed of light for a while, come back and should be done
if you want exponential speedup, need to get exponentially close to speed of light (requires exponential energy)
ex. zenoâ€™s computer  run clock faster (exponentially more cooling = energy)
2.5.1. basicsÂ¶
An nbit computer has 2^n states and is in one of them with probability 1. You can think of it as having 2^n coefficients, one of which is 0 and the rest of which are 1. Operations on it are multiplying these coefficients by stochastic matrices. Only produces n bits of info.
an nqubit quantum computer is described by 2^n complex coefficients. The sum of their squares sums to 1. Itâ€™s 2^n complex coefficients must be multiplied by unitary matrices (they preserve that the sum of the squares add up to 1.)
Problem: Decoherence â€“ results from interaction with the outside world
Properties:
Superposition â€“ an object is in more than one state at once
Has a percentage of being in both states
Entanglement â€“ 2 particles behave exactly the opposite â€“ instantly
2.5.2. storing qubitsÂ¶
Fullerenes â€“ naturally found in Precambrian rock, reasonable for storing qubits â€“ can store
not developed, but some experiments have shown ability to store qubits for milliseconds
2.5.3. introÂ¶
probability with minus signs
amplitudes  used to calculate probabilites, but can be negative / complex
applications
quantum simulation
also could factor integers in polynomial time (shor 1994)
scaling up is hard because of decoherence= interaction between cubits and outside world
errorcorrecting codes can make it so we can still work with some decoherence
algorithms
paths that lead to wrong answer  quantum amplitudes cancel each other out
for right answer, quantum amplitudes in phase (all positive or all negative)
prime factorization is NP but not NP complete
unclear that quantum can solve all NP problems
Groverâ€™s algorithm  with quantum computers, something like you can only use sqrt of number of steps
adiabatic optimization  like quantum simulated annealing, maybe can solve NPcomplete problems
dwave  company made ~2000 cubit machine
donâ€™t maintain coherence well
algorithms for NPcomplete problems may not work
hope: quantum tunneling can get past local maximum in polynomial time maybe
empircally unclear if this is true
quantum supremacy  getting quantum speedup for something, maybe not something useful
2.5.4. maxwellâ€™s demonÂ¶
second law of thermodynamics: entropy is always increasing
hot things transfer heat to cold things
temperature is avg kinetic energy  particles follow a diistribution of temperature
separate 2 samples (one hot, one cold) with insulator
idea: demon makes all fast particles go to hot side, all slow particles go to slow side  this is against entropy
demon controls door between the samples

demon opens door whenever high temperature particle comes from cold sample, then closes
demon opens door for slow particles from hot sample, then closes
problem: demon has to track all the particles (which would generate a lot of heat)