How semantic polymorphism works in quantum computing
A few months ago, I published an article about an obscure mathematical concept which can be used to describe high-level semantic information. The gist is that certain algebraic structures (particularly the free commutative magma) can represent any discrete high-level semantic concept using an arbitrary reference frame of initial concepts. This model leads to a unique programming paradigm and file format detailed in this Medium article and Google Colab notebook:
After thinking some more about this topic, I realized that a similar concept emerges in the mathematical model of quantum computing. While this explanation will require some prior knowledge of linear algebra and quantum mechanics, I will do my best to explain this in a way that can be vaguely understood by everyone.
Any classical and quantum algorithm can be represented via a matrix M which maps some given input state x to a corresponding output y, represented by the equation y = Mx. The key difference between computing models can be seen in the limitations of the matrices and vectors.
Classical computers require M to be a logical matrix and impart a one-hot restriction on x and y. For instance, the number 3 can be represented as [00010000…] (three zeros and then one 1). For clarity, we can drop trailing zeros, e.g. [0001…] = 3.
Notice that this model represents zero as [10…] and one as [01…]. In bra-ket notation, this is usually written as |0⟩ = [10] and |1⟩ = [01]. From here, we can find the physical binary representation by thinking of x as the Kronecker product of the binary representation of the number.
The number 6 is 110 in binary, which is written as |0⟩ ⊗|1⟩ ⊗|1⟩ or more concisely |011⟩. The order of the bits is flipped because our vector [0000001…] begins from the left rather than the right like typical counting numbers.
0 │0⟩ │0⟩ │0⟩ │0⟩ ...
1 │1⟩ │0⟩ │0⟩ │0⟩ ...
2 │0⟩ │1⟩ │0⟩ │0⟩ ...
3 │1⟩ │1⟩ │0⟩ │0⟩ ...
4 │0⟩ │0⟩ │1⟩ │0⟩ ...
5 │1⟩ │0⟩ │1⟩ │0⟩ ...
6 │0⟩ │1⟩ │1⟩ │0⟩ ...
7 │1⟩ │1⟩ │1⟩ │0⟩ ...
8 │0⟩ │0⟩ │0⟩ │1⟩ ...
9 │1⟩ │0⟩ │0⟩ │1⟩ ...While this is quite a complex way to think about algorithms, it lays the groundwork for understanding the logic of both quantum computing and semantic polymorphism.
Unlike their classical counterparts, quantum computers are able to work with any combination of numbers simultaneously and in specific proportions via quantum superposition. In other words, it is possible to run algorithms on a wave function of bit configurations, each with a rotation-like phase and relative magnitude. The catch is that while x is far more flexible, M must be a unitary matrix and y can only be measured indirectly based on the probability distribution generated by the algorithm.
If you are looking for ways to better understand this computational model, I highly recommend Michael Nelsen’s Quantum Computing for the Determined YouTube series:
Now is where things begin to get interesting for those already familiar with the above topics. The vectors |0⟩ and |1⟩ form a basis in a two-dimensional space, and each Kronecker product doubles the number of dimensions in the system. As such, we end up with a countably infinite dimensionality.
The key concept that fascinates me is the ability to reinterpret each dimension as an entirely different chain of Kronecker products. By abstracting away the underlying architecture of bits or qubits, we can, for example, relabel the entire system using a three-dimensional basis of |0⟩, |1⟩, and |2⟩.
0 │0⟩ │0⟩ │0⟩ ...
1 │1⟩ │0⟩ │0⟩ ...
2 │2⟩ │0⟩ │0⟩ ...
3 │0⟩ │1⟩ │0⟩ ...
4 │1⟩ │1⟩ │0⟩ ...
5 │2⟩ │1⟩ │0⟩ ...
6 │0⟩ │2⟩ │0⟩ ...
7 │1⟩ │2⟩ │0⟩ ...
8 │2⟩ │2⟩ │0⟩ ...
9 │0⟩ │0⟩ │1⟩ ...In this sense, we can easily “simulate” any other basis simply by using a different numerical base for our vector indices. This concept has significant potential for discovering new quantum algorithms and languages.
Since the quantum computing ecosystem has not yet reached this level of abstraction, I made an experimental language designed around reinterpreting the dimensions of quantum systems. You can learn more by browsing the GitHub repository, skimming this article, or running the online examples.
Let’s take this a step further. Since we can choose any interpretation of the space, it is possible to represent increasingly unusual structures.
These systems can be simulated by one another by choosing a one-to-one mapping between states. In these examples, we use the natural numbers to define an arbitrary total order for each system. In practical situations, one might derive a total order based on the physical location of each qudit in the architecture.
In essence, this layout is the semantic “file format” described in the previously mentioned notebook. We can now move on to explore how a sense of logical polymorphism emerges from this structure.
As a brief recap of the relevant information in the notebook, it is possible to use the counting system shown above to recursively define concepts using a discrete semantic basis. Inspired by RDF and Hexastore, the system is designed for semantic representation and querying. Instead of using the slightly anthropocentric notion of subject-verb-object triples, we focus on a general formulation which corresponds to an infinite undirected recursively defined graph. In doing so, a “query” directly corresponds to an algorithm derived from the abstract high-level interpretation of a given model.
It turns out that in a quantum context, semantic models show some fascinating and useful behavior. Typically, given an initial state and a set of rules, one may continue to expand the state to encompass the full logical implications of the system. However, upon introducing the ability to superpose states and rules, the model generates a probability distribution as though each rule operated on all possible logical structures. Likewise, phase shifting can be used to distinguish between different types of logical outcomes. For instance, an input concept which uses the complex unit vector i can be interpreted as “this concept is definitely outside of the model.” After applying quantum phase estimation, one can identify the extent to which a statement is expected to be within the model assuming unknown as the default conclusion.
TLDR: you can interpret quantum superposition as a probability distribution of logical assertions. Likewise, you can use the phase of a quantum state to distinguish between two types of conclusions, such as “known to be true” and “known to be false” assuming unknown for everything else.
In summary, it’s possible to design more intuitive quantum algorithms by relabeling the individual states of a quantum system, and this approach is ideal for expressing higher-order logic and semantic information.
I hope that this article has given you some ideas and inspiration for your next project.
Cheers!
