Quantum Information

Following John Preskill’s 1998 Quantum Information and Computation notes.

Introduction

• Landauer’s principle: It takes energy to erase information (since erasure always compresses phase space, such processes are irreversible)
  • You can store a bit of information as one molecule in a box. If it’s on the left, it’s on, else it’s off. If you slowly compress the volume in half, you’re gaurenteed to be in the LHS. The change in entropy is k ln 2, which has some associated work that needs to be performed
• Logic gates used to perform computation are typically irreversible
  • For instance, NAND is irreversible, since one bit of information is lost for each gate
• Charles Bennett observed that any computation can in principle be done reversibly
  • You can construct a Toffoli gate:
    • Input is (a,b,c)
    • Output is $(a,b, c \oplus a ^ b)$
      • So a and b get mirrored, and the third bit gets flipped if the first two bits are both 1 (otherwise, it mirrors the input)
  • You can in principle do any computation up to the end, print out a copy of the answer (logically reversible process), then step back the computation back to the beginning

Maxwell’s Demon

• The aforementioned ideas allows a resolution of the Maxwell’s demon paradox
  • The original formulation is as follows: You have a partitioned box (split into A and B parts) and some demon which observes the molecules in the box
    • If a fast particle is moving from A to B and it will cross the partition, then the demon allows it through
    • If a fast particle is moving from B to A across the partition, the demon blocks it
    • Over time, you will get faster particles on the right and slower ones on the left with minimal work. This has the effect of having heat flow from a cold place to a hot place at no cost, in violation of the 2nd law of thermodynamics
    • The resolution to this is that the demon needs to have some memory/ keep information on the molecules in the box. If the demon has a finite memory capacity, eventually, information will need to be erased, which results in work being done

Quantum Influence

• The quantum nature of reality changes the definition of information
• Quantum mechanics is a truly random process, which has no place in deterministic classical dynamics
• The uncertainty principle implies that the act of acquiring information from a system invariably disturbs the system
• The no-cloning theorem of quantum mechanics states that quantum information cannot be copied with perfect fidelity
  • In classical computation, you can clearly copy a state with impunity
• The main fundamental difference of quantum mechanics is Bell’s theorem. This states that quantum mechanics is not a local hidden variable theory. All of the information in a quantum system is encoded in nonlocal correlations that have no classical analog

Quantum Complexity

• Classically, the indivisible unit of information is the bit
• The quantum analog is the qubit, which is a vector in a 2D complex vector space with an inner product
  • ie. $|\phi > = a|0> + b | 1>$
• Performing measurements on $\phi>$ gives a probabilistic output
• Generalizing to N qubits, you need $2^{N}$ basis vectors to completely specify the state
  • This can be compactly written as $\Sigma_{x=0}^{2^{N}-1} a_{x} | x>$ where $a_{x}$ are complex numbers
• Thus, any quantum computation consists of applying unitary transformations onto this N qubit representation. You can then measure the state by projecting onto one of the basis vectors
  • A quantum computation is probabilistic by nature, so multiple runs are not guaranteed to yield the same result
• All of these operations can be simulated on a classical computer (re: vector representations, matrix multiplications, inner products)
  • The trouble arises if you want to simulate a large number of qubits. Even 100 qubits requires manipulating way more than $10^{30}$ complex numbers as a vector
  • You can’t divide and conquer the complexity of a quantum system due to the nonlocal correlations imparting the vast majority of the information content
• Standard computers are Turing complete: If given an infinite amount of time and infinite memory, any computation can be done
• Problems can be classified as “hard” or “easy” depending on how much time and memory they consume
• Describe how “hard” a problem is should be universal: it should not depend on the hardware you’re running on
  • The standard distinction is between polynomial time algorithms and exponential time algorithms
• Simulating a quantum computer on a classical computer is not a polynomial time algorithm
  • In light of this physical reality, a classical Turing machine is not an appropriate model for quantum computers

Errors

• Information is stored in nonlocal correlations of the system. A large quantum system can couple to it’s environment, which “spreads out” the correlation to the environment. You can’t measure the environment perfectly, so you inevitably lose information
  • Can think of this as decoherence: the enviornment is continually “measuring” the state, which causes it to drift over time
• A separate problem is that we don’t have perfect quantum gates. Trying to implement perfect unitary transformation ain’t happening. There will always be some error of order $\epsilon$ from the ideal
• You need some sort of error correcting codes to deal with this reality
  • Classically, there are a ton of error correcting codes (think Hamming codes)
    • The simplest is just repetition: make N copies of your data, then do majority polling to determine the correct output
  • Quantum mechanically, more things can go wrong
    • You can have the standard bit errors like in classical computing
    • You can have phase errors, where, for instance, $|0> \rightarrow - |0>$
      • This phase shift is continuous, unlike the jump discontinuities of classical bit flips
    • You can’t clone a quantum system with perfect fidelity
    • You can’t measure the system without disturbing it
• Unsurprisingly, Peter Shor developed the first quantum error-correcting code, which can be though of as an extension of the N-bit repetition code.
  • For simplicity, suppose that we want to encode one qubit as 3 qubits
    • So the state $a|0> + b |1> = a|000> + b|111>$
  • We want to be able to detect errors without destroying this superposition
    • If I measure the first qubit and get 0, then all the states collapse to 0 and I lose information about the coefficients a and b
    • What if you instead measure pairs of qubits?
      • Let the 3 qubit state be represented as $|x,y,z>$. Define $x \oplus y$ denote XOR-ing the bits
      • Define the two-bit observable $(y \oplus z, x \oplus z)$ For our 3-qubit system, this observable will dictate which index an error occurred at
        • 0 for no error, and then 1,2,3 (in binary) to denote that qubit 1,2,3 has been flipped (going left to right)
    • What if there is a small deviation in state?
      • Say that the following perturbations occur: $|000> \rightarrow |000> + \epsilon |100>$ and $|111> \rightarrow |111> + \epsilon |011>$
      • When you project onto the eigenstate of $(y \oplus z, x \oplus z)$, most of the time (with probability $1-|\epsilon|^{2}$), the state will get reprojected back to the original state. The $|\epsilon|^{2}$ outcome just sets the observable to (0,1), indicating a bit flip in position 1
      • This scheme fails with a probability of $|\epsilon|^{4}$ if multiple bit-flips happen
    • The above scheme allows us to:
      • Make a measurement of the system without damaging information ( you gain information about the error location, but not the exact configuration of your system)
      • Small continuous errors either get corrected immediately, or produce a large discrete error which can be corrected
      • Avoid the no cloning theorem ($a|000>+b|111>$ is not the same as $(a|0>+b|1>)^{3}$)
    • The only source of error left are phase errors
      • Do a similar trick used to address the other problems:
        • Define a set of 9-qubit states $|0> = \frac{1}{2^{\frac{3}{2}}}(|000> + |111>)(|000> + |111>)(|000> + |111>)$ and $|1> = \frac{1}{2^{\frac{3}{2}}}(|000> - |111>)(|000> - |111>)(|000> - |111>)$
          • Define a “cluster” as state within each parentheses
            • If a bit flip occurs within a cluster, you can correct it with the aforementioned scheme
        • Observe that the phases between each cluster is aligned (ie. they are all + or all -). If a phase flip occurs, then the phases between each cluster won’t be aligned (ie. one is + and one is 1)
        • You can generate a similar index observable, but now it’s a 6-bit observable. If this observable is non-zero, than you can detect which cluster has a different sign compared to the others and correct folor it
    • The most general single-qubit unitary transformation can be expanded to order $\epsilon$ in terms of the Pauli matrices:
      • $U = 1+ i\epsilon_{x}\begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}+ i \epsilon_{y}\begin{pmatrix} 0 & -i \\ 0 & i \end{pmatrix}+ i\epsilon_{z} \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$
      • Each term can be though of as a bit flip, a phase flip, and a combination of the two respectively
• The key takeaways of the quantum repetition code are:
  • That the errors became digitized: Either you are in a state of no error, or you are in a discrete set of error states that you know how to recover from
  • You can measure the error without measuring the data (re: sampling all of the qubits)
  • The errors are local (re: uncorrelated), and the encoded information is nonlocal, so as long as you keep your measurements to single qubits, then you can’t get information out of the system

States and Ensembles

Quantum Mechanics Axioms

• A state is a ray in Hilbert space
  • A Hilbert space is a vector space over the complex numbers
  • You can define an inner product which maps an ordered pair of vectors to C that is strictly positive, linear, and skew symmetric (ie. swapping order of vectors is complex conjugation)
  • An additional constrain is that there is some notion of a norm: $||\phi|| = <\phi| \phi>^{\frac{1}{2}}$
  • A ray is an equivalence class of vectors which differ by a multiplication by a nonzero complex scalar. We choose the representative of this class to have a unit norm
• An observable is a property of a physical system which can be measured
  • Must be a linear, self-adjoint operator(ie. $<\psi| A \psi> = < A^{\dag} \psi | \psi >$ )
    • As a result of the self-adjoint property, we can write $\Sigma_{n} a_{n} P_{n}$ where the projection operator $P_{n}$ satisfies $P_{n}P_{m} = \sigma_{n,m} P_{n}$ and $P^{\dag} = P$
• We can make a measurement of a state by using the projection operator
• The dynamics of the system is unitary (re: probability preserving) and is governed by $\frac{d}{dt}|\phi> = -i H |\phi>$
  • We can describe the time evolution of a state as $|\phi(t)> = U(t) | \phi(0)>$
  • If H is time independent, then $U = exp(-i t H)$

Qubits

• A qubit is a state in a 2D Hilbert space that can take the form $a|0> + b|1>$

Symmetries

• Any symmetry of a quantum system must leave the probabilities untouched
  • This implies that a symmetry is a automorphism of the Hilbert space which preserves the absolute values of inner products for all members of the space
• Each symmetry maps onto either a unitary or anti-unitary operator
  • Anti-unitarity doesn’t matter for continuous symmetries
  • Compositions of symmetries should also be a symmetry (up to an overall phase factor). This follows from group theory
• Symmetries should commute with the dynamics of a system
  • Let R be the symmetry in question. The following must hold: $U(R) exp(-itH) = exp(-itH) U(R)$
  • For a continuous symmetry, we can let R get arbitrarily close to the identity: $R = I + \epsilon T$. This implies that, to first order, $U = 1-i\epsilon Q$ where Q is unitary. This in turn implies that Q commutes H
    • We call Q the generator
  • Since any finite transformation can be written as a product of infinitesimal ones: $R = (1+\frac{\theta}{N} T)^{N} \rightarrow U = exp(i\theta Q)$, knowing how the infinitesimal symmetry transformations are represented lets you do finite transformations

Rotations

• A finite rotation is given by $R(\hat{n}, \theta) = exp(-i\theta\hat{n}\cdot J)$
  • $\hat{n}$ is the axis of rotation, $\theta$ is the rotation angle, and $\vec{J}$ is the angular momentum
• The associated commutation relationship for angular momentum is $[J_{k}, J_{l}] = i \epsilon_{klm} J_{m}$
• The simplest non-trivial irrreducible representation of angular momentum is 2D, as given by the Pauli matrices: $J_{k} = \frac{1}{2}\sigma_{k}$
  • The Pauli matrices satisfy the anti-commutation relationship: $\sigma_{k}\sigma_{l}+\sigma_{l}\sigma_{k} = 2\delta_{lk} I$
• We can use the Pauli matrices to write any finite rotation as $U(\hat{n},\theta) = exp(-i\frac{\theta}{2} \hat{n}\cdot \vec{\sigma})$
  • There is a $2\pi$ ambiguity, which gives rise to spinor representations
    • For rotaation, you have the action $U(\hat{n} ,\theta = 2\pi) = -1$
• The components of angular momentum transform under rotations like a vector
  • $U(R)J_{k} U(R)^{\dag} = R_{kl} J_{l}$
  • This implies that if state $|m>$ is an eigenstate of $J_{3}$, then $U(R)|m>$ is an eigenstate of $RJ_{3}$ with the same eigenvalue
  • The above implies that we can construct eigenstates of angular momentum along the axis $\hat{n} = < \sin \theta \cos \phi, \sin \theta \sin \phi, \cos \theta >$ by applying a rotation through $\theta$ to the z axis
    • This means that all direction measurements can be performed by first rotating the $\hat{n}$ axis to the z axis, and then measuring along z