1.1: global perspectives
- QC and QI: study of information processing tasks accomplished using QM systems
1.1.1:
- classical physics were predicting absurdities -> UV catastrophe or electrons spiraling into the nucleus -> creation of QM
- QM: set of rules for construction of physical theories
- possible to use quantum effects to signal faster than light -> whether it is possible to clone an unknown quantum state (construct copy of QS) -> not possible in general with QM -> no-cloning theorem
- controlling single quantum systems -> trap single atom in atom trap, isolating from world allowing us to probe it -> explore untouched regimes in Nature
- computer science -> Church-Turing Theorem -> UTM complexly captures what it means to perform a task by algorithmic means
- quantum effects beginning to interfere in functioning of electronic devices as they are getting smaller and smaller
- failure of Moore’s Law -> move to different computing paradigm
- ordinary computer can simulate QC but not efficiently (polynomial time)
- strengthened version of Church-Turing thesis:Any algorithmic process can be simulated efficiently using a Turing machine -> for purposes of analyzing whether a given computational task can be accomplished efficiently, restrict ourselves to analysis of Turing machine model
- analog computation: analog computers can solve efficiently when Turing machines can’t -> violation? but when assumption about presence of noise in analog computers is made, their power disappears??
- unlike analog computation, QM can tolerate finite amount of noise and retain computational advantages
- first challenge: number is prime or composite using randomized algorithm -> could only determine if probably prime/composite -> perform the algorithm a few times
- ad hoc modification -> Any algorithmic process can be simulated efficiently using a probabilistic Turing machine
- Deutsch: can laws of physics be used to derive stronger version of Church-Turing thesis -> computational device capable of efficiently simulating an arbitrary physical system -> because laws of physics were QM -> quantum analogs of machines defined by Turing
- Universal Quantum Computer ?
- quantum computers may be able to efficiently solve problems that have no efficient solution on a probabilistic Turing machine
- Shor and Grover algorithms
- Feynman: essential difficulties in simulating quantum mechanics with classical computers -> build computers based on principles of quantum mechanics to avoid difficulties
- algorithm design for quantum computers is hard because . human intuition is rooted in classical world . must design an algorithm that is better than existing classical algorithm, not just QM!
- while computer science was exploding, information theory was too
- Shannon: mathematically define concept of information
- two key questions about communication of information:
- what resources are required to send information over communications channel?
- can information be transmitted in a way that is protected against noise in communications channel
- two fundamental theories:
- noiseless channel coding theorem: quantifies physical resources required to store the output from information source
- noisy channel coding theorem: quantifies how much information it is possible to reliably transmit through noisy communications channel -> upper limit on protection afforded by error-correcting codes
- two key questions about communication of information:
- to achieve reliable transmission in presence of noise: error-correcting codes
- quantum information theory:
- Schumacher: quantum bit/qubit has tangible physical resource (analogue to noiseless coding theorem)
- but no analogue to noisy channel coding theorem
- theory of quantum error-correction has been developed: allows QC to compute efficiently in presence of noise and allow communication over noisy quantum channels
- CSS (Calderbank, Shor, Steane) codes and stabilizer codes (Calderbank, Rains, Shor, Sloane)
- quantum error-correcting codes: protect quantum states against noise - transmitting ordinary classical information using quantum channel?
- Bennett/Wiesner: transmit two classical bits of information while only transmitting one quantum bit -> superdense coding
- distributed QC: QC require exponentially less communication to solve certain problems
- study of information theory: properties of single communications channel
- in applications: networks of many channels -> networked information theory: information carrying properties of networks of communication channels -> very developed
- networked quantum information theory, still in infancy, no unifying theory of networked information theory exists for quantum channels
- cryptography: communication and computation between two paries who may not trust each other
- private key cryptosystems: A and B communicate by sharing a private key (only they know)
- problems: how to distribute the keys?
- QM can be used to distrbute keys such that A and B’s security is not compromised -> quantum cryptography -> observation disturbs the system being observed -> an observer would be visible as disturbance of communications channel
- public key cryptosystems: B publishes a key available to the general public, A can use this key to encrypt a message but a third party cannot use the public key to decrypt the message. B has secret key matched to the public key.
- solve problem of key distribution
- RSA cryptosystem -> most widely deployed key cryptosystem
- difficult to invert encryption stage if only public key available -> belief that this cannot be solved on classical computer (factoring), but it can be solved on QC!
- private key cryptosystems: A and B communicate by sharing a private key (only they know)
- quantum entanglement: uniquely QM resource
1.1.2: future
- think physically about computation
- any physical theory -> basis for theory of information processing and communication
- think computationally about physics -> physics about understanding elementary objects/simple systems, interesting things happen when things are larger and more complicated (chemistry and engineering, ad hoc fashion)
- computation and algorithms as systematic means of constructing and understanding (small and relatively complex) systems
1.2: quantum bits
- mathematical objects with certain specific properties
- abstract entity: construct a general theory of QC/QI that doesn’t depend on specific system
- qubit can be |0⟩, |1⟩ or a linear combination of states |ψ⟩ = α|0⟩ + β|1⟩ (superposition)
- vector in 2D space
- computational basis states: |0⟩, |1⟩ -> form orthoormal basis for this vector space
- we cannot examine a qubit to determine it’s quantum state
- qubit’s state is unit vector in 2D complex vector space
- lack of direct correspondence between elements of abstraction and real world with qubits -> there is indirect correspondence for qubit states to be manipulated and transformed to lead to measurement outcomes -> these quantum states have real, experimentally verifiable consequences.
- exist in continuum of states until it is observed
- because |α|2 + |β|2 = 1 we can say: |ψ⟩ = eiγ(cos(θ/2) + eiϕsin(θ/2))
- θ and ϕ define a point on unit three-dimensional sphere (Bloch sphere)
- Bloch sphere can be used to describe single qubits
- how much information represented by a qubit -> infinite number of points on unit sphere so infinite binary expansion of θ
- not true: measurement changes the state of qubit, collasping the superposition
- only 0 or 1, so measurement only returns one state
- not true: measurement changes the state of qubit, collasping the superposition
- would need to measure infinite number of qubits to determine α and β
- how much information is represented by a qubit if we do not measure it? -> potential amount of “hidden information” grows exponentially with more qubits
1.2.1: multiple qubits
- two qubits have four computational basis states: |ψ⟩ = α00|00⟩ + α01|01⟩ + α10|10⟩ + α11|11⟩
- {0, 1}2: set of strings of length 2 with each letter either one or zero
- measuring the first qubit as 0 gives probability |α00|2 + |α01|2 and post-measurement state: $$|\psi ' \rangle = \frac{(\alpha_{00} | 00 \rangle + \alpha_{01} | 01 \rangle)} {\sqrt{|\alpha_{00}|^2 + |\alpha_{01}|^2)}}$$
- important two qubit state, Bell state or EPR pair: $$\frac{|00\rangle + |11 \rangle}{\sqrt{2}}$$
- key ingredient in quantum teleportation and superdense coding
- upon measuring first qubit, second qubit’s value is correlated
- Bell: measurement correlations in Bell state are stronger than could ever exist between classical systems
- consider a system of n qubits:
- computational basis states: |x1, x2...xn⟩
- quantum state is represented by 2n amplitudes
- amplitude, α, is for α|0⟩
1.3 quantum computation
- changes occurring to a quantum state
- quantum circuit with quantum gates
single qubit gates
- quantum NOT gate: α|0⟩ + β|1⟩ → α|1⟩ + β|0⟩ it acts linearly
- nonlinear behaviour can lead to paradoxes
- NOT gate in matrix form
$$ X \equiv \begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix}$$
- quantum state α|0⟩ + β|1⟩
$$ X \begin{bmatrix} \alpha \\ \beta \end{bmatrix} = \begin{bmatrix} \beta \\ \alpha \end{bmatrix}$$
single qubit quantum gates: two by two matrix
quantum gate must still ensure the probabilities sum to 1
the matrix U representing the single qubit gate must be unitary: U†U = I
- U† is obtained by transposing then complex conjugating U
any quantum gate must follow this unitarity constraint
Z gate: leaves |0⟩ unchanged and flips sign of |1⟩ to −|1⟩
$$ Z \equiv \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$$
Hadamard gate, square root of NOT gate, but H2≠ NOT: $$|0\rangle \rightarrow \tfrac{|0\rangle + |1\rangle}{\sqrt{2}}$$ $$|1\rangle \rightarrow \tfrac{|0\rangle - |1\rangle}{\sqrt{2}}$$
$$ H \equiv \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$$
we can also decompose a single qubit gate into a product of rotations
- can build up arbitrary single qubit gate using finite set of quantum gates
an arbitrary quantum computation on any number of bits can be generated by a finite set of gates that is said to be universal for quantum computation
1.3.2 multiple qubit gates
controlled-NOT or CNOT gate
- control qubit and targit qubit: |00⟩→|00⟩; |01⟩→|01⟩; |10⟩→|11⟩; |11⟩→|10⟩
- generalized: |A, B⟩→|A, B⨁A⟩ the control qubit and targit qubit are XORED and stored in target
$$ U_{CN} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$$
- classical gates like NAND or XOR can’t be understood as a unitary gate; these gates are irreversible or non-invertible
- given output, cannot determine the input (a loss of information)
- unitary quantum gates are always reversible -> quantum gate can always be inverted by another quantum gate (because of unitary)
prototype gates (CNOT and single qubit gates): any multiple qubit logic gate can be composed from CNOT and single qubit gates
1.3.3 measurement in bases other than computational basis
- given any basis states |a⟩ and |b⟩ for a qubit, it is possible to express an arbitrary state as linear combination α|a⟩ + β|b⟩
- if given states are orthonormal: possible to perform measurement with respect to |a⟩,|b⟩ basis with probabilities |α|2 and |β|2
- formalism allows us to describe observed experimental results
1.3.4 quantum circuits
features in classical circuits not usually present in quantum circuits:
- no loops, circuit is acyclic
- no joining wires together (FANIN), resulting single wire containing bitwise OR of inputs
- not reversible, not unitary
- FANOUT: QM forbids copying of qubit
controlled U Gate: suppose U is a unitary matrix, define as a natural extension of controlled-NOT gate
- single control qubit and n target bits
measurement: convert single qubit state into probabilisticclassical bit M
1.3.5 qubit copying circuit
- no cloning theorem:
- can we create |ψ⟩|ψ⟩
- once we measure one qubit, the state of the other is determined
- measuring the first qubit loses the extra hidden information, but if we could make a copy then the second qubit still contains the extra hidden information -> therefore cannot create a copy
- can we create |ψ⟩|ψ⟩
1.3.6 example: bell states
- Hadamard gate: puts top qubit in a superposition
- CNOT: top qubit is control input
- transforms 4 computational basis states into Bell states
$$|\beta_{xy}\rangle = \frac{|0,y\rangle + (-1)^x |1,\bar{y}\rangle}{\sqrt{2}}$$
1.3.7 example: quantum teleportation
- moving quantum states around, even in absence of channel
- A and B generate an EPR pair, and each one takes a qubit from EPR pair.
- A wants to send a qubit |ψ⟩ to B but does not know state of qubit and can only send classical information (A and B don’t where each other are)
- A doesn’t know state of |ψ⟩
- describing |ψ⟩ takes infinite amount of classical information because |ψ⟩ takes values on continuous space
- A wants to send a qubit |ψ⟩ to B but does not know state of qubit and can only send classical information (A and B don’t where each other are)
- use quantum teleportation:
- A interacts the |ψ⟩ with half of the EPR pair -> 00,01,10,11
- B gets the two bits from A and can recover original state |ψ⟩
- not faster than light due to need to transport two clasical bits using classical communication channel
- appears to create copy of quantum state being transported: only target qubit in state |ψ⟩ and original data qubit is a computational basis
- one shared EPR pair and two classical bits equal to one qubit