Title: Theory / Unimportant / CS / Fundamental / Complexity / Complexity Arora Barak/{ / Quantum
Tags: fromMath mathToDef mathToSee

Name: qubit
Definition: \(\alpha_0|0\rangle+\alpha_1|1\rangle\) with \(|\alpha_0|^2+|\alpha_1|^2=1\), \(\alpha_0,\alpha_1\in\mathbb C\).
Page: 204
Chapter: 10
Section: 1

Name: The amplitudes
Definition: The \(\alpha_i\)'s.
Page: 204
Chapter: 10
Section: 1
Variables: \(\alpha_0|0\rangle+\alpha_1|1\rangle\) a qbit.

Question: When it is observed, it is reavealed to be
Answer: \(|0\rangle\) with probability \(|\alpha_0|^2\) and \(|1\rangle\) with probability \(|\alpha_1|^2\).
Page: 204
Chapter: 10
Section: 1
Variables: \(\alpha_0|0\rangle+\alpha_1|1\rangle\) a qbit.

Q: [...] is also written [...].
A: \(|xy\rangle\); \(|x\rangle|y\rangle\)
Page: 205
Chapter: 10
Section: 1

Question: If \(|\alpha_0|^2+|\alpha_1|^2\) is neither 0 nor 1, it represents
Answer: \(\frac{\alpha_0|0\rangle+\alpha_1|1\rangle}{|\alpha_0|^2+|\alpha_1|^2}\).
Page: 206
Chapter: 207
Section: 2
Variables: \(\alpha_0|0\rangle+\alpha_1|1\rangle\) a qbit.

Name: Uniform quantum state
Definition: \(\sum_{w\in\{0,1\}^n}|w\rangle\).
Page: 206
Chapter: 207
Section: 2
Variables: \(n\in\mathbb N\)

Question: The only quantum transformation are
Answer: unitary operations.
Page: 206
Chapter: 207
Section: 2
Variables: \(n\in\mathbb N\)

Name: EPR paradox
Definition: Game: Alice and Bob receive a random bit. If both bits are 1, they must answer different bit, otherwise the same bit. Best probability of winning is \(0.75\) without information, and at least \(.8\) with a pair of entangled qbit.
Page: 207
Section: 2

Name: Quantum register
Definition: \(m\) qbits.
Page: 209
Chapter: 3
Section: 3.2
Variables: \(m\in\mathbb N\).

Question: The state of a quantum register is
Answer: a superposition of all \(2^m\) basic states.
Page: 209
Chapter: 3
Section: 3.2
Variables: \(m\in\mathbb N\).

Question: A basic state of a quantum register is
Answer: a word in \(\{0,1\}^m\).
Page: 209
Chapter: 3
Section: 3.2
Variables: \(m\in\mathbb N\).

Page: 211
Chapter: 3
Section: 3.4
Name: Quantum operations
-Flipping a qbit: Inversing \(|0\rangle\) and \(|1\rangle\).
-Reordering qbit: exchanging the value of 2 basic states.
-controlling not: Flipping the second coponent when the first is \(1\).
-Rotation on a single bit; \(|0\rangle\mapsto \cos\theta|0\rangle+\sin\theta|1\rangle\) and \(|1>\mapsto s\sin\theta|0\rangle+\cos\theta|1\rangle\).
-Reversible AND: \(|b_1\rangle|b_2\rangle|b_3\rangle\mapsto|b_1\rangle|b_2\rangle|b_3\oplus(b_1\land b_2)\rangle\)
-Hadamard operation: \(|0\rangle\mapsto|0\rangle+|1\rangle\) and \(|1\rangle\mapsto|0\rangle-|1\rangle\)