# Quantum Bayesian Networks

## March 14, 2014

Filed under: Uncategorized — rrtucci @ 3:47 am

Recently, Scott Aaronson posted in his blog 2 nice, teaser posts about Computational Complexity Theory.

In his first post, Scott discusses 2 papers. One paper by Lenny Susskind proposes that the number of elementary operations in a quantum circuit be used as a clock, to measure time intervals. The second paper by Terry Tao uses complexity theory to study the solutions of the Navier Stokes equation.

In his second post, Scott tries to explain to the non-specialist why he believes that $P\neq NP$.

I know next to nothing about complexity theory, so you better take anything I say next with a grain of salt.

$NP$= problems that can be verified in poly time.

$P$= problems that can be solved in poly time. $P\subset NP$. $P$ problems are the easiest to solve problems in $NP$.

$P$ and $NPcomplete$ are both subsets of $NP$. They are believed to be disjoint.

$NPcomplete=NPhard \cap NP$. $NPcomplete$ problems are the hardest to solve problems in $NP$ but their solution can be verified in poly time. 3-SAT problem is an element of $NPcomplete$.

If $P$ and $NPcomplete$ intersect, then they become equal to each other and to the whole $NP$ set. This doomsday scenario is called $P=NP$.

In one of his posts, Scott compares the boundary between sets $P$ and $NPcomplete$ to an “electrified fence” for electrocuting frogs. Raoul Ohio observes in the comments that the $P$, $NPcomplete$ separation reminds him of the phenomenon of “eigenvalue avoidance”, wherein a random matrix rarely has two degenerate eigenvalues. Raoul’s comment moved me to tears and inspired me to write the following very sad tale.

The Sad Tale Of The Two Sets That Once Kissed and Then Parted

Matrix $M(t)$ had two eigenvalues $x_1(t)$ and $x_2(t)$ where $t\in[0,1]$. Let

$Set_1 = \{ (t, x_1(t)) : t\in[0,1]\}$
$Set_2 = \{ (t, x_2(t)) : t\in[0,1]\}$

Originally, everyone thought that there was no symmetry in the system that $M(t)$ described, which meant that $Set_1$ and $Set_2$ did not intersect.

Then someone discovered an “accidental” symmetry that led to an “accidental degeneracy”, which led the two sets to kiss at a single point.

Then someone realized that the original model was too naive and that in real life there is a perturbation that breaks the accidental symmetry, so an eigenvalue “gap” develops, which led the two sets to stop kissing each other and part forever.

THE END