CliqueVM is an experimental framework for building computational models, both classical and quantum mechanical, and tracing their multithreaded evolution as 2D/3D graphs. New models can be coded in JavaScript directly on the app by modifying the operator function that maps a clique of states into a new generation of states.

Run online: https://met4citizen.github.io/CliqueVM/

The purpose of the project is NOT to make an app for practical simulations, but to study the underlying concepts and ideas.

For an overview of the notation used in the app, check out the following YouTube video. In the video, David introduces us to the CHSH game and explores the mystery of quantum entanglement by modeling particles as computational objects.

The app uses @hpcc-js/wasm for compiling Graphviz DOT language into SVG, 3d Force-Directed Graph for rendering 3D graphs and CodeMirror as a JavaScript editor.

The project is based on my two earlier projects Hypergraph and BigraphQM. For a philosophical take on these ideas read the blog post The Game of Algorithms.

All physical systems evolve over time. We can represent this with a mathematical object called an operator that maps the state of the system at time $t$ into another state at $t+1$. When we run this operator iteratively, we get a computational object called a program, a sequence of operations, acting on states.

Often the system has so many possible states that it is very hard or impossible to describe the operator. Fortunately, all physical interactions are, as far as we know, spacelike and local. This means that instead of acting on the full state of the system we can process smaller collections of microstates independently of each other. We call these collections cliques, because they show up as maximal cliques in our graphs.

For two programs to end up spacelike and local, their computational histories must be mutually consistent and they must compute the same function. More specifically, their lowest common ancestors (LCAs) must be operations, not states, and they have to belong to the same equivalence class of programs. Both of these properties are relative. If and when these pairwise relations change, we end up with not one but multiple threads that can branch, merge and run in parallel.

A multithreaded system, real or simulated, can be classical, quantum mechanical, or some mix of the two, depending on the operator. The thing that makes a system quantum mechanical is the existence of superpositions. A quantum superposition is a situation in which some computational sequence $A$ is pairwise consistent with both $B$ and $C$, but $B$ and $C$ are not consistent with each other. Graph-theoretically these are called open triplets. They are second-order inconsistencies that break local classical states into two or more overlapping maximal cliques.

Once we know how to calculate these maximal cliques, we can use them as inputs to our operator function, iterate the process, and trace the system's multithreaded evolution with a pre-defined set of graph-based tools. All this can be done within the app.

CliqueVM is called a framework, because it allows us to define, among others, our own initial state, operator and equivalence relation. By using JavaScript's primitive types, such as numbers, strings, arrays and objects, we can construct hyperedges, vectors, complex numbers, matrices, coordinate systems etc. Using these data structures as states, it is possible, at least in theory, to build different types of rewriting systems, physical simulations and other computational models.

Let $H$ be a 3-partite directed acyclic graph (DAG) with the following three parts: operations $V_o$, states $V_s$, and maximal cliques $V_c$.

$\displaystyle\qquad H= (V_o \cup V_s \cup V_c, E),\quad E\subseteq (V_o{\times}V_s)\cup (V_s{\times}V_c)\cup (V_c{\times}V_o)$

At each new step, the latest set of maximal cliques, $L_c$, is used as an input for the operator $\hat{M}$, which maps each clique into a new generation of operations and output states.

$\displaystyle\qquad L_c=\big\lbrace v \in V_c\mid\mathbf{deg^+} (v)=0 \big\rbrace$

$\displaystyle\qquad \hat{M}: L_c\longrightarrow (V_o \cup V_s, E),\quad E\subseteq V_o{\times}V_s$

In order to calculate the new generation of maximal cliques, we start from the latest operator-generated states $L_s$. Two states are local and spacelike if and only if they are equivalent $\sim$ and their lowest common ancestors (LCAs) are operations. Let an undirected graph $G$ track all such pairs.

$\displaystyle\qquad L_s=\big\lbrace v \in V_s\mid\mathbf{deg^+} (v)=0 \big\rbrace$

$\displaystyle\qquad G= (L_s, E),\quad E = \big\lbrace (a,b)\mid a\sim b\wedge\mathbf{LCA}_H(a,b)\subset V_o\big\rbrace$

Now, let $\Omega$ be one of the disconnected subgraphs in $G$. In order to find its maximal cliques, we use a variant of the Bron-Kerbosch algorithm. The algorithm has the worst-case time complexity $O(3^{n\over 3})$ and for k-degenerate graphs $O(kn3^\frac{k}{3})$.

$\displaystyle\qquad\mathcal{F} = \mathbf{BK}(\varnothing,\Omega,\varnothing)$

ALGORITHM BK(R, P, X) IS
    IF P and X are both empty THEN
        report R as a maximal clique
    choose a pivot vertex u in P ⋃ X
    FOR each vertex v in P \ N(u) DO
        BK(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

Once all the maximal cliques of all the disconnected subgraphs have been calculated, a new iteration (step) can be started.

If the operator is deterministic, the system, too, will be deterministic. However, if the operator generates more that one operation, even a deterministic system can become quantum mechanical. In these cases the evolution will appear probabilistic to any internal observer due to self-locating uncertainty.

Under self-locating uncertainty, an observation becomes a process in which the observer interacts locally in a way that resolves all the second-order inconsistencies (superpositions). These interactions make new shortcuts through the ancestral structure. This in turn prevents certain future interactions, which appears to the internal observer as a wave-function collapse.

From the internal observer's point of view, the proportion of all the possible Hamiltonian paths that lead to the maximal clique $\mathcal{F_i}\in\mathcal{F}$ is the probability $p_i$ of that outcome.

$\displaystyle\qquad p_i={{|\mathcal{F_i}|!}\over{\sum\limits_{j} |\mathcal{F_j}|!}},\quad i\in \lbrace 1,\dots,|\mathcal{F}| \rbrace$

Note that from the external point of view - from "the point of nowhere" - all the possible interactions get actualised without any randomness or probabilities. In this context, often called the Many-Worlds interpretation, $p_i$ can be seen as the path weight.

The framework offers the following graph-based views:

VIEW	DESCRIPTION
Trace	Multithread trace views the evolution of the system as a directed acyclic graph. Option Full shows the full 3-partite DAG with local spacetime clusters. Option Cliques shows cliques and local clusters ignoring operations and states. Option Locs shows only spacetime locations and their spatial coordinates.
Snap	Snapshot (hypersurface/foliation) of the multithread trace at the current step. Option States shows the snapshot at the level of states. Two states are connected if they are local and consistent (spacelike) relative to each other. Option Cliques shows the snapshot at the level of cliques. Two cliques are connected if they overlap, that is, share common states. Option Locs shows the snapshot at the level of locations. Two locations are connected if they have an immediate parent location.
Space	Spatial 3D projection of the evolution. Each node represents a spatial coordinate. Two coordinates are connected with an undirected edge when one of them has been a direct parent of another. Option Paths shows the relative density of operations leading to each coordinate at the current step. Option Action shows the relative density calculated over time starting from the initial state.
Hits	Detector hit counts as a bar chart. Option Step shows the number of hits at the current step. Option Total shows the total count starting from the initial state.

The previous or the next step can be calculated by clicking the arrows. Reset returns the model to its initial state. Cancel aborts current processing and cancel the job queue.

By clicking Model, the user can specify his own model, deploy the model, and export/import models as JSON strings.

A model is a set of JavaScript functions:

The INITIAL STATE returns an array of initial states. A state can be any valid JavaScript data structure. An example:

/**
/* @return {any[]} Array of initial states.
**/
return [1];

The OPERATOR gets a maximal clique (array of states) as its input and returns an array of operations so that each operation is an array of output states. An example:

/**
* @param {any[]} c Clique, array of input states
* @return {any[][]} New operations with output states.
**/
let sum = c.reduce((a,b)=>a+b,0);
let state1 = (2*sum+3) % 10;
let state2 = (3*sum+1) % 7;
let operation1 = [ state1, state2 ];
return [ operation1 ];

The COORDINATE / EQUIVALENCE gets a state as its input and returns its coordinate label as a string. The coordinate label is used to test whether two states are equivalent (local). This state equivalence could also be seen as an observer-theoretic coarse-graining and/or encoding function. An example:

/**
* @param {any} s State
* @return {string} Spatial coordinate.
**/
return s.toString();

The VISIBILITY gets a state as its input and returns true or false depending on whether the state is to be shown or not. Note: This doesn't affect the processing, only how the states get visualised. An example:

/**
* @param {any} s State
* @return {boolean} true, if the state is to be shown.
**/
return true;

The DETECTORS returns an array of coordinates to be monitored. Whenever some detector state is visited at some step, its counter is increased. An example:

/**
* @return {string[]} Array of detector coordinates.
**/
return ['0','1','2','3','4'];

All functions get executed with the "use strict" directive.

NOTE: The JavaScript source code in the JSON string is used to create a new Function object inside a Web Worker. This means that the code will have no DOM access and critical issues such as infinite loops can be easily solved by terminating the worker (reset). However, for security reasons, always check the model before importing!

In order to keep the functions short, the framework offers a simple API (ModelAPI class) with a set of commonly used utility functions and generators. In the app these methods can be called with this, for example: this.id().

TODO: Add utility functions for typical use cases such as graph rewriting.

By default, the model is computed in your browser using Web Worker threads. However, it is also possible to compute the model on an external WebSocket server.

In order to run the server, install Node.js, clone the project, and install:

git clone https://github.com/met4citizen/CliqueVM.git
cd CliqueVM/server
npm install

There are two types of servers: a single server server.mjs and a distributed server serverd.mjs. The single server computes the whole model in one instance. Distributed servers compute only cliques, but unlike in the single server architecture, you can run and utilize several server instances, each running on a different computer.

If you want to use the single server architecture, start the server with the following command:

node server.mjs --cert=/path/server.crt --key=/path/server.key --port=8880

Alternatively, if you want to use the distributed architecture, run the following command on each computer in your computer clusters:

node serverd.mjs --cert=/path/server.crt --key=/path/server.key --port=8881

Once the server/servers is/are running, open CliqueVM page, click Server on toolbar, specify your server URL(s), and click the check box next to it to enable.

Notes:

• If you run the server over SSL, use protocol wss on the URL, e.g. wss://<domain.com>:8880/.
• If you run the server without SSL, use protocol ws on the URL, e.g. ws://<domain.com>:8880/.
• If you run CliqueVM over HTTPS, but the server without SSL, you need to allow insecure content from your browser's settings (not recommended).
• If you use a self-signed certificate on your server, you might need to first open the HTTPS page, e.g. "https://<domain.com>:8880/", on your browser to accept the certificate.

Copy the JSON string below and import it to the app:

{
  "init":"return [\"ABBABAA\"];",
  "oper":"let a=/BA/gi,b=\"AB\",r,o=[];\nwhile( r=a.exec(c[0]) ) {\n  let s = c[0].split(\"\");\n  s.splice(r.index,b.length,b);\n  o.push( [s.join(\"\")] );\n};\nreturn o;",
  "coord":"return s;",
  "show":"return true;",
  "detectors":"return [];"
}

Copy the JSON string below and import it to the app:

{
  "init":"let v = this.id();\nreturn [[v,v],[v,v]];",
  "oper":"let s = this.clone(c);\nthis.shuffle(s);\nif(s.length>=2){\n  let v1=s[0][0],v2=s[0][1],v3=s[1][1],v4=this.id();\n  s.splice(0,2,[v1,v2],[v1,v4],[v2,v4],[v3,v4]);\n}\nreturn [s];",
  "coord":"return s[0].toString();",
  "show":"return true;",
  "detectors":"return [];"
}

Copy the JSON string below and import it to the app:

{
  "init":"return [{x:0,y:0,z:0},{x:0,y:0,z:0}];",
  "oper":"let s=[],t=[];\nfor( let p of c ) {\n  let [a,b]=this.clone([p,p]);\n  let i=this.shuffle(['x','y','z'])[0];\n  if (a[i]<3) a[i]++;\n  if (b[i]>-3) b[i]--;\n  s.push(a);\n  t.push(b);\n}\nreturn [s,t];",
  "coord":"return s.x+','+s.y+','+s.z;",
  "show":"return true;",
  "detectors":"return Array.from({length:7},(_,i)=>i-3+',0,0');"
}

In the CHSH game, two players, Alice and Bob, are not allowed to communicate with each other. The referee sends them each a random bit, $Q_A,Q_B\in \lbrace 0,1\rbrace$, for which they both respond with a bit, $R_A,R_B\in \lbrace 0,1\rbrace$. If the logical AND of questions equals the logical XOR of responses, they win. It can be shown that in the repeated game Alice and Bob can win at most 75% of the time. This classical limit, $Pr[Q_A\wedge Q_B = R_A\oplus R_B]\leq 75\%$, is called the CHSH inequality.

Suppose we now change the game so that the referee sends Alice and Bob not only two random bits but also two entangled particles. From actual physical experiments we know that if Alice and Bob measure their own entangled particles in a certain way, they can break the classical 75% limit. This is called the violation of CHSH inequality.

In the following CliqueVM model, we show the violation of CHSH inequality using multithreaded evolution and bit rotations (circular shift). The final results that the model prints to the log are the following:

--- SIMULATION STARTS ---
0*0 == 0^0  WIN 41.7% | 0^1 Lost  8.3% | 1^0 Lost  8.3% | 1^1  WIN 41.7%
0*1 == 0^0  WIN 41.7% | 0^1 Lost  8.3% | 1^0 Lost  8.3% | 1^1  WIN 41.7%
1*0 == 0^0  WIN 41.7% | 0^1 Lost  8.3% | 1^0 Lost  8.3% | 1^1  WIN 41.7%
1*1 == 0^0 Lost  8.3% | 0^1  WIN 41.7% | 1^0  WIN 41.7% | 1^1 Lost  8.3%
--- SIMULATION ENDS ---

Copy the JSON string below and import it to the app:

{
  "init":"// Create a matrix for the results\nthis.qs = [[0,0],[0,1],[1,0],[1,1]]; // Possible questions\nthis.rs = [[0,0],[0,1],[1,0],[1,1]]; // Possible responses\nthis.results = {};\nfor( const q of this.qs ) {\n  const qkey = q.join('∧');\n  this.results[qkey] = {};\n  for( const r of this.rs ) {\n    const rkey = r.join('⊕');\n    this.results[qkey][rkey] = {\n      status: ( (q[0] * q[1]) === (r[0] ^ r[1]) ) ? 'W' : 'L',\n      weight: BigInt(0)\n    };\n  }\n}\n\n// Spin in computational basis\nthis.spinup = '00001111';\nthis.spindown = '11110000';\n\n\n// Helper functions for binary vector rotation and Hamming distance metric\nthis.rot = (s,n) => { return s.slice(-n % s.length) + s.slice(0,-n % s.length); }\nthis.dhamm = (s,t) => { return [...s].reduce( (a,b,i) => a + (b === t.charAt(i) ? 0 : 1),0 ) }\n\n// Start the first round\nthis.log('--- SIMULATION STARTS ---');\n\nreturn [ \"Questions\"];",
  "oper":"// Location is the first part of the state and the same within the clique\n// Subsequent parts of the state contain the messages and memories\nconst location = c[0].split(\"-\")[0];\nconst messages = {};\nc.forEach( x => {\n  const m = x.split('-')[1];\n  if ( m ) {\n    const p = m.split('+');\n    messages[p[0]] = (p.length > 2 ? p.slice(1) : p[1]);\n  }\n});\n\n// Classical state machine\nconst ops = [];\nif ( location === 'Questions' ) {\n  \n  // Send classical messages, one for Alice, one for Bob\n  const [ QA, QB ] = this.qs.shift();\n  ops.push( [ \"AliceQ-Question+\" + QA, \"BobQ-Question+\" + QB, \"Particle\" ] );\n\n  // Next question, if no more questions then report\n  if ( this.qs.length ) {\n    ops.push( [ \"Questions\" ] );\n  } else {\n    ops.push( [ \"ZZZReport\" ] );\n  }\n  \n} else if ( location === 'Particle' ) {\n\n  // Send entangled spin particles to Alice and Bob\n  // Here particle is a superposition of all binary rotations\n  for( let i=0; i<this.spinup.length; i++ ) {\n    ops.push( [\n      'AliceSG-Particle+' + this.rot(this.spinup,i),\n      'BobSG-Particle+' + this.rot(this.spindown,i)\n    ]);\n  }\n  \n} else if ( location === 'AliceQ' ) {\n\n  // Parse message and set measurement angle:\n  // - If question is 0, do not rotate\n  // - If question is 1, rotate -45° (-2*pi/8)\n  const question = messages[\"Question\"];\n  const rotate = ( question === '0' ? 0 : Math.round( (-2/8) * this.spinup.length) );\n  const setting = this.rot(this.spinup, rotate);\n  ops.push( [ 'AliceSG-Measure+' + question + '+' + setting ] );\n  \n} else if ( location === 'AliceSG' ) {\n\n  // Parse message\n  const [question,setting] = messages[\"Measure\"];\n  const particle = messages[\"Particle\"];\n\n  // Simulate Stern–Gerlach\n  // You as an observer can only detect up/down, which\n  // respond to responses 0/1\n  const d = this.dhamm(particle,setting);\n  const limit = Math.round(this.spinup.length / 2);\n  const R0 = 'Responses-Alice+' + question + '+' + '0';\n  const R1 = 'Responses-Alice+' + question + '+' + '1';\n  if ( d > limit ) ops.push( [ R1, R1 ] );\n  if ( d == limit ) ops.push( [ R0 ], [ R1 ] );\n  if ( d < limit ) ops.push( [ R0, R0 ] );\n  \n} else if ( location === 'BobQ' ) {\n\n  // Parse message and set measurement angle:\n  // - If question is 0, rotate 135° (3*pi/8)\n  // - If question is 1, rotate -135° (-3*pi/8)\n  const question = messages[\"Question\"];\n  const rotate = ( question === '0' ? Math.round( (3/8) * this.spinup.length) : Math.round( (-3/8) * this.spinup.length) );\n  const setting = this.rot(this.spinup, rotate);\n  ops.push( [ 'BobSG-Measure+' + question + '+' + setting ] );\n  \n} else if ( location === 'BobSG' ) {\n\n  // Parse message\n  const [question,setting] = messages[\"Measure\"];\n  const particle = messages[\"Particle\"];\n\n  // Simulate Stern–Gerlach\n  // You as an observer can only detect up/down, which\n  // respond to responses 0/1\n  const d = this.dhamm(particle,setting);\n  const limit = Math.round(this.spinup.length / 2);\n  const R0 = 'Responses-Bob+' + question + '+' + '0';\n  const R1 = 'Responses-Bob+' + question + '+' + '1';\n  if ( d > limit ) ops.push( [ R1, R1] );\n  if ( d == limit ) ops.push( [ R0 ], [ R1 ] );\n  if ( d < limit ) ops.push( [ R0, R0 ] );\n  \n} else if ( location === 'Responses' ) {\n\n  // Parse the original questions and the responses\n  const [QA,RA] = messages[\"Alice\"];\n  const [QB,RB] = messages[\"Bob\"];\n  \n  // Add the weight to the report\n  // For an observer, Charlie, the weight is the number of permutations with\n  // the clique, which is the factorial of the clique size.\n  this.results[QA+'∧'+QB][RA+'⊕'+RB].weight += this.factorial(c.length);\n  \n} else if ( location === 'Report' ) {\n  \n  // Print report for all questions\n  for( let [q,rs] of Object.entries(this.results) ) {\n\n    // Sum of the factorials in order to calculate the probabilities\n    const tot = Object.values(rs).reduce( (a,b) => a + (b.weight || BigInt(0)), BigInt(0) );\n\n    // Print summary for question q\n    let s = [];\n    for( let [r,vs] of Object.entries(rs) ) {\n      const p = Number( (vs.weight || BigInt(0) ) * 10000n / tot ) / 10000;\n      s.push( r + ' ' + vs.status + ' ' + (100*p).toFixed(1).padStart(4) + '%' );\n    }\n    this.log( q + ' == ' + s.join(' | ') );                \n  }\n\n  this.log('--- SIMULATION ENDS ---');\n  \n} else if ( location.startsWith('Z') ) {\n  // Delayed state\n  ops.push( c.map( x => x.substring(1) ) );\n}\n\nreturn ops;",
  "coord":"// Coordinate is the first part of the state\nreturn s.split('-')[0];",
  "show":"return true;",
  "detectors":"return [];"
}