Crate quantum_world_state

Quantum World State

This library implements an in-ram database with relationships between elements inspired by quantum superposition and entanglement.

The QuantumWorldState is useful to represent the state of a system as it evolves into the future. It allows multiple exclusive “forks” of evolution to be explored without committing to a single one. It is useful for planning an optimal sequence of operations. The word “Quantum” in the QuantumWorldState doesn’t refer to anything being quantized, but rather it refers to some metaphores borrowed from quantum mechanics, namely we borrowed the ideas of superposition, collapse, and entanglement. Both the Many Worlds Interpretation and the Copenhagen Interpretation provide useful insights, but they are only metaphores and thus have limits.

Overview

The two fundamantal concepts in the QuantumWorldState are Elements and Transactions.

Each element can be thought of as a database record. An element can be any Rust type that implements the QWSElement trait, but ownership of the object must be given to the QWS. Each element is assigned a unique QWSElementID that can always be used to locate that element in the world. The QWS is an append-only data store, so you cannot modify an element after it has been added to the world, but a transaction may delete a given element and replace it with a newer version. Each version of the element will have its own unique QWSElementID.

Elements may also supply meta-data values, that can be used to locate the elements through queries. Currently the query semantics are limited but they may be extended in the future.

The append-only nature means that the history of the data structure is preserved immutably. It is possible to destroy an element with a transaction, and that effectively removes the element from a branch representing one possible reality, but an alternate history in which that element continues to exist is also possible and can’t be removed.

Transactions create and destroy elements. The process of creating a transaction involves providing 3 sets of elements:

• The elements created by the transaction (i.e. the elements added to the world)
• The elements destroyed by the transaction
• The elements entangled by the transaction

Entanglement occurs when an element is read in order to influence at least one of the elements being created. Conceptually you can think of entanglement as expressing a dependency. In other words, if the entangled element weren’t present, it would have been impossible to create at least one of the elements, so therefore the created elements can’t exist in the versions of the world where the entangled elements don’t also exist.

The state of the world at any given instant is referred to an Epoch. In a given epoch, each element will be in one of the states of existance defined in the QWSElementStatus enum. A transaction exists at an epoch.

Adding Some Elements and Transactions

#[macro_use] extern crate maplit; 
use quantum_world_state::*;
let mut qws = QuantumWorldState::new();

// Create an object that will become our first element
// MetaData keys without values function like tags
let forty_two_element = QWSElementWrapper::new_with_metadata(hashmap!{md_str!("my_tag") => vec![]}, 42);

// Add it to the QWS with a new transaction, and get back the new ElementID
let forty_two_id = qws.add_transaction(&[], &[], vec![Box::new(forty_two_element)])
    .unwrap().created_elements()[0];

// Create another transaction that destroys 42 and adds 43
qws.add_transaction(&[forty_two_id], &[], vec![Box::new(QWSElementWrapper::new_with_metadata(hashmap!{md_str!("my_tag") => vec![]}, 43))]);

Queries and Views

The QuantumWorldState can be queried to find elements matching a query expression. For now, the only query expression implemented is “key contains value”, although conceptually this could be extended to allow other more expressive queries, including compound queries e.g. with join operations, etc.

Queries are issued through the QWSDataView object. Effectively, a view object is a perspective from which elements are visible, and a query may limit the visible elements to the subset that match the query.

// Get a view of the queried elements
let query_view = qws.new_view().query_contains_key(&md_str!("my_tag")).unwrap();

// Iterate over the query results
for element_id in query_view.elements_iter() {
    // Prints "element 42" and "element 43" when run with the QWS from above
    println!("element {}", qws.get_element(element_id).unwrap().get_payload::<i32>().unwrap());
}

Superposition and Collapse

QWSDataViews can also be collapsed to restrict which elements are found by the query. In our example from above, element 42 and element 43 are mutually exclusive because element 43 was created in a transaction that destroyed element 42. Our query above returned both elements.
However the elements have a status of Superposition, indicating that they may or may not exist.

// We see that element 42 is in Superposition, in the query view we created above
println!("status of 42 = {}", query_view.get_element_status(forty_two_id));

In order to be sure an element exists, the view must be collapsed with respect to that element. We do that with one of the collapse_ methods of the QWSDataView.

// Get the transaction id for the transaction that created element 42
let transaction_id = qws.get_creator_transaction(forty_two_id).unwrap().id();

// Collapse the view further around that transaction 
let query_view = query_view.collapse_transactions(&[transaction_id]).unwrap();

// Now we see that element 42 is in KnownPresent, from the perspective of the view
println!("status of 42 = {}", query_view.get_element_status(forty_two_id));

// And we only see "element 42" when we iterate over the query results
for element_id in query_view.elements_iter() {
    println!("element {}", qws.get_element(element_id).unwrap().get_payload::<i32>().unwrap());
}

Conceptual Example

Say I am storing “contents_of_my_backpack” in a QuantumWorldState. At the start, I have an [Apple, a BaseballGameTicket and a FiveDollarBill], which are all Present, i.e. existant, at the epoch being queried.

Then I conduct a transaction where I spend the FiveDollarBill at a convenience store, and buy a Sandwich. At the epoch after that transaction, the query results for everything contained by the contents_of_my_backpack would be: [Apple, BaseballGameTicket, Sandwich], but at an earlier epoch, the results would be [Apple, BaseballGameTicket, FiveDollarBill].

There is no point in time that the FiveDollarBill and the Sandwich existed together in my backpack. It can be said that the FiveDollarBill and the Sandwich are entangled with each other. The different result sets represent two different states of the world, as it existed at two different Epoches.

If I issue the query without collapsing the epoch, I will get the results: [Apple-P, BaseballGameTicket-P, FiveDollarBill-S, Sandwich-S], where ‘P’ denotes that an element is KnownPresent and ‘S’ denotes that the element is in Superposition.

Now let’s consider an alternate reality in which I was less responsible or more thirsty. Say I chose to spend the FiveDollarBill on a SixPackOfBeer instead. (It’s really cheap beer.) Now there are 3 possible result sets that could be returned in 3 different Epoches: 1:[Apple, BaseballGameTicket, FiveDollarBill], 2:[Apple, BaseballGameTicket, Sandwich], 3:[Apple, BaseballGameTicket, SixPackOfBeer].

But I can collapse the view such that I only see results in which I have a SixPackOfBeer, thus reducing my possible result sets to only: [Apple, BaseballGameTicket, SixPackOfBeer]. This is referred to a partially collapsed view, because only results that are compatible with SixPackOfBeer are included. However, this it is not a fully collapsed view because no entanglement exists between SixPackOfBeer and the Apple and BaseballGameTicket.

Full vs. Partial Collapae

Continuing the example, If I traded the BaseballGameTicket for a ZooTicket, I would still be free to decide whether to buy the SixPackOfBeer or the Sandwich. In that situation, I can still collapse the view around the SixPackOfBeer and thus the set of possible fully collapsed world states would be: 1:[Apple, BaseballGameTicket, SixPackOfBeer], 2:[Apple, ZooTicket, SixPackOfBeer].

But what if I bought a BallParkHotDog at the stadium with my FiveDollarBill, instead of buying a Sandwich or a SixPackOfBeer at the convenience store? In that case, the BallParkHotDog is entangled, not only with FiveDollarBill, but also with BaseballGameTicket. So then, if I want to query for the “contents_of_my_backpack” in situations where I have the BallParkHotDog, the only possible results are: [Apple, BaseballGameTicket, BallParkHotDog].

The entanglement between BaseballGameTicket and BallParkHotDog is an asymetric entanglement. That is, the existance of BallParkHotDog depends on BaseballGameTicket up to the point that BallParkHotDog is created, but nothing related to the BallParkHotDog has any effect on BaseballGameTicket. Asymetric entanglement is created when one element is non-destructively used as input in the process of creating another element. This differs from real quantum physics, in which every interaction entangles all particles involved in that interaction, and nothing can influence something else without being influenced itself.

If the quantum physics metaphor is a little alien, luckily we software people are already acquainted with these concepts through distributed source control systems such as git. We can think of a git repository as a QuantumWorldState of the state of all of the files in the source tree, and a single checkout as being a collapsed WorldState as it exists for one observer.

Insights

• Every element was created by exactly one transaction, so for any element, there is at least one epoch where it is known to exist
• Transactions entangle elements, so by extension transactions have dependencies and conflicts with other transactions
• Transactions can be arranged into a branching tree

Misc

The implementation of this object has some similarities to a solver for the Boolean Satisfiability Problem. Perhaps there are some insights to be gained from the academic research on that topic.

Future Work & Optimization Opportunities

Eventually, if (when) this becomes a bottleneck, I’d like to investigate better implementations, and possibly better interfaces to get more performance. Currently we’re using immutable HashSets and HashMaps for the QueryMasks on the theory that cloning them is cheap. However we also end up performing a lot of union operations in situations where it is highly possible both sets will contain a large number of elements. I am not sure about the performance of union operations in this case although algorithms definitely exist to optimize this for our use case where we are likely to have many operations that involve very nearly the same data. Something along the lines of chunking the sets up with a checksum around each chunk and treating the entire chunk as one entry.

An alternative is to replace the datastore with something like SQLite for the main datastore, in order to support more elaborate queries. I’d need to do more research into whether or not SQL could be limited to only select statements to avoid making destructive changes to the datastore that would make it out of sync with the dependency mask meta-data.

Another (non-exclusive) path to consider is a database that supports data-flow programs where the Mask that dictates the status of each element at a given epoch can actually be a dataflow program to update a materialized view. When we get to this stage, consider looking at Noria Database, as well as the “timely” Dataflow Rust crate.

Finally, as another alternative, it’s likely that the Immutable HashSets that I’m using to store the mask are actually not the best performing data structure for this use case. Specifically, we know our sets only store numerical IDs and we also know the IDs are assigned sequentially. We also know there will be high ammounts of clustering. Therefore I suspect that some kind of hierarchicial bitmap datastructure (hierarchical because large blocks of 1s or 0s could) be represented as small sentenel values and compared and stored more efficiently. Anyway, we can measure this later when we know what operations need to be fast.

Macros

md_bool

Expresses the bool value as a QWSMetaData type. Equivalent to QWSMetaData::Bool()

md_int

Expresses the Integer value as a QWSMetaData type. Equivalent to QWSMetaData::Int()

md_str

Expresses the String or &str value as a QWSMetaData type. Equivalent to QWSMetaData::String()

Structs

QWSDataView

A view into the QuantumWorldState that may represent a partially collapsed or fully collapsed view, and / or the results of a query.

QWSElementID

An index that uniquely identifies an element in a QuantumWorldState

QWSElementWrapper

A wrapper around any generic type to conveniently implement the QWSElement trait.

QWSElementsIterator

An Iterator for elements in the QuantumWorldState. A QWSElementsIterator is used to access results from a query.

QWSTransaction

Represents a transaction in the QuantumWorldState, and provides methods to inspect the transaction.

QWSTransactionID

An index that uniquely identifies a transaction in a QuantumWorldState

QuantumWorldState

The top-level object, containing all elements and transactions for a given world.

Enums

QWSElementStatus

Describes a status for an element, i.e. whether an element is known to exist, known not to exist, or is in an undefined (superposition) state with respect to QWSDataView of the QuantumWorldState

QWSError

An error type that is used to pass back error codes and error messages

QWSMetaData

An enum to represent a data type that can function as either a key or a value used by the meta-data search capabilities of the QWS

Traits

QWSElement

An element in the QuantumWorldState must implement this trait.