Physics 449: Quantum computation. Encoding information (optional)

Quantum computation is the use of a quantum system to act as a computing device. The optional problem set two problem in which you showed that a quantum system can act as a perfect random number generator was a nice example:

Apply a Hadamard gate to a ground state $|0\rangle\rightarrow {1\over \sqrt{2}}(|0\rangle+|1\rangle)=|\psi\rangle$
and then apply a measurement operator, $\hat{N}=|0\rangle \langle 0|$ which produces $0,1$ randomly with equal probability, but do it for a $b$ -bit system

$\psi=\Big({1\over \sqrt{2}}(|0\rangle+|1\rangle)\Big)\otimes \Big({1\over \sqrt{2}}(|0\rangle+|1\rangle)\Big)\otimes \cdots \otimes \Big({1\over \sqrt{2}}(|0\rangle+|1\rangle)\Big)={1\over \sqrt{2^b}}\sum_x |x\rangle$

Here’s a nice number operator

$\hat{N}_b=\hat{N}\otimes 1\otimes 1\otimes\cdots\otimes 1+2\Big(1\otimes \hat{N}\otimes 1\otimes\cdots\otimes 1\Big)+\cdots+2^{b-1}\Big(1\otimes 1\otimes\cdots\otimes 1\otimes\hat{N}\Big)$

For a 4 bit system find the eigenvalues of $\hat{N}$ , and use Bell.jl to make 30,000 measurements of $\hat{N}$ on $\psi$ . Make a histogram of the results, and explain how this system of 4 qubits can be used as a 4 bit true random number generator.
In existing computer systems random numbers are generated by algorithms that do not produce true random numbers. For example we can create a list of pseudo random numbers with a congruential generator $x_{n+1}=(ax_n+c) \, mod \, m$
with $a=16807=7^5$ and $m=2^{31}-1$ ( $c=0$ is the Lehmer RNG). Such numbers are not truly random, but the outcomes of measurements on quantum systems are genuinely random.

The problem solution is as follows:

include("Bell.jl")
using .Bell
ψ=(HG*ψ₀)⊗(HG*ψ₀)⊗(HG*ψ₀)⊗(HG*ψ₀)
H1=ψ₀⊗ψ₀'
Nb=H1⊗u⊗u⊗u+2*u⊗H1⊗u⊗u+4*u⊗u⊗H1⊗u+8*u⊗u⊗u⊗H1
mymeasurements=[measurement(ψ,Nb)[1] for j in 1:30000
using FreqTable
mytable=freqtable(mymeasurements)
bar([j for j in 0:15],mytable ./30000)
savefig("QCprob-1.png")

Those possible 4-bit numbers $0,1,\cdots, 15$ are measurement outcomes of equal likelihood, but of course we are using a classical computer to simulate the behavior of a quantum measurement process.

Encoding information as bits
Classical bits are $b=0$ , $b=1$ , a quantum bit is a superposition

$|q\rangle=a|0\rangle+b|1\rangle$

only measurable things are $|a|$ and $|b|$ since $|q\rangle$ and $e^{i\phi}|q\rangle$ represent the same quantum state.
A quantum system with $n$ qubits contains the information of $2^n$ complex numbers, so modeling such a system with a classical computer will require storage of a vast amount of floating point data.
We typically create the qubits (superpositions) by applying gates such as a Hadamard gate, to a state that could be interpreted as a classical bit such as $|0\rangle, \quad |1\rangle$ . So we will want to transform data such as ords or numbers into bitstrings such as $0101110$ and in a quantum system with $7$ qubits we would want to use this object as an input. creating a state $|0101110\rangle$ that computational gates can be applied to.

So the first order of business is transforming words or numbers into bitstrings. This is done by coding.
Coding is about sending a discrete variable $x$ observed at point “A” to point “B” by a network using codes of $0,1$ signals. Let the message be composed of discrete values $x_1,x_2,x_3,x_4$ for example. These may represent letters like $x_1\sime M$ , $x_2\sim A$ and so forth, in some language. They are encoded by assigning them unambiguously to sequences of $0,1's$ in a reversible way

$x_1\rightarrow 00, \quad x_2\rightarrow 01, x_3\rightarrow 10, \quad x_4\rightarrow 11$

(all require two bits) or

$x_1\rightarrow 0, \quad x_2\rightarrow 10, x_3\rightarrow 110, \quad x_4\rightarrow 111$

(ine 1-bit, two 2-bit, one 3-bit) are both allowed, since no sequence can be made by taking a shorter one and adding more terms, that would lead to ambiguities.

$11001010010=110|0|10|10|0|10=x_3x_1x_2x_2x_1x_2$

For economy it is best to use codings that require a minimal number of bits: that depends of the character frequency of the language, In English, not all letters are used with the same frequency to compose words (see https://www3.nd.edu/~busiforc/handouts/cryptography/letterfrequencies.html), for example in a random word the probability that a given letter is an E is 0.111 but the probability that it is a Q is 0.0019. Suppose that in our four-letter language

$\wp(x_1)=1/2, \quad \wp(x_2)=1/4,\quad \wp(x_3)=1/8,\quad \wp(x_4)=1/8$

then any message using the first coding requires

$2\cdot\Big({1\over 2}+{1\over 4}+{1\over 8}+{1\over 8}\Big)=2$

bits per character on average, and the second coding

$1\cdot{1\over 2}+2\cdot{1\over 4}+3\cdot{1\over 8}+3\cdot{1\over 8}=1.75$

bits/character sent, and so is preferable.

For messages comprised of symbols $\{x_1,x_2,\cdots, x_n\}$ encoded as bit-strings of lengths $n_1,n_2,\cdots, n_n$ , valid encodings must obey

$\sum_{i=1}^n \Big({1\over 2}\Big)^{n_i}\le 1$

{\bf Proof}. Let $w_j$ equal the number of $n_i$ ‘s that are equal to $j$ (for the first case above $w_1=0$ , $w_2=4$ , $w_3=w_4=\cdots=0$ , and for the second case $w_1=1$ , $w_2=1$ , $w_3=2$ , $w_{j>3}=0$ ).

$\begin{array}{ll}w_1\le 2 & \mbox{since we only have bits $0,1$}\\ w_2\le 2^2-2w_1 & \mbox{can't tack a $0,1$ onto a length-$1$ code}\\ w_3\le 2^3-2^2w_1-2w_2& \mbox{can't tack $00,01,10,11$ onto a length-$1$}\\ & \mbox{or a $0,1$ onto a length-$2$ code}\\ \end{array}$

so in general

$w_n\le 2^n-2^{n-1}w_1-\dots -2w_{n-1}, \qquad \sum_{j=0}^{n-1} w_j 2^{n-j}\le 2^n, \qquad \sum_{j=0}^{n-1} w_j 2^{-j}\le 1,\quad\mbox{or}\quad \sum_j \Big({1\over 2}\Big)^{n_j}\le 1$

since the $w_j$ counts the number of $n$ ‘s equal to $j$ .
Noiseless coding theorem

$\sum_i n_i \wp(x_i)\ge -\sum_i \wp(x_i)\log_2 \wp(x_i)$

The right hand side is the Boltzmann entropy (equal to the information entropy or statistical surprise) of statistical physics.

Proof: Use the theorem with $q_i={2^{-n_i}\over Q}$

$\sum_i^n 2^{-n_i}=Q\le 1, \qquad \sum_iq_i=\sum_i{2^{-n_i}\over Q}=1$

(1) $\begin{eqnarray*}-\sum_i \wp(x_i)\log_2\wp(x_i)&\le& -\sum_i \wp(x_i)\log_2 q_i\nonumber\\ &=&-\sum_i \wp(x_i)\log_2(2^{-n_i}/Q)\nonumber\\ &=&\sum_i\wp(x_i) n_i +\sum_i \wp(x_i)\log_2 (Q)\nonumber\\ &=&\sum_i\wp(x_i) n_i +\Big(\sum_i \wp(x_i)\Big)\cdot\log_2 (Q)=\sum_i\wp(x_i) n_i +\log_2 (Q)\nonumber\\ &\le& \sum_i\wp(x_i) n_i \nonumber\end{eqnarray*}$

since

$\log_2 (Q)\le \log_2 1=0$

The right side is the length of a typical coded single character. The theorem defines a place for the entropy or surprise function $H(x)=-\sum_i \wp(x_i)\log_2 \wp(x_i)$ of probability theory and statistical physics in coding theory.

Source coding is a mapping from a sequence of symbols from an information source to a sequence of alphabet symbols (usually bits) such that the source symbols can be exactly recovered from the binary bits (lossless source coding) or recovered within some distortion (lossy source coding). This is the concept behind data compression.
Shannon’s coding theorem
$N$ independent and identically distributed random variables $x_i$ each with entropy

$H(X) =-\sum_i \wp(x_i) \log_2 \wp(x_i)$

can be compressed into more than $NH(X)$ bits with negligible risk of information loss, as $N\rightarrow\infty$ , but if they are compressed into fewer than $NH(X)$ bits it is virtually certain that information will be lost.

Quantum information
Consider $|0\rangle$ and ${1\over \sqrt{2}}(|0\rangle+|1\rangle)$ . Apply $|0\rangle\langle 0|$ to each, and in the first case we get $0$ , in the second we get $0$ half of the time. The $0$ measurement result reveals nothing about which state was measured, there is no way to reliably distinguish between these two states by this measurement.

In quantum error correction the data of a qubit is stored in a highly entangled multi-qubit state, protecting it against loss by noise or bad gates. Thermal interactions between the qubit quantum systems and the environment can cause a qubit to flip or change states, cosmic ray collisions can do the same, and a quantum computer will be highly susceptible to errors created by such processes. How can errors and data loss be detected and corrected in a system of qubits? Suppose that thermal interactions have a probability $\wp$ of flipping a qubit. We will soon study how $\wp$ depends on temperature $T$ .

Bit flip gates;

$\hat{U}=\left(\begin{array}{cc} 1 & 0 \\0 & 1\end{array}\right), \quad \wp=1-p, \qquad \hat{U}=\left(\begin{array}{cc} 0 & 1 \\1 & 0\end{array}\right), \quad \wp=p$

In what follows we will assume that at most one qubit is flipped and not describe detection/correction of multiple flips.
Construct the following four mutually compatible projection operators

$\hat{Q}_0=|000\rangle\langle000|+|111\rangle\langle111|, \quad \mbox{no flipped bits}$

and

$\hat{Q}_1=|100\rangle\langle100|+|011\rangle\langle011|,\quad \hat{Q}_2=|010\rangle\langle010|+|101\rangle\langle101|$

$\hat{Q}_3=|001\rangle\langle001|+|110\rangle\langle110|$

which detect flipped bits on first, second or third qubits. The operators project onto the bit-flipped state vectors. Let

$\hat{M}=1\hat{Q}_0+2\hat{Q}_1+3\hat{Q}_2+4\hat{Q}_3$

be an “error syndrome” operator, whose eigenstates are the original and single qubit-flipped stste-vectors. Note that if there are no qubits flipped

$|\psi\rangle=a|000\rangle+b|111\rangle, \qquad \hat{Q}_0|\psi\rangle=|\psi\rangle, \qquad \hat{Q}_{j\ne 0}|\psi\rangle=0, \qquad \hat{M}|\psi\rangle=|\psi\rangle$

and if the first qubit is flipped

$|\psi\rangle=a|100\rangle+b|011\rangle, \qquad \hat{Q}_1|\psi\rangle=|\psi\rangle, \qquad \hat{Q}_{j\ne 1}|\psi\rangle=0, \qquad \hat{M}|\psi\rangle=2|\psi\rangle$

so that depending on the measurement outcome for the error syndrome, we recover the state and can apply a suitable gate to reconstruct from it the original data (do nothing if the error syndrome is $1$ , apply a bit-flipping gate to qubit two if the error syndrome is $2$ , and so forth).

Home 2.0

Physics 449: Quantum computation. Encoding information (optional)

Related Posts

Physics 449: Quantum computation. Encoding information (optional)

Published by Jeff on February 12, 2022February 12, 2022

Related Posts

Protected: Physics 449-2023: Lecture 14 (Aufbau, Fine structure)

Protected: Thermal physics from entanglement

Protected: Physics 449: Reference material on error propagation