From 45af77f068aaa57c052cd861412d53beecbe5e3b Mon Sep 17 00:00:00 2001 From: Prefetch Date: Fri, 9 Apr 2021 20:44:44 +0200 Subject: Expand knowledge base --- content/know/concept/cavitation/index.pdc | 119 +++++++++++++++++++++ .../concept/rayleigh-plesset-equation/index.pdc | 110 +++++++++++++++++++ content/know/concept/toffoli-gate/and.png | Bin 0 -> 7765 bytes content/know/concept/toffoli-gate/index.pdc | 93 ++++++++++++++++ content/know/concept/toffoli-gate/nand.png | Bin 0 -> 8119 bytes content/know/concept/toffoli-gate/not.png | Bin 0 -> 6051 bytes content/know/concept/toffoli-gate/or.png | Bin 0 -> 18615 bytes content/know/concept/toffoli-gate/toffoli.png | Bin 0 -> 3979 bytes content/know/concept/toffoli-gate/xor.png | Bin 0 -> 7708 bytes .../know/concept/von-neumann-extractor/index.pdc | 85 +++++++++++++++ 10 files changed, 407 insertions(+) create mode 100644 content/know/concept/cavitation/index.pdc create mode 100644 content/know/concept/rayleigh-plesset-equation/index.pdc create mode 100644 content/know/concept/toffoli-gate/and.png create mode 100644 content/know/concept/toffoli-gate/index.pdc create mode 100644 content/know/concept/toffoli-gate/nand.png create mode 100644 content/know/concept/toffoli-gate/not.png create mode 100644 content/know/concept/toffoli-gate/or.png create mode 100644 content/know/concept/toffoli-gate/toffoli.png create mode 100644 content/know/concept/toffoli-gate/xor.png create mode 100644 content/know/concept/von-neumann-extractor/index.pdc (limited to 'content/know') diff --git a/content/know/concept/cavitation/index.pdc b/content/know/concept/cavitation/index.pdc new file mode 100644 index 0000000..8f6b0c4 --- /dev/null +++ b/content/know/concept/cavitation/index.pdc @@ -0,0 +1,119 @@ +--- +title: "Cavitation" +firstLetter: "C" +publishDate: 2021-04-09 +categories: +- Physics +- Fluid mechanics +- Fluid dynamics + +date: 2021-04-06T19:03:36+02:00 +draft: false +markup: pandoc +--- + +# Cavitation + +In a liquid, **cavitation** is the spontaneous appearance of bubbles, +occurring when the pressure in a part of the liquid drops +below its vapour pressure, e.g. due to the fast movements. +When such a bubble is subjected to a higher pressure +by the surrounding liquid, it quickly implodes. + +To model this case, we use the simple form of +the [Rayleigh-Plesset equation](/know/concept/rayleigh-plesset-equation/) +for an inviscid liquid without surface tension. +Note that the RP equation assumes incompressibility. + +We assume that the whole liquid is at a constant pressure $p_\infty$, +and the bubble is empty, such that the interface pressure $P = 0$, +meaning $\Delta p = - p_\infty$. +At first, the radius is stationary $R'(0) = 0$, +and given by a constant $R(0) = a$. +The simple Rayleigh-Plesset equation is then: + +$$\begin{aligned} + R \dv[2]{R}{t} + \frac{3}{2} \bigg( \dv{R}{t} \bigg)^2 + = - \frac{p_\infty}{\rho} +\end{aligned}$$ + +To solve it, we multiply both sides by $R^2 R'$ +and rewrite it in the following way: + +$$\begin{aligned} + - 2 \frac{p_\infty}{\rho} R^2 R' + &= 2 R^3 R' R'' + 3 R^2 (R')^3 + \\ + - \frac{2 p_\infty}{3 \rho} \dv{t} \Big( R^3 \Big) + &= \dv{t} \Big( R^3 (R')^2 \Big) +\end{aligned}$$ + +It is then straightforward to integrate both sides +with respect to time $\tau$, from $0$ to $t$: + +$$\begin{aligned} + - \frac{2 p_\infty}{3 \rho} \int_0^t \dv{\tau} \Big( R^3 \Big) \dd{\tau} + &= \int_0^t \dv{\tau} \Big( R^3 (R')^2 \Big) \dd{\tau} + \\ + - \frac{2 p_\infty}{3 \rho} \Big[ R^3 \Big]_0^t + &= \Big[ R^3 (R')^2 \Big]_0^t + \\ + - \frac{2 p_\infty}{3 \rho} \Big( R^3(t) - a^3 \Big) + &= \Big( R^3(t) \: \big(R'(t)\big)^2 \Big) +\end{aligned}$$ + +Rearranging this equation yields the following expression +for the derivative $R'$: + +$$\begin{aligned} + (R')^2 + = \frac{2 p_\infty}{3 \rho} \Big( \frac{a^3}{R^3} - 1 \Big) +\end{aligned}$$ + +This equation is nasty to integrate. +The trick is to invert $R(t)$ into $t(R)$, +and, because we are only interested in collapse, +we just need to consider the case $R' < 0$. +The time of a given radius $R$ is then as follows, +where we are using slightly sloppy notation: + +$$\begin{aligned} + t + = \int_0^t \dd{\tau} + = - \int_{a}^{R} \frac{\dd{R}}{R'} + = \int_{R}^{a} \frac{\dd{R}}{R'} +\end{aligned}$$ + +The minus comes from the constraint that $R' < 0$, but $t \ge 0$. +We insert the expression for $R'$: + +$$\begin{aligned} + t + = \sqrt{\frac{3 \rho}{2 p_\infty}} \int_{R}^{a} \Bigg( \sqrt{ \frac{a^3}{R^3} - 1 } \Bigg)^{-1} \dd{R} + = \sqrt{\frac{3 \rho a^2}{2 p_\infty}} \int_{R/a}^{1} \frac{1}{\sqrt{x^{-3} - 1}} \dd{x} +\end{aligned}$$ + +This integral needs to be looked up, +and involves the hypergeometric function ${}_2 F_1$. +However, we only care about *collapse*, which is when $R = 0$. +The time $t_0$ at which this occurs is: + +$$\begin{aligned} + t_0 + = \sqrt{\frac{3 \rho a^2}{2 p_\infty}} \sqrt{\frac{3 \pi}{2}} \frac{\Gamma(5/6)}{\Gamma(1/3)} + \approx \sqrt{\frac{3 \rho a^2}{2 p_\infty}} 0.915 \:\mathrm{s} +\end{aligned}$$ + +With our assumptions, a bubble will always collapse. +However, unsurprisingly, reality turns out to be more complicated: +as $R \to 0$, the interface velocity $R' \to \infty$. +By looking at the derivation of the Rayleigh-Plesset equation, +it can be shown that the pressure just outside the bubble diverges due to $R'$. +This drastically changes the liquid's properties, and breaks our assumptions. + + + +## References +1. B. Lautrup, + *Physics of continuous matter: exotic and everyday phenomena in the macroscopic world*, 2nd edition, + CRC Press. diff --git a/content/know/concept/rayleigh-plesset-equation/index.pdc b/content/know/concept/rayleigh-plesset-equation/index.pdc new file mode 100644 index 0000000..ee8622b --- /dev/null +++ b/content/know/concept/rayleigh-plesset-equation/index.pdc @@ -0,0 +1,110 @@ +--- +title: "Rayleigh-Plesset equation" +firstLetter: "R" +publishDate: 2021-04-06 +categories: +- Physics +- Fluid mechanics +- Fluid dynamics + +date: 2021-04-06T19:03:36+02:00 +draft: false +markup: pandoc +--- + +# Rayleigh-Plesset equation + +In fluid dynamics, the **Rayleigh-Plesset equation** +describes how the radius of a spherical bubble evolves in time +inside an incompressible liquid. +Notably, it leads to [cavitation](/know/concept/cavitation/). + + +## Simple form + +The simplest version of the Rayleigh-Plesset equation is found +in the limiting case of a liquid with zero viscosity zero surface tension. + +Consider one of the [Euler equations](/know/concept/euler-equations/) +for the velocity field $\va{v}$, +where $\rho$ is the (constant) density: + +$$\begin{aligned} + \frac{\mathrm{D} \va{v}}{\mathrm{D} t} + = \pdv{\va{v}}{t} + (\va{v} \cdot \nabla) \va{v} + = - \frac{\nabla p}{\rho} +\end{aligned}$$ + +We make the ansatz $\va{v} = v(r, t) \vu{e}_r$, +where $\vu{e}_r$ is the basis vector; +in other words, we demand that the only spatial variation of the flow is in $r$. +The above Euler equation then becomes: + +$$\begin{aligned} + \pdv{v}{t} + v \pdv{v}{r} + = - \frac{1}{\rho} \pdv{p}{r} +\end{aligned}$$ + +Meanwhile, the incompressibility condition +is as follows in this situation: + +$$\begin{aligned} + \nabla \cdot \va{v} + = \frac{1}{r^2} \pdv{(r^2 v)}{r} + = 0 +\end{aligned}$$ + +This is only satisfied if $r^2 v$ is constant with respect to $r$, +leading us to a solution $v(r)$ given by: + +$$\begin{aligned} + v(r) + = \frac{C(t)}{r^2} +\end{aligned}$$ + +Where $C(t)$ is an unknown function that does not depend on $r$. +We then insert this result in the earlier Euler equation, +and isolate it for $\pdv*{p}{r}$, yielding: + +$$\begin{aligned} + \pdv{p}{r} + = - \rho \bigg( \pdv{v}{t} + v \pdv{v}{r} \bigg) + = - \rho \bigg( \frac{1}{r^2} C' - \frac{2}{r^5} C^2 \bigg) +\end{aligned}$$ + +Integrating this with respect to $r$ yields the following expression for $p$, +where $p_\infty$ is the (possibly time-dependent) pressure at $r = \infty$: + +$$\begin{aligned} + p(r, t) + = p_\infty(t) + \rho \bigg( \frac{1}{r} C'(t) - \frac{1}{2 r^4} C^2(t) \bigg) +\end{aligned}$$ + +We now consider a spherical bubble with radius $R(t)$ and pressure $P(t)$ along the liquid surface. +To study the liquid boundary's movement, we set $r = R$ and $p = P$, +and see that $R'(t) = v(t)$, such that $C = r^2 V = R^2 R'$. +We thus arrive at: + +$$\begin{aligned} + P + &= p_\infty + \rho \bigg( \frac{1}{R} \dv{(R^2 R')}{t} - \frac{1}{2 R^4} (R^2 R')^2 \bigg) + \\ + &= p_\infty + \rho \bigg( 2 (R')^2 + R R'' - \frac{1}{2} (R')^2 \bigg) +\end{aligned}$$ + +Rearranging this and defining $\Delta p = P - p_\infty$ +leads to the simple Rayleigh-Plesset equation: + +$$\begin{aligned} + \boxed{ + R \dv[2]{R}{t} + \frac{3}{2} \bigg( \dv{R}{t} \bigg)^2 + = \frac{\Delta p}{\rho} + } +\end{aligned}$$ + + + +## References +1. B. Lautrup, + *Physics of continuous matter: exotic and everyday phenomena in the macroscopic world*, 2nd edition, + CRC Press. diff --git a/content/know/concept/toffoli-gate/and.png b/content/know/concept/toffoli-gate/and.png new file mode 100644 index 0000000..c406fda Binary files /dev/null and b/content/know/concept/toffoli-gate/and.png differ diff --git a/content/know/concept/toffoli-gate/index.pdc b/content/know/concept/toffoli-gate/index.pdc new file mode 100644 index 0000000..84e7656 --- /dev/null +++ b/content/know/concept/toffoli-gate/index.pdc @@ -0,0 +1,93 @@ +--- +title: "Toffoli gate" +firstLetter: "T" +publishDate: 2021-04-09 +categories: +- Quantum information + +date: 2021-04-09T14:44:43+02:00 +draft: false +markup: pandoc +--- + +# Toffoli gate + +The **Toffoli gate** or **controlled-controlled-NOT (CCNOT) gate** +is a logic gate that is *reversible* (no information is lost) +and *universal* (all reversible logic circuits can be built using Toffoli gates). + +It takes three input bits $A$, $B$ and $C$, +of which it returns $A$ and $B$ unchanged, +and flips $C$ if both $A$ and $B$ are true. +In circuit diagrams, its representation is: + + + + + +This gate is reversible, because $A$ and $B$ are preserved, +and are all you need to reconstruct to $C$. +Moreover, this gate is universal, +because we can make a NAND gate from it: + + + + + +A NAND is enough to implement every conceivable circuit. +That said, we can efficiently implement NOT, AND, and XOR using a single Toffoli gate too. +Note that NOT is a special case of NAND: + + + + + + + + + + + + + +Using these, we can, as an example, make an OR gate +from three Toffoli gates, +thanks to the fact that $A \lor B = \neg (\neg A \land \neg B)$, +i.e. OR is NAND of NOT $A$ and NOT $B$: + + + + + +Thanks to its reversibility and universality, +the Toffoli gate is interesting in quantum computing, +where it is often referred to as the CCNOT gate. +In the basis $\ket{A} \ket{B} \ket{C}$, its matrix is: + +$$\begin{aligned} + \boxed{ + \mathrm{CCNOT} = + \begin{bmatrix} + 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{bmatrix} + } +\end{aligned}$$ + +If we apply this gate to an arbitrary three-qubit state $\ket{\psi}$, +it swaps the last two coefficients: + +$$\begin{aligned} + \mathrm{CCNOT} \ket{\psi} + &= \mathrm{CCNOT} \big( c_{000} \ket{000} + c_{001} \ket{001} + c_{010} \ket{010} + c_{011} \ket{011} \\ + &\qquad\qquad\quad\:\; c_{100} \ket{100} + c_{101} \ket{101} + c_{110} \ket{110} + c_{111} \ket{111} \big) + \\ + &= c_{000} \ket{000} + c_{001} \ket{001} + c_{010} \ket{010} + c_{011} \ket{011} \\ + &\quad\,\, c_{100} \ket{100} + c_{101} \ket{101} + c_{111} \ket{110} + c_{110} \ket{111} +\end{aligned}$$ diff --git a/content/know/concept/toffoli-gate/nand.png b/content/know/concept/toffoli-gate/nand.png new file mode 100644 index 0000000..5086537 Binary files /dev/null and b/content/know/concept/toffoli-gate/nand.png differ diff --git a/content/know/concept/toffoli-gate/not.png b/content/know/concept/toffoli-gate/not.png new file mode 100644 index 0000000..910cc85 Binary files /dev/null and b/content/know/concept/toffoli-gate/not.png differ diff --git a/content/know/concept/toffoli-gate/or.png b/content/know/concept/toffoli-gate/or.png new file mode 100644 index 0000000..8cb8763 Binary files /dev/null and b/content/know/concept/toffoli-gate/or.png differ diff --git a/content/know/concept/toffoli-gate/toffoli.png b/content/know/concept/toffoli-gate/toffoli.png new file mode 100644 index 0000000..53f3351 Binary files /dev/null and b/content/know/concept/toffoli-gate/toffoli.png differ diff --git a/content/know/concept/toffoli-gate/xor.png b/content/know/concept/toffoli-gate/xor.png new file mode 100644 index 0000000..4cebb3b Binary files /dev/null and b/content/know/concept/toffoli-gate/xor.png differ diff --git a/content/know/concept/von-neumann-extractor/index.pdc b/content/know/concept/von-neumann-extractor/index.pdc new file mode 100644 index 0000000..6e7caa3 --- /dev/null +++ b/content/know/concept/von-neumann-extractor/index.pdc @@ -0,0 +1,85 @@ +--- +title: "Von Neumann extractor" +firstLetter: "V" +publishDate: 2021-04-09 +categories: +- Cryptography + +date: 2021-04-09T19:59:31+02:00 +draft: false +markup: pandoc +--- + +# Von Neumann extractor + +The **Von Neumann extractor** is a simple example of a **randomness extractor**: +given a stream of "imperfectly random" bits, +it extracts the entropy, and outputs a "perfectly random" stream. + +As input, the Von Neumann extractor expects +a stream of independent (uncorrelated) bits, +i.e. the result of a [Bernoulli process](/know/concept/binomial-distribution/), +where each bit is $0$ with probability $p$, +and $1$ with probability $1 \!-\! p$. +Crucially, $p$ does not need to be $1/2$; +there may be a bias. + +The extractor will output a uniformly random stream with $p = 1/2$. +Given input bits $a_1, a_2, ...$, it achieves this +by looking at the bits in pairs $(a_1, a_2)$, $(a_3, a_4)$, etc. +Then: + ++ If $a_n = a_{n+1}$, it discards both bits. ++ If $a_n \neq a_{n+1}$, it keeps the first bit $a_n$, and discards $a_{n+1}$. + +Evidently, the first case $a_n = a_{n+1}$ occurs with the following probabilities: + +$$\begin{aligned} + P(0, 0) + = p^2 + \qquad \qquad + P(1, 1) + = (1 - p)^2 +\end{aligned}$$ + +Meanwhile, the second case $a_n \neq a_{n+1}$ occurs with probabilities given by: + +$$\begin{aligned} + P(0, 1) + = p (p - 1) + \qquad \qquad + P(1, 0) + = (p - 1) p +\end{aligned}$$ + +Crucially, they are equal; $P(0, 1) = P(1, 0)$. +Therefore, if the extractor encounters an input pair satisfying $a_n \neq a_{n+1}$, +the first bit $a_n$ is $0$ or $1$ with a 50-50 probability, +regardless of $p$. +Since the extractor only keeps those bits, +its output is guaranteed to be "perfectly random". + +Clearly, because it discards many of the bits, +the output stream will have a length $N_\mathrm{out} < N_\mathrm{in}$. +The exact value of $N_\mathrm{out}$ is as follows, +where $P(0, 1) + P(1, 0)$ is the probability that we keep a bit, +and the factor $1/2$ is due to us discarding half of the pair even in that case: + +$$\begin{aligned} + N_\mathrm{out} + = \frac{1}{2} N_\mathrm{in} \Big( P(0, 1) + P(1, 0) \Big) + = \frac{1}{2} N_\mathrm{in} \Big( 2 p (p - 1) \Big) + = N_\mathrm{in} p (p - 1) +\end{aligned}$$ + +The key assumption that allows the Von Neumann extractor to work +is that there is no correlation at all between the bits. +In practice, this may be difficult to achieve, +in which case a more complex randomness extraction scheme is needed. + + + +## References +1. J.B. Brask, + *Quantum information: lecture notes*, + 2021, unpublished. -- cgit v1.2.3