Title: Theory / Unimportant / CS / Fundamental / Quantum / Comp. & Inf.
Tags: fromAlgorithm hasNotNewEffectReturnsMeaning fromImplementation oldAlgoNewName fromImplication hasSeenConjDef some_instruction

Question: All vector spaces are assumed to be
Answer: finite dimensional
Page: xxix
Chapter: Nomenclature and notation

Name: A positive definite operator
Definition: An operator \(A\) such that [$]\expval{A}{\psi}>0[/$] for all [$]\ket{\psi}\ne0[/$].
Page: xxix
Chapter: Nomenclature and notation

Name: The support of \(A\)
Definition: The vector space orthogonal to the kernel of \(A\).
Page: xxix
Chapter: Nomenclature and notation
Variables: \(A\) an operator

Name: A unitary operator/matrix
Definition: An operator/matrix \(M\) such that [$]M^\dag M=I[/$]
Page: xxix, 21
Chapter: Nomenclature and notation, 1
Section: , 3.2
Denoted by: \(U\), \(V\)

Name: The Hadamard gate
Definition: \(\frac1{\sqrt2}\left[\begin{array}{ll}1&1\\1&-1\end{array}\right]\).
Page: xxix, xxx, 19
Chapter: Nomenclature and notation, 1
Section: 3.1
Context: Quantum computing
Notation: \(H\)
Definition2: [$]\alpha_0\ket0+\alpha_1\ket1\mapsto\alpha_0\frac{\ket 0+\ket 1}{\sqrt2}+\alpha_1\frac{\ket0-\ket1}{\sqrt2}=\frac{\alpha_0+\alpha_1}{\sqrt 2}\ket0+\frac{\alpha_0-\alpha_1}{\sqrt2}\ket1[/$].
Name2: Square root of NOT
Intuition: On the Bloch sphere, it consists of a 90° rotation about \(\hat y\) followed by a rotation about the \(\hat x\) axis by 180°

Definition: The vector \((1,0)\)
Page: xxix
Chapter: Nomenclature and notation
Notation: [$]\ket0[/$]

Definition: The vector \((0,1)\).
Page: xxix
Chapter: Nomenclature and notation
Notation: [$]\ket1[/$]

Name: The Pauli-\(Z\) sigma matrix
Definition: \(\left[\begin{array}{ll}1&0\\0&-1\end{array}\right]\),
[$]\alpha_0\ket0+\alpha_1\ket1\mapsto\alpha_0\ket 0-\alpha_1\ket1[/$]
Page: xxix, xxx, 19
Chapter: Nomenclature and notation, 1
Section: , 3.1
Notation: \(\sigma_z\)
Notation2: \(\sigma_3\)

Definition: The \(2\times 2\) identity matrix
Page: xxx
Chapter: Nomenclature and notation
Notation: \(\sigma_0\)
Notation2: \(I\) matrix

Question: Logarithms' base is
Answer: 2
Page: xxx
Chapter: Nomenclature and notation

Name: A probability distribution
Definition: A finite set of non-negative real numbers, \(p_k\) whose sum is 1
Page: xxx
Chapter: Nomenclature and notation

Name: The relative entropy of \(A\) relative to \(B\)
Definition: \(\text{tr}(A\log A)-\text{tr}(A\log B)\)
Page: xxx
Chapter: Nomenclature and notation
Variables: \(A,B\) positive operators
Notation: \(S(A||B)\)

Definition: Modulo two addition
Page: xxx
Chapter: Nomenclature and notation
Context: Arithmetic
Notation: \(\oplus\)

Name: The Pauli-\(Y\) sigma matrix
Definition: \(\left[\begin{array}{ll}0&-i\\i&0\end{array}\right]\)
[$]\ket0\mapsto i\ket 1[/$], [$]\ket1\mapsto-i\ket 0[/$]
Page: xxx
Chapter: Nomenclature and notation
Notation: \(\sigma_y\)
Notation2: \(\sigma_2\)

Name: The Pauli-\(X\) sigma matrix
Definition: \(\left[\begin{array}{ll}0&1\\1&0\end{array}\right]\)
[$]\alpha_0\ket0+\alpha_1\ket1\mapsto\alpha_1\ket0+\alpha_0\ket 1[/$]
Page: xxx, 18
Chapter: Nomenclature and notation, 1
Section: , 3.1
Context: Quantum computing
Notation: \(\sigma_x\)
Name2: The not gate
Extra: swap ?
Notation2: \(\sigma_1\)

Name: Phase
Definition: \(\left[\begin{array}{ll}1&0\\0&i\end{array}\right]\)
[$]\ket0\mapsto\ket 0[/$], [$]\ket1\mapsto i\ket 1[/$]
Page: xxx
Chapter: Nomenclature and notation
Notation: \(S\)

Definition: \(\left[\begin{array}{ll}1&0\\0&e^{i\pi/4}\end{array}\right]\)
[$]\ket0\mapsto\ket 0[/$], [$]\ket1\mapsto e^{i\pi/4}\ket 1[/$]
Page: xxx
Chapter: Nomenclature and notation
Notation: \(T\)
Notation2: \(\pi/8\)

Smaller0: phase gate
Greater0: \(\pi/8\)
Page: xxx
Chapter: Nomenclature and notation
Smaller to greater: is the square of
Greater to smaller: is the square root of
Smallest: Pauli-\(Z\) gate

Question: The order of vectors in a matrix is
Answer: increasing order, according to the usual binary representation of integers
Page: xxx
Chapter: Nomenclature and notation
Context: Quantum computing

Name: Controlled-NOT
Definition: \(\left[\begin{array}{llll}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{array}\right]\)
Page: xxxi
Chapter: Nomenclature and notation

Name: Swap
Definition: \(\left[\begin{array}{llll} 1&0&0&0\\0&0&1&0\\0&1&0&0\\0&0&0&1\end{array}\right]\)
[$]\sum_{i,j\in\{0,1\} } \alpha_{i,j}\ket{ij}\mapsto\sum_{i,j\in\{0,1\} } \alpha_{i,j}\ket{ji}[/$]
Page: xxxi
Chapter: Nomenclature and notation

Name: Toffoli
Definition: [$]\begin{array}{llllllll}
1&0&0&0&0&0&0&0\\
0&1&0&0&0&0&0&0\\
0&0&1&0&0&0&0&0\\
0&0&0&1&0&0&0&0\\
0&0&0&0&1&0&0&0\\
0&0&0&0&0&1&0&0\\
0&0&0&0&0&0&0&1\\
0&0&0&0&0&0&1&0\\
\end{array}
[/$]
Page: xxxi
Chapter: Nomenclature and notation
Intuition: A controlled controlled-not

Name: Fredkin
Definition: \(\left[\begin{array}{lllllllll} 1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\end{array}\right]\)
Page: xxxi
Chapter: Nomenclature and notation
Context: Quantum computing
Name2: Controlled-swap

Name: Measurement
Definition: Projection onto [$]\ket 0[/$] and [$]\ket 1[/$].
Page: xxxi
Chapter: Nomenclature and notation

Name: qubit
Definition: Wire carrying a single qubit (times goes left to right)
Page: xxxi
Chapter: Nomenclature and notation
Context: Quantum computing

Name: classical bit
Definition: Wire carrying a single bit
Page: xxxi
Chapter: Nomenclature and notation

Name: \(n\) qubits
Definition: Wire carrying \(n\) qubits
Page: xxxi
Chapter: Nomenclature and notation

Name: Dirac notation
Page: 13
Chapter: 1
Section: 2
Notation: [$]\ket{}[/$]

Name: A qubit
Definition: An element of the form [$]\alpha_0\ket0+\alpha_1\ket1[/$], with \(\alpha_i\in\mathbb C\) and \(\sum|\alpha_i|^2=1\)
Page: 13
Chapter: 1
Section: 2
Denoted by: [$]\ket\phi[/$]

Name: The computational basis states
Definition: [$]\ket 0[/$] and [$]\ket 1[/$]
Page: 13
Chapter: 1
Section: 2

Name: Its measurement along the computational basis state
Definition: [$]\ket i[/$] with probability \(|\alpha_i|^2\)
Page: 13
Chapter: 1
Section: 2
Variables: [$]\alpha_0\ket0+\alpha_1\ket1[/$] a qubit

Definition: [$]\frac{\ket0+\ket1}{\sqrt2}[/$]
Page: 14
Chapter: 1
Section: 2
Notation: [$]\ket+[/$]

Name: Ground state
Page: 14
Chapter: 1
Section: 2
Notation: The state [$]\ket0[/$]

Name: Excited state
Page: 14
Chapter: 1
Section: 2
Notation: The state [$]\ket1[/$]

Name: The Block sphere picture
Definition: The sphere of points of the form [$]\cos\frac\theta2\ket0+e^{i\phi}\sin\frac\theta2\ket1[/$].
Page: 15
Chapter: 1
Section: 2

Name: An amplitude
Definition: A complex coefficient by which an element of the base is multiplied
Page: 16
Chapter: 1
Section: 2.1

Name: The set of strings of length \(n\) with each letter being either zero or one
Page: 16
Chapter: 1
Section: 2.1
Variables: \(n\in\mathbb N\)
Notation: \(\{0,1\}^n\)

Name: The normalization condition
Definition: Stating that, if [$]\sum_{x\in\{0,1\}^n}\alpha_x\ket x[/$] is \(n\)-quantum bit, then \(\sum_{x\in\{0,1\}^n}|\alpha_x|^2=1\)
Page: 16
Chapter: 1
Section: 2.1
Variables: \(n\in\mathbb N\)
Context: Quantum theory

Name: The measurement along the first component
Definition: It gives \(i\in\{0,1\}\) with probability \(\sum_{x\in\{0,1\}^{n-1} }|\alpha_{ix}^2|\), leaving the post-measurement state [$]\frac{\sum_{x\in\{0,1\}^{n-1} }\alpha_{ix}\ket{ix}}{\sqrt{\sum_{x\in\{0,1\}^{n-1}}|\alpha_{ix}|^2}}[/$].
Page: 16
Chapter: 1
Section: 2.1
Variables: \(n\in\mathbb N\),
\(\alpha_{x}\) for \(x\in\{0,1\}^n\) a normalized sequence of numbers

Name: A Bell state
Definition: [$]\frac{\ket{0j}+(-1)^i\ket{1\overline j}}{\sqrt2}[/$]
Page: 16, 26
Chapter: 1, 1
Section: 2.1, 3.3
Notation: [$]\ket{\beta_{ij}}[/$]
Name2: An EPR pair

Name: \(n\) qubits
Definition: An element of the form [$]\sum_{x\in\{0,1\}^n}\alpha_x\ket x[/$] where the \(\alpha_x\) satisfies the normalization condition.
Page: 16
Chapter: 1
Section: 2.1
Variables: \(n\in\mathbb N\)

Name: The complexe conjugate of \(A\)
Definition: The matrix obtain by applying complex conjugate to each element of \(A\).
Page: 18
Chapter: 1
Section: 3.1
Variables: \(n\in\mathbb N\)Let \(A\) a matrix of dimension \(n\times n\)

Name: The adjoint of \(A\)
Definition: The complex conjugate of the transpose of \(A\)
Page: 18
Chapter: 1
Section: 3.1
Variables: \(n\in\mathbb N\)Let \(A\) a matrix of dimension \(n\times n\)
Notation: [$]A^\dagger[/$]

Name: An unitary operator
Definition: An operator \(A\) such that [$]A^\dagger A=I[/$].
Page: 18
Chapter: 1
Section: 3.1

Question: \(H^2\) is
Answer: \(I\)
Page: 19
Chapter: 1
Section: 3.1

Name: A universal set
Definition: A set of operators such that any operator can be arbitrary approximated by composing operators from this set
Page: 20
Chapter: 1
Section: 3.1

Name: The control bit of \(G\)
Definition: The first bit
Page: 20
Chapter: 1
Section: 3.2
Variables: \(G\) a controlled gate

Name: The target bit(s)
Definition: The non-control bit(s)
Page: 20
Chapter: 1
Section: 3.2
Variables: \(G\) a controlled gate

Definition: [$](\ket0-\ket1)\sqrt2[/$]
Page: 22
Chapter: 1
Section: 3.3
Notation: [$]\ket-[/$]

Question: A quantum computation starts
Answer: usually in the state consisting of all [$]\ket 0[/$]s
Page: 23
Chapter: 1
Section: 3.3

Name: Controlled \(U\)
Definition: The operator sending [$]\ket 0 v_0+\ket1v_1 [/$] to [$]\ket 0 v_0+\ket1(Uv_1) [/$]
Page: 23
Chapter: 1
Section: 3.3
Variables: \(U\) an unitary matrix on \(n\) bits

Name: The no cloning theorem
Definition: It is impossible to copy an arbitrary qubit
Page: 25
Chapter: 1
Section: 3.3

Question: The square of the Toffoli gate is
Answer: identity
Page: 29
Chapter: 1
Section: 4.1

Page: 30
Section: 4.1
Chapter: 1
Effect: Classical nand
Variables: \(a,b\) bits
Context: Quantum computing

Page: 30
Section: 4.1
Chapter: 1
Effect: Classical copy
Variables: \(a\) a bit

Page: 30
Implementation: [$]\ket 0 H[/$] measured along the standard base
Section: 4.1
Chapter: 1
Effect: Classical random bit
Variables: \(a,b\) bits

Question: How to compute a function \(f\) using quantum computer ?
Answer: computes \(U_f\)
Page: 31
Chapter: 1
Section: 4.1

Definition: [$]\ket{x,y}\mapsto\ket{x,y\oplus f(x)}[/$]
Page: 31
Chapter: 1
Section: 4.1
Variables: \(f\) a function \(\{0,1\}^n\to \{0,1\}^n\)
Notation: \(U_f\)

Name: The data register of \(U_f(x,y)=(x,y\oplus f(x))\)
Definition: The register \(x\)
Page: 31
Chapter: 1
Section: 4.1
Variables: \(f\) a function \(\{0,1\}^n\to \{0,1\}^n\)

Name: The target register of \(U_f(x,y)=(x,y\oplus f(x))\)
Definition: The register \(y\)
Page: 31
Chapter: 1
Section: 4.1
Variables: \(f\) a function \(\{0,1\}^n\to \{0,1\}^n\),

Name: Quantum parallelism
Definition: The fact that, applying \(U_f\) to the Bell qubit and [$]\ket 0[/$], one obtain [$]\frac{\ket{0,f(0)}+\ket{1,f(1)} }{\sqrt2}[/$]
Page: 31
Chapter: 1
Section: 4.1

Name: The Hadamard transform
Definition: \(n\) Hadamard gates acting in parallel on \(n\) qubits
Page: 31
Chapter: 1
Section: 4.1
Variables: \(n\in\mathbb N\)
Notation: \(H^{\otimes n}\)
Name2: The Walsh-Hadamard transform

Question: [$]H^{\otimes n}\ket{0}[/$]
Answer: equals [$]\frac{\sum_x\ket x}{\sqrt{2^n}}[/$]
Page: 31
Chapter: 1
Section: 4.1
Variables: \(n\in\mathbb N\)

Page: 33
Section: 4.1
Chapter: 1
Name: Deutsch algorithm
Returns: Whether \(f\) is constant, or balanced.
First qbit is 0 if it is balanced, else nonzero.

Page: 34, 35
Implementation: and measure the query register.
Section: 4.4
Chapter: 1
Variables: \(f:\{0,1\}^2\to\{0,1\}\)
Name: Deutsch-Josza algorithm
Returns: Check whether \(f\) takes one or two values
First bit is 0 if \(f\) is constant, and nonzero if balanced.
Assuming: \(f\) is balanced or constant.

Page: 33
Implementation: [$]U_f\left(\frac{\ket{x}(\ket0-\ket1)}{\sqrt2}\right)[/$]
Section: 4.4
Chapter: 1
Effect: [$](-1)^{f(x)}\frac{\ket{x}(\ket0-\ket1)}{\sqrt2}[/$]
Variables: \(f:\{0,1\}^n\to\{0,1\}\) either constant or balanced,
\(x\in\{0,1\}^n\)

Name: Kronecker delta
Definition: \(1\) if \(i=j\), \(0\) otherwise
Page: https://en.wikipedia.org/wiki/Kronecker_delta
Notation: \(\delta_{ij}\)

Name: The Pauly-\(a\) matrix
Definition: \( \begin{pmatrix} \delta_{a3} & \delta_{a1} - i\delta_{a2}\\ \delta_{a1} + i\delta_{a2} & -\delta_{a3} \end{pmatrix}\)
Page: https://en.wikipedia.org/wiki/Kronecker_delta
Variables: \(a\in\{1,2,3\}\)
Notation: \(\sigma_a\)

Page: 27
Section: 3.3
Chapter: 1
Effect: Giving to the last bit the state of the first one
Name: Quantum teleportation

Name: A balanced function
Definition: A function \(\{0,1\}^n\to\{0,1\}\) such that the values are 0 and 1 \(2^{n-1}\) times
Page: 34
Chapter: 1
Section: 4.4

Question: [$]H\ket0[/$]
Answer: =[$]\ket+[/$]
Page: 22
Chapter: 1
Section: 3.3
Extra: Not in the book directly, but useful

Question: [$]H\ket1[/$]
Answer: =[$]\ket-[/$]
Page: 22
Chapter: 1
Section: 3.3

Question: [$]H\ket+[/$]
Answer: [$]=\ket0[/$]
Page: 22
Chapter: 1
Section: 3.3

Question: [$]H\ket-[/$]
Answer: [$]=\ket1[/$]
Page: 22
Chapter: 1
Section: 3.3

Question: The square of the Hadamard gate is
Answer: the identity
Page: xxx
Chapter: Nomenclature and notation

Name: Quantum state tomography
Definition: Given a quantum state, figure out how to describe it.
Page: 47
Chapter: 1
Section: 5.2

Name: Quantum process tomography
Definition: completely characterize the dynamics of a quantum system.
Page: 47
Chapter: 1
Section: 5.2

Name: Quantum information theory
Definition: study of elementary quantum information processing tasks
Page: 51
Chapter: 1
Section: 6

Name: An information source
Definition: A finite set of probabilities
Page: 52
Chapter: 1
Section: 6.1
Denoted by: \(p_1,\dots, p_d\)

Name: Shannon entropy of \(p\)
Definition: \(-\sum_{j}p_j\log (p_j)\)
Page: 52
Chapter: 1
Section: 6.1
Variables: \(p=(p_1,\dots, p_d)\) an information source
Notation: \(H(p)\)

Name: A quantum information source
Definition: A probability distribution over a finite set of quantum states
Page: 5^4
Chapter: 1
Section: 6.1
Denoted by: \(\psi_j\) and \(p_j\)

Question: What is the heart of quantum computation and information ?
Answer: The indistinguishability of non-orthogonal quantum states.
Page: 56
Chapter: 1
Section: 6.1

Name: Linear algebra
Definition: The study of vector spaces and of linear operations on those vector spaces.
Page: 61
Chapter: 2
Section: 1

Page: 33
Section: 4.1
Chapter: 1
Name: Deutsch algorithm
Returns: For \(f:\{0,1\}\to\{0,1\}\), an algorithm stating whether \(f(0)=f(1)\) using a single execution of \(f\)