CSE 490Q Notes

Linear algebra is not specific to quantum! Also possible for probabilistic computation.

Three ways to represent 1/2 chance of heads, 1/2 chance of tails:

Matrix notation: [1 2]

Multiplication by unit vectors: 1/2*e_H + 1/2*e_T

Dirac Notation:

​|v> which means column vector, Nx1 (| = many rows, > = one column)

<v| means row vector, 1xN. v doesn't inherently have an orientation; it's simply a vector with 1 in one dimension or the other, and this coerces it into a row vector.

Then, like in arithmetic, things are multiplied by being put next to each other. Eg, <v| |w> means v^t times w (assuming they both start as column vectors), or v dot w. <v|w> is shorthand.

​|w><v|, ie w v^t, results in a matrix.

Think of data as flowing from right to left. For |v>, a single data point enters on the right, is processed by v, then a vector comes out. For <v|w>, a single point comes out, some weird shit happens in the middle, and a single value comes out. |w><v| turns a vector into a matrix.

Back to the coins: 1/2|e_H> + 1/2|e_T>.

We can use |1> to indicate the first basis vector [1 0] (as a column) because the special dirac notation disambiguates it from the numeral 1. (When representing random bits, |0> = [1 0] and |1> = [0 1])

So, with coins: 1/2|H> + 1/2|T>

A random bit has some probability of being 1 and some probability of being zero. These probabilities must add to one.

The linear algebra computing we've been describing so far is called "BPP". Stochastic matrices have columns that sum to 1, and the sum of the components of a valid state sum to 1.

In BQP, the components of state vectors and operation matrices are complex. They can have negative real parts, even. And rather than requiring that columns sum to 1, we require that the square of the magnitudes in each column sum to 1. This is the 2-norm, while the BPP uses the 1-norm (sum). We don't square root the result because 1²=1.

A qubit has two complex numbers whose 2-norm is 1.

In dirac notation, 〈x| is the complex conjugate and transpose of |x〉. A † symbol (dagger) is an explicit way to transpose and conjugate a matrix. 〈x|x〉 is \(\bar \textbf{x}\) dot \(\textbf{x}\). Recall that \((x)(\bar x)=|x|^2\), so 〈x|x〉=|x|².

Rather than a "stochastic" matrix, we call quantum operation matrices "unitary matrices". TFAE:

• U is a unitary matrix.
• | u|x〉| = | |x〉 | (for any p-norm)
• U^t U = Identity
• Any eigenvalue of U has norm/magnitude 1. If it were not so, then an eigenvector would have the sum of its probabilities be changed!
• |det(U)|=1

I think stochastic matrices (1-norm) are also unitary? Are those defintiions equivalent if higher norms are used, too?

The definition of unitary matrices only makes complete sense when they are defined over the complexnumbers. So they are not "stochastic".

The second and third are equivalent becuase \[||U|x\rangle ||^2=(U|x\rangle)^\dagger(U|x\rangle)=\langle x|U^\dagger U|x\rangle=\langle x|x \rangle=||x||^2\] Which is 1 if \(x\) is a valid state vector to begin with.

The tensor product of two quantum states is a valid quantum state. \[||a \otimes b||^2 = ||[a_1b_1, a_1b_2, ..., a_2b_1, a_2b_2, ...]||^2 = (a_1b_1)^*(a_1b_1)+... = a_1^2(b_1^*b_1+b_2^*b_2+...)+a_2^2(...)+... = (a_1^2+a_2^2+...)(b_1^*b_1+b_2^*b_2+...)=||a||^2||b||^2\] TODO: something's wrong with the $a$s at the end.

To show that \(U\otimes V\) is a unitary matrix for unitary matrices U and V, show that \((U \otimes V)^\dagger(U\otimes V)=(U^\dagger U)\otimes(V^\dagger V)=I\), one of the equivalent definitions of a unitary matrix.

Property: \((a \otimes b)^\dagger=a^\dagger \otimes b^\dagger\).

If \(U\) is unitary, so is \(U^\dagger\). \(U^\dagger\) is the inverse of \(U\), because \(U^\dagger U=I\)! (I should've noticed that). This is not usually the case for a stochastic (1-norm) matrix. For example, [ .5 .5 \\ .5 .5] is clearly singular. . If you know the output state of a quantum computer, and the operations that were carried out, you can transpose all the operations and multiply to get the input state. But if quantum computers are reversible, and classical computers are not, are quantum computers more restricted?

But we can reverse classical computation by…just storing the inputs to each stage permanently? I'm pretty sure that's cheating.

When we carry out probabilistic computing, our matrices tell us probabilities, but the output bits are in definite states. We run it many times to determine the probabilities. But a quantum computation results in bits that actually contain the 0 and 1 states to different extents; they're in superposition. We coerce it to a bit with probability of 1 equal to q|1〉 and probability of 0 equal to q|0〉, where q is the qubit's state.

A diagonal matrix with all diagonal values being \(e^{i\theta}\) is unitary. This "rotates" all the qubits, but the magnitudes of their |0〉 and |1〉s stay the same. It would be fair to ask, what's the point of phase at all if it doesn't affect magnitude? Maybe answer: The phase difference between |1〉 and |0〉 matters, but not the "bias" phase they both share. But we just don't know what that phase difference is used for.

Partial Measurement: We can observe certain qubits without others. You can't observe only certain combinations of qubits (eg, it doesn't make sense to measure |01〉 only – it would tell you things about 00, 10, and 11 as well – so you'd just measure both qubits).

If you have a vector of multi-qubit state, how do you model a single-qubit measurement?

1. Determine the probability that a certain qubit will be measured as one or zero by factoring the tensor product. Eg, if we have a state of 2 qubits with |00>, |01>, |10>, and |11>, we can turn it into the form |0>⮾|x>+|1>⮾|y> for some x and y single-qubit states, using simple rules of distributivity and stuff over tensor product.
2. Determine what the resulting state will be when one of the qubits is measured as a certain value. From the equation above, say that the first bit is observed as 1. Then the state of the other bits is certainly related to |y>, but |y> on its own is not a valid state vector and must be normalized by uniformly scaling up its components until the sum of their squares is 1 (\(|y\rangle * 1/|y|\), where the norm is the square root of the sum of the squares of the components of y. The sum of the squares of the partial state add up to \(|y|^2\), so we want to increase this sum by \(1/|y|^2\), which is achieved by multiplying each component by \(1/|y|\), because this causes the square of each component to be multiplied by \(1/|y|^2\), which we can then factor out). This does not violate any rules when you start manipulating the scaled y as a complete state; all our theorems depend only on 2-norm magnitude of the state, not any specific dependencies between the individual components.

Many multi-qubit states are not "independent" combinations of qubits. When a multi-qubit state is a combination of independent probabilities, it is a "product state". In these cases, we don't need to store 2ⁿ complex numbers – just n, then we could do tensor product later. But in "entangled states", we need 2ⁿ. This is quantum!

Einstein, Podolski, and Rosen studied the aptly named "EPR States" such as .707|00〉

• .707|11〉, which is one of many "Bell States" (maximally entangled states). .707|10〉
• .707|01〉 is another Bell state.

How do we operate on an initial, non-entangled state to create an entangled state? We obviously cannot tensor together two operation matrices, (U⮾V)(a⮾b)=(Ua)⮾(Ub) which is a product state. One of the simplest examples: CNOT, toggle the second bit if the first bit is 1. But the operation carried out on one bit is dependent on the state of another bit, so the operation matrix is clearly not a tensor product. The matrix:

1	0	0	0
0	1	0	0
0	0	0	1
0	0	1	0

If the input vector is [ 00, 01, 10, 11 ]

When developing intuition for the Kronecker product of operations, we said that the operation on the right hand of the matrix only needs local information, hence why it is duplicated as a block matrix throughout the product matrix. But breaking this CNOT matrix into blocks, it is clear they are not scalar multiples – the effect is only achieved with global knowledge.

Previously, we talked about how to transform a state if it is partially observed (ie, some but not all qubits are observed). We were able to "factor out" the observed bit using the tensor product to determine what the other bits should be. And, interestingly, this factoring is still possible; recall we were able to perform the factoring without any information about how the state was created from tensor products, so it need not be created from tensor products.

Eg, for .707|00〉+.707|11〉, we decompose into .707|0〉⮾|0〉+.707|1〉⮾|1〉. See how tensor product here doesn't mean anything about independence, because there's a separate tensor product for each possible state of the first bit.

"Marginal" Distribution: We can determine the probability distribution for a single qubit pretty simply, by adding the complex numbers of all states where that qubit is 0, and making that the "probability" of it being zero, and proceed similarly for 1. In fact, we have to do this as part of our "decomposition" used in modeling a single qubit measurement. Then he said this doesn't work for qubits?

Recall that qubits actually store the probability distribution itself, and are not "actually" one nor zero. So if you have an entangled pair, then observe one half of it, the other half might be resolved into one state or the other, or the probability distribution might change.

When you look at part of an entangled state, it acts like its in a probability distribution between the different states that part might be in, depending on what happened to the other side.

Allows full visualization of how one-y or zero-y a qubit is, as well as the phase difference between the one and zero components. Note that (as long as we don't care about global phase), any qubit can be represented by the following equation: \[\cos(\theta/2)|0\rangle+e^{i\varphi}\cdot\sin(\theta/2)|1\rangle\] Note that this qubit is valid because \(\sin^2 x+\cos^2 x=1\) and \(\|e^{i\varphi}\|=1\).

Then, we define the Bloch sphere like so: Start with a vector pointing straight up. Let the x-axis point out of the page, the y-axis point to the right, and the z-axis point up. Let \(|0\rangle\) be at (0,0,1). Then rotate it around the y-axis (so at first it comes toward you) by θ. So if the bit is \(|0\rangle\), don't move it at all, but if it is \(|1\rangle\), it points straight down (0,0,-1). Then, rotate it around the z-axis by ϕ, so that at first it goes right.

• |0> = (0,0,1)
• |1> = (0,0,-1)
• -|0> = (0,0,1) (phase 180, but who cares)
• -|1> = (0,0,-1) (phase 180, but who cares)
• \(1/\sqrt2\cdot(|0\rangle+|1\rangle)\) = (1,0,0)
• \(1/\sqrt2\cdot(|0\rangle-|1\rangle)\) = (-1,0,0) (phase 180)

Basic transforms in terms of what they do to the Bloch sphere:

• Z=[ 1 0 \\ 0 -1 ]: Inverts the second term, i.e, adds 180 to phase, inverting both x and y coordinates.
• X=[ 0 1 \\ 1 0 ]: Inverts the z coordinate (flips around xy-plane) (not gate)
• H=1/sqrt(2)*[ 1 1 \\ 1 -1 ]: Rotates 90 degrees around y-axis, then flips over x-y

Because the homework keeps asking about them.

F1:

0	0
1	1

G:

1/2	0
1/2	1

X (not):

0	1
1	0

The "more mysterious" parts of Quantum Mechanics. Oh boy.

A product state can be represented as a tensor product of some number of qubits. The qubits are not entangled whatsoever.

An entangled state has some probability connections between qubits. Without entangled states, you could just store each qubit separately in polynomial space on a classical system.

An EPR pair is \(\frac{1}{\sqrt2}|00\rangle+\frac{1}{\sqrt2}|11\rangle\), one of the maximally engangled Bell States, because if you measure one qubit, it gives you 100% of the information about the state of another qubit. More accurately, neither qubit can be described on its own using only a quantum state.

That doesn't mean entangled qubits can't be described. Recall that a qubit state isn't a set of probabilities; the qubit, before its measured, actually has those coefficients tucked away somewhere, in their full precision. When you try to describe a single qubit \(a\) that's entangled with qubit \(b\), the state of \(a\) depends on what happens when you measure \(b\). But what happens when you measure \(b\) is probabilistic. Thus we need a probability distribution between two different states of \(a\), one state that will occur if \(b\) is measured as zero, and another if \(b\) is measured as one.

Although we think about describing the state of an entangled qubit as a "probability distribution between quantum states", the math is a bit simpler; since quantum states appear probabilistic when we measure them, we can combine the "quantum state" part of the probability and the "entanglement probability distribution" into a single probability. See slide 5 for an example of the math. It's done mainly by "factoring out" the qubit of interest from all the others: \[\sum_{\mathrm{all\ states\ of\ other\ qubits}}(\mathrm{state\ of\ all\ other\ qubits})\otimes(a|0\rangle+b|1\rangle)\], where \(a\) and \(b\) will differ depending on the current "state of all other qubits". The probability of the state \(a|0\rangle+b|1\rangle\), then, is the amplitude of the "state of all other qubits" (which might be, eg, \(|0111001100\rangle\)). You might need tensor products on both sides of the qubit in question (here I assumed the qubit was the "last" one in the state), but the technique is the same.

Nothing "happens" to one entangled qubit when you mess with the other. That's the way the probability distributions work. That being said, if you measure one qubit of an entangled qubit, it does give you more information about the other qubit – but information about the way it already was.

It's possible to apply a single-bit operation to an entangled bit. It's equivalent to applying that operation matrix, tensor product'ed with identities on both sides, to the entire state (ie, the same thing as applying an operation to an un-entangled state).

A mixed state contains qubits that are entangled with qubits outside that mixed state. Put differently, "mixed state" means "probability distribution between quantum states". Any other state is a pure state, which I think is the same as a product state.

The monogamy of entanglement states that if two qubits are maximally entangled, neither can be entangled whatsoever with anything other qubit. If you and a friend have maximally entangled qubits, you know that nobody else can have a qubit entangled with them. Consider the "GHZ" state: \(\frac{1}{\sqrt2}|000\rangle+\frac{1}{\sqrt2}|111\rangle\). If you measure any one bit, you end up with a probability distribution on the other two: 50% chance of measuring \(|00\rangle\) and 50% chance of measuring \(|11\rangle\). This is not a "bell state"; it's a superposition of two product states.

Any quantum operation that can turn a product state into a mixed state (i.e., it can entangle qubits) cannot be written as a tensor product of one-qubit unitary operations. The interesting operations are the non-product ones.

When talking about quantum operation matrices, we will restrict ourselves to matrices smaller than some certain size (eg, \(10\times10\), though a matrix that operates on only 2 qubits at once is enough to do anything you can do with larger ones), otherwise constructing those matrices could be expensive, since the number of elements grows as \(2^n\) with the number of qubits, and it's physically very difficult to construct a quantum computer that acts on many qubits at once.

A "classical circuit" is stuff like AND, OR, NOT, etc. All classical circuits can be build using just NAND gates, and similarly, there's a set of quantum operations that can do anything. One of the simplest (but not the smallest): The union of all possible 1-qubit operations and CNOT.

There are finitely many (two) reversible one-bit classical operations: NOT and identity. But there are clearly infinitely many one-qubit operations, since you can rotate by arbitrary amounts, for example.

The {one-qubit stuff, CNOT} set is actually implemented with Ion Traps! Single-qubit operations are implemented by firing a laser at a specific atom at some frequency that changes its energy state, sometimes. To CNOT a couple atoms, a laser is fired at one in such a way that, since the ions are levitated in a magnetic or electric field, to jiggle back and forth. The electric interactions between the ions cause all of them to jiggle based on the jiggle of the first one. Then a laser is fired at the second atom, and since whether the laser hits the atom straight on is dependent on the jiggling of the atom, which is turn dependent on the jiggling of the first atom, the state of the second one becomes entangled with the first. Apparently this is sorta sketchy so people are moving away from Ion Traps these days.

Qubits have two degrees of freedom; Given the amplitude and phase of either \(|0\rangle\) or \(|1\rangle\), we can figure out the amplitude of the other (norm=1) and we don't care about the phase of the other one, since we know the local phase.

We can restrict 1-qubit operations to H and T and use them to approximate (not exactly equal? due to finitely many multiplications?) any 1-qubit operation.

For efficiency calculations, we'll assume that, if we limit ourselves to a certain maximum size of matrix, any unitary operations using a matrix within that size takes a fixed amount of time.

A physical quantum computer might, for example, need two qubits to be next to each other in order to CNOT them. But that's a compiler level thing: If you try to CNOT two far-apart qubits, the compiler will insert swaps to get them locally before applying CNOT.

We know the mixed state of 50% chance of \(|0\rangle\) and 50% chance of \(|1\rangle\) is the same, under observation, as a single qubit state \(\frac{1}{\sqrt2}|0\rangle+\frac{1}{\sqrt2}|1\rangle\). However, there are certain unitaries we can apply to the qubit that will allow us to see the difference. If we apply the Hadamard gate, then the mixed state will turn into \(\frac{1}{\sqrt2}|0\rangle+\frac{1}{\sqrt2}|1\rangle\), because both \(|0\rangle\) and \(|1\rangle\) turn into that. Under observation it has equal likelihood of 1 and 0. However, if we apply Hadamard to the pure state, we will get \(|0\rangle\), with no 1 component at all, and when measured it will certainly be 0!

For reference: \[H|0\rangle=\frac{1}{\sqrt2}(|0\rangle+|1\rangle)\] \[H|1\rangle=\frac{1}{\sqrt2}(|0\rangle-|1\rangle)\]

Why is Hadamard considered so important? Does it "care" about the phase or something?

Since we know "any 1-qubit operation + CNOT" is a universal instruction set, we can prove that a different instruction set is universal by showing that it can perform any 1-qubit operation and CNOT.

\(|+\rangle=\frac{1}{\sqrt2}(|0\rangle+|1\rangle)\) and \(|-\rangle=\frac{1}{\sqrt2}(|0\rangle-|1\rangle)\). These are orthogonal and form a basis for 1-qubit states. So now we have two common bases for a qubit state; We call the 0 and 1 the Z-basis, and the + and - the X-basis.

You cannot copy a qubit! I.e., |x〉⮾|0〉 cannot be taken to |x〉⮾|x〉 for arbitrary x by a unitary matrix. Any operation matrix must work on the computational basis states TODO

We can make a specific unitary that can copy a state that's one of two orthogonal states (change basis, CNOT (which is "copy" for 0 and 1), then change back). But it won't work on anything else.

What does exp(M) mean for a matrix M? Since exp has a Taylor series that converges, and taylor series (centered at zero) only requires integer exponentiation of scalar multiplication of its argument, we could try to pass in a matrix instead of a scalar. If the matrix in question is Hermitian, it is symmetric, and then by the spectral theorem it has an orthonormal eigenbasis (it is diagonalizable). Now we can substitute into the expression for the Taylor polynomial of e^x:

\begin{align*} e^x&=a_0x^0+a_1x^1+a_2x^2+\dots \\ &= a_0M^0+a_1M^1+a_2M^2+\dots \\ &= a_0(PD^0P^\dagger)+a_1(PD^1P^\dagger)+a_2(PD^2P^\dagger)+\dots \\ &= P(a_0D^0+a_1D^1+\dots)P^{-1} \\ &= P(\mathrm{diag}(a_0\lambda_1^0,a_0\lambda_2^0,\dots)+\mathrm{diag}(a_1\lambda_1^1,a_1\lambda_2^1,\dots)+\dots)P^{-1} \\ &= P(\mathrm{diag}((a_0\lambda_1^0+a_1\lambda_1^1+a_2\lambda_1^2+...) + (a_0\lambda_2^0 + a_1\lambda_2^1+\dots) + \dots))P^{-1} \\ &= P(e^{\lambda_1}+e^{\lambda_2}+e^{\lambda_3}+\dots)P^{-1} \end{align*}

I.e, it's the matrix with exp applied to all of its eigenvalues!

Exponential growth or decay in the real world is modeled by the differential equation \(f'(t)=rf(t)\) with the solution \(f(t)=e^{rt}C\). Well, apparently "evolution" in the quantum world is described by Schrödinger's equation, \(|x'(t)\rangle=-iH|x(t)\rangle\), which has the solution \(|x(t)\rangle=e^{-iHt}|C\rangle\) (notice how the constant is a vector). We want \(|x(t)\rangle\) to always be a quantum state. Since |C> is a valid state, this occurs when \(e^{-iHt}\) is unitary. Which means the eigenvalues of \(e^{-iHt}\) must all be one. The eigenvalues are of the form \(e^{-i\lambda}\) for each λ eigenvalue of H, and \(|e^{-i\lambda}|=1\) exactly when λ is real, because then it's an Euler's formula thing.

A diagonalizable matrix has real eigenvalues exactly when \(H^\dagger=H\), i.e. H is Hermitian. Because \(H=P\mathrm{diag}(\lambda_1, \lambda_2,\dots)P^\dagger\) (how do we know P is unitary?) so \(H^\dagger=(P^\dagger)^\dagger\mathrm{diag}(\lambda_1^*,\lambda_2^*,\dots)P^\dagger\) which is the same as H iff the eigenvalues are real.

\(e^{-iH}\) is unitary exactly when H is Hermitian. All unitaries can be turned into a Hamlitonian, so the two representations are equiv. Given a unitary, we can find the Hamiltonian by looking at the eigenvalues of U. Each eigenvalue \(\mu_j\) is equal to \(e^{-i\lambda_j}\) for one of the eigenvalues of H. Furthermore, each \(|u_j|=1\), so \(u_j=e^{it}\) for some t. This yields \(e^{it}=e^{-i\lambda_j}\), so \(i\log t=-i\log \lambda_j\)

If \(U=e^{-iH}\), then \(\log U=-iH\) or \(H=i\log U\). The logarithm of a matrix is defined similarly to the exponential (in terms of the Taylor polynomial).

using ( (q1, q2) = (Qubit[5], Qubit()) ) {
      H(q1);
}

• How is our "reversible computation" different than just storing all the arguments?
• If protein computing does not include effects from quantum physics, why do we need quantum computers to simulate it? If we could observe protein folding well, could we use it to compute?
• Why use complex numbers if we only care about magnitudes?
• Nature must "measure" a qubit when it is destroyed, otherwise it would be possible to use it for faster than light communication, or so Kevin said. But then wouldn't nature have to measure it a soon as it gets any distance away from you? I.e, it could be used for faster than light communication across a room. Nature "has" to measure it immediately?
• A more precise version of the above question: Does nature internally "measure" the qubits as soon as they're separated, so that, although both qubits are described by a probability distribution of states, those probabilities are depedent? I.e, if I measure \(a\) while \(b\) is on the way to a black hole, the state of \(a\) before I measured it was the state corresponding to the actual version of \(b\) if it were measured? So, i.e., I can tell what will happen when \(b\) is measured after measuring \(a\), or vice versa (assuming the probabilities are 1/0 so no ambiguity).
• What's really wrong with arbitrarily large quantum operation matrices? If locality is not restricted to 2 bits, there's not really a hard limit, right? And is the "solving the halting problem" really a real problem? Isn't the problem on determining the columns of that matrix, rather than using it as a quantum operation? After all we could actually construct such a matrix for, eg, 8 byte Java programs, if there was a halting detection algorithm. Or is the purpose of the size restriction on operation matrices simply to prevent defining a matrix as a function? But there's a limit at the number of qubits in the system anyway, unlike a turing machine with unlimited tape…
• How can we possibly do interesting operations with only a single qubit? Couldn't we just multiply all the unitaries then do it classically? Or does "useful" mean "comparable to classical computers" rather than "faster than classical computers", since you can do matrix multiplication with a single qubit?