Title: Theory / Unimportant / CS / Fundamental / Quantum / Lipton - Regan
Tags: récupéré hasSeenConjDef mathToSee fromMath omitted

Name: A state of a quantum computation
Definition: A vector \(\mathbf a=\left[\begin{array}{l}a_0\\\dots\\a_{2^n-1}\end{array}\right]\) with \(|\sum{a_i}^2|=1\)
Page: 3
Chapter: 1
Section: 2
Intuition: An element of the sphere of radius 1 and dimension \(2^n\)

Name: An amplitude
Definition: some \(a_i\)
Page: 3
Chapter: 1
Section: 2
Variables: \(\mathbf a=\left[\begin{array}{l}a_0\\\dots\\a_{2^n-1}\end{array}\right]\) a state

Name: A basis state
Definition: 1 on the \(k\)-th value, 0 everywhere else
Page: 3
Chapter: 1
Section: 2
Notation: \(\mathbf e_k\)
Property: An element of the standard basis

Name: A superposition state
Definition: A non-basis state
Page: 3
Chapter: 1
Section: 2
Extra: entangled ?

Name: The probability to measure the system in state \(a_k\)
Definition: \(|a_k|^2\)
Page: 4
Chapter: 1
Section: 2
Variables: \(\mathbf a=\left[\begin{array}{l}a_0\\\dots\\a_{2^n-1}\end{array}\right]\) a state
Intuition: For \(N=1\) the state belongs to the circle of radius 1 in dimension \(2\). The probability is the projection of \(\sin\) or \(\cos\), squared

Name: A unitary operation
Definition: \(U^*U=I\)
Page: 5
Chapter: 3
Variables: \(N\in\mathbb N\)
Notation: \(\mathbf U\)
Index: 1
Kind: Def
Conjdef: A square matrix \(U\) such that, equivalently

Name: States
Page: 5
Section: 3
Chapter: 1
Variables: \(N\in\mathbb N\)
Under: unitary operations

Name: A quantum computation
Definition: Initial state: \(\mathbf e_0\)
Page: 5
Chapter: 1
Section: 3
Variables: \(n\in\mathbb N\)
Definition2: Step: applying an unitary matrix to the state
Conjdef: In this order
Definition4: end: making a measurement. Output being an index of \([0,2^n)\)

Question: How to compute the same problem for different values
Answer: Change the code to hard-code the distinct values
Page: 6
Chapter: 1
Section: 4
Variables: \(n\in\mathbb N\)

Name: The Boolean inner product of \(x\) and \(y\)
Definition: \(\bigoplus _{i=1}^nx_iy_i\)
Page: 10
Chapter: 2
Variables: \(n\in\mathbb N\),
\(x_1,y_1,\dots, x_n,y_n\) boolean values
Notation: \(x\bullet y\)

Question: Omitting
Answer: Standard notion of computer science and basic linear algebra
Page: 11
Chapter: 2
Section: 1

Definition: \(a_i\)
Page: 15
Chapter: 3
Section: 1
Variables: \(\mathbf a=\left[\begin{array}{l}a_0\\\dots\\a_{2^n-1}\end{array}\right]\) a state
Notation: \(\mathbf a(i)\)

Name: The Hilbert space of dimension \(n\)
Definition: A complex or real vector space with dimension \(N\), and Euclidean norm
Page: 16
Chapter: 3
Section: 1
Variables: \(n\in\mathbb N\)
Notation: \(\mathbb H_n\)

Name: The Cartesian product of \(\mathbb H_N\) and \(\mathbb H_{N'}\)
Definition: Elements are tuple with an element of \(\mathbb H_N\) and one of \(\mathbb H_{N'}\), operations defined pointwise
Page: 17
Chapter: 3
Section: 2
Variables: \(N,N'\in\mathbb N\)

Name: The tensor product of \(\mathbb H_{N_1}\) and \(\mathbb H_{N_2}\)
Definition: A vector space of dimension \(N_1N_2\)
Page: 17
Chapter: 3
Section: 2
Variables: \(N,N'\in\mathbb N\)
Notation: \(\mathbb H_{N_1}\otimes\mathbb H_{N_2}\)

Name: The tensor product of \(\mathbf a_1\) and \(\mathbf a_2\)
Definition: \((i,j)\mapsto \mathbf a_1(i)\mathbf a_2(j)\)
Page: 17
Chapter: 3
Section: 2
Variables: \(N_1,N_2\in\mathbb N\),
\(\mathbf a_i\in \mathbb H_{N_i}\)
Notation: \(\mathbf a_1\otimes \mathbf a_2\)

Name: A separable state
Definition: The tensor product of two other vectors
Page: 17
Chapter: 3
Section: 2
Variables: \(N_1,N_2\in\mathbb N\),
Context: \(\mathbb H_{N_1}\otimes \mathbb H_{N_2}\)

Name: An entangled state
Definition: A state which is not separable
Page: 17
Chapter: 3
Section: 2
Variables: \(N_1,N_2\in\mathbb N\),
Context: \(\mathbb H_{N_1}\otimes \mathbb H_{N_2}\)

Name: A permutation matrix
Definition: A matrix with exactly one 1 in each line/column, and 0 everywhere else
Page: 18
Chapter: 3
Section: 2
Variables: \(N_1\in\mathbb N\),

Name: The inner product of \(\mathbf a\) and \(\mathbf b\)
Definition: \(\sum_{k=0} ^m\overline{\mathbf a(k)}\mathbf b(k)\)
Page: 19
Chapter: 3
Section: 4
Variables: \(N\in\mathbb N\),
\(\mathbf {a,b}\in\mathbb H_N\)
Notation: \(\langle\mathbf{a,b}\rangle\)

Name: The inner product of \(\mathbf {U_1}\) and \(\mathbf {U_2}\)
Definition: The \(m_1m_2\times n_1n_2\)-matrix with entry \(((i_1,i_2),(j_1,j_2))\) being \(U_{1}(i_1,j_1)U_2(i_2,j_2)\)
Page: 19
Chapter: 3
Section: 4
Variables: \(\mathbf {U_i}\) matrices of dimension \(n_i\times m_i\)
Notation: \(\mathbf {U_1}\otimes \mathbf {U_2}\)

Q: Length of vectors is:
-[...] under [...]
A: preserved; product by unitary matrix
Page: 20
Chapter: 3
Section: 4

Name: The tensor product of \(U_1\) and \(U_2\)
Definition: The matrix of \(X^{\prod m_{1,i}\times \prod m_{2,i}}\) whose entries \(((n_{1,1},n_{1,2}),(n_{2,1},n_{2,2}))\) is \((\prod U^in_{i,1},\prod U^in_{i,2})\)
Page: 20
Chapter: 3
Section: 4
Variables: \(X\) a field
\(U^i\in X^{m_{1,i}\times m_{2,i}}\)
Notation: \(U_1\otimes U_2\)

Question: \((U_1\otimes U_2)(c)(i_1i_2)\)
Answer: equals \(\prod_j(U^ja)(i_j)\)
Page: 20
Chapter: 3
Section: 4
Variables: \(X\) a field
\(U^i\in X^{m_{1,i}\times m_{2,i}}\)
\(c\in X^{m_1m_2}\)

Question: Graphs
Answer: Omitted
Page: 20
Chapter: 3
Section: 5

Name: Stochastic matrix
Definition: A matrix where every row has non-negative numbers summing to 1
Page: 21
Chapter: 3
Section: 5

Name: Doubly stochastic matrix
Definition: A matrix where every row and column has non-negative numbers summing to 1
Page: 21
Chapter: 3
Section: 5

Name: Boolean function
Definition: Omitted
Page: 27
Chapter: 4
Section: 5

Name: A feasible Boolean function
Definition: A Boolean fuction whose circuit size is polynomial in the size of the input
Page: 30
Chapter: 5
Section: 1

Name: Controlled not
Definition: applies negate \(x_2\) if \(x_1=1\)
Page: 34
Chapter: 4
Section: 3
Definition2: returns \((x_1,x_1\oplus x_2)\)
Conjdef: The function on two bits \(x_1,x_2\), equivalently:
Abbreviation: CNOT
Extra: Matrix ?

Name: The quatum encoding of \(f\)
Definition: the function [$]\defFun{2^{n+1}}{2^{n+1}}{x_1,\dots,x_n,z}{x_1,\dots,x_n,z\oplus f(x_1,\dots,x_n)}[/$]
Page: 34
Chapter: 4
Section: 3
Variables: \(f:2^{n}\to 2\)
Denoted by: \(F\)

Name: Standard encoding scheme
Definition: sends \(j\in[0,\dots,n-1]\) to the \(n\)-th bit binary string that denotes \(j\) in binary notation
Page: 34
Chapter: 4
Section: 3
Variables: \(n\in\mathbb N\)

Question: \(F(x_1,\dots,x_n,F(x_1,\dots,x_n,z))\)
Answer: equals \(x_1,\dots,x_n,z\)
Page: 34
Chapter: 4
Section: 3
Variables: \(f:2^{n}\to 2\)
\(F\) its quantum encoding

Question: How to encode helper bit in quantum computing ?
Answer: Enter them in the output bits.
Page: 34
Chapter: 4
Section: 3
Variables: \(f:2^{n}\to 2\)
\(F\) its quantum encoding

Name: A qubit line
Definition: A row in the matrix of \(F\), with a 1 only in column \((x_1,\dots,x_j,f(x_1,\dots,x_n))\)
Page: 35
Chapter: 4
Section: 3
Variables: \(f:2^{n}\to 2\)
\(F\) its quantum encoding

Name: An ancilla qubit
Definition: A qubit used to help the computation
Page: 35
Chapter: 4
Section: 3
Variables: \(f:2^{n}\to 2\)
\(F\) its quantum encoding

Name: A quantum coordinate
Definition: A qubit, seen as an entry of the matrix of \(F\)
Page: 35
Chapter: 4
Section: 3
Variables: \(f:2^{n}\to 2\)
\(F\) its quantum encoding