Classical Mental Models are Incommensurate with the Quantum Mindset

The Classical and Quantum Mindset

My blog today is to draw the reader into questioning one's own mindset in attempting to conceive and imagineer new quantum inspired or quantum computing models.  I will get back to the probability density polytope shortly from the previous post.

I would like to start out with a quote from a really good book on Quantum Computing:

"Algorithm design for quantum computers is hard because designers face two difficult problems not faced in the construction of algorithms for classical computers. First, our human intuition is rooted in the classical world. If we use that intuition as an aid to the construction of algorithms, then the algorithmic ideas we come up with will be classical ideas. To design good quantum algorithms one must ‘turn off’ one’s classical intuition for at least part of the design process, using truly quantum effects to achieve the desired algorithmic end. Second, to be truly interesting it is not enough to design an algorithm that is merely quantum mechanical. The algorithm must be better than any existing classical algorithm! Thus, it is possible that one may find an algorithm which makes use of truly quantum aspects of quantum mechanics, that is nevertheless not of widespread interest because classical algorithms with comparable performance characteristics exist. The combination of these two problems makes the construction of new quantum algorithms a challenging problem for the future."   Nielsen, Michael A.; Chuang, Isaac L. (2010-12-09). Quantum Computation and Quantum Information. Cambridge University Press. Kindle Edition. 

In simple terms, this hits to the heart of the Church-Turing Thesis (which has never been well challenged, disproved nor proved) - so it would seem that it will be very hard to build efficient true quantum algorithms,  even harder to build a quasi-quantum, pseudo-quantum algorithm, and plausibly moderately hard to build a quantum-inspired algorithm.

Ultimately, and at the foundation of current systems, it must hold from whichever variety of Church-Turing Thesis that you would like, that a conception of any programming language must be a Turing machine:  if, however, the foundation is changed, then conceptually we are in a place where the current history of science has not yet ventured and I have no idea about what that might look like - I admit it can exist, but, that the foundations must be radically not as they are today (in the conception of theories in modern physics).

However, in attempting to get outside the box of classical thinking, it does serve some purpose to expound upon a simple concept: the Qubit and the Bit.

In reviewing the traditional understanding of a Qubit, it is stated often that a qubit is just like a classical bit only that it can probabilistically flip between a state of "0" and a state of "1".   Therefore, the question oft comes up why we can not just use a statistical (hidden) variable with a probability distribution function that represents either "0" or "1" by a certain probability.

Here is the answer: because in the classical case, we have already chosen how the probability will outcome while in the quantum case we are forced to measure and interact.

This, in a deep way, implies that there is no way to describe a qubit classically. This point goes back to the essence of the quote from Nielsen and Chuang's text on Quantum Computation and Quantum Information.

Another difference is that a bit is a point-instance object while a qubit is a system: it is a quantum-mechanical system and can hold more information than just one bit. The outcome of this is that you cannot redefine a qubit as an interpolation between a function that outputs "0" and "1" in the same way that you can describe, say, a fair coin toss.  They completely not related.

However, my personal view is that while we cannot yet work effectively and efficiently at the level of individual qubits (though research is making progress), what about an ensemble?  An ensemble will exhibit statistical properties just like any ensemble and the relevance of individual qubits becomes subsumed within the ensemble, so that, at least from the algorithmic viewpoint, we have indirect access to qubits as a result of the statistics.  Is that possible?

The implication of that last statement is that ensembles, as long as they are made up of quantum systems, store individual qubits but can be indirectly manipulated via classical techniques at the level of the ensemble.  In the real world, for example, even though we do not have access to the individual quantum systems of a Superconductor, nonetheless, we have access to the ensemble effects of the quantum systems (i.e. its superconductivity properties) and indeed companies like D-Wave have taken advantage of this.

What about the research on individual qubits? Qubits are idealized mathematical objects and in nature, discoveries on how to implement the qubit abstraction have resulted in, for example:  the states of electrons orbiting an atom, or the nuclear spin in magnetic fields or as the polarizations of a photon.

And in between the pure ensemble model and individual qubit model is the model of the topological qubit that can be implemented in terms of states of matter (either via an ensemble or via a unit), such as for example, in  Graphene.  I believe, the future, that the novel functionally graded doped versions of Graphene will result in topological qubits (a personal belief of mine).

What does all this tell us about the Classical versus the Quantum mental models or mindsets that we use.  I claim that it tells us the following:  that we need to base our thinking on mathematical abstractions first, and then seek to discover design models for these abstractions in terms of real world physics, or equivalently, for us computer geeks, in terms of Turing Machine models.

Until Next Time!

Quantum Inspired Computing - the Density Polytope Quanton (and Kyndi's Computation Model)

Quantons (aka Kyndi's Model for Quantum Inspired Computing)

First, I would like to start off with a quote:

"Tensor networks provide a mathematical tool capable of doing just that. In this view, space-time arises out of a series of interlinked nodes in a complex network, with individual morsels of quantum information fitted together like Legos. Entanglement is the glue that holds the network together. If we want to understand space-time, we must first think geometrically about entanglement, since that is how information is encoded between the immense number of interacting nodes in the system." - Tensor Networks

Why I mention this is that the MERA (multiscale entanglement renormalization ansatz) model has potentially interesting surrogates in terms of classical structures. One of the computer science components at the heart of the concepts are variable orderings and permutations with respect to network structures (specifically tree tensor network diagrams).  However, none of this matters if it cannot be done fast.   So the crux is to identify the mappings between structural regularity and analytic precision between representations like tensor networks and surrogates that are faster but essentially equivalent. 

One way to approach this is through geometry.

The idea of tensor networks, and in general, matroids, could be seen from the viewpoint of multiplihedra, associahedra and related polytopes (zonotopes) have a very interesting structure. 

More on tensor networks and matroids in another posting - there are several intertwined concepts that still need to be surfaced.  Mathematical ideas without understanding, in my view, is junk factoids - so I will do my best to craft a path from where we are (with introducing ideas, specifically an interesting object, the Quanton) and where we need to get - so please bear with me.

One of the interesting structures is the Birkhoff polytope because it corresponds to permutations (i.e. it is what is called an extended representation of the Permutohedron). 

Given a Birkhoff polytope, for example, for 4 integers, it will encode the 24 outcomes of the permutation of the 4 integers as an extended representation of the 4-Permutohedron.  Of course, this structure, has 24 vertices, but, there are also 24! ways of choosing the ordering of vertices (in other words, there are a very large number of different Permutohedra!).

The interesting element is when the polytopes are embedded into manifolds, which could be (hyper)spherical or (hyper)torii - imagine each vertex is associated with a probability density, and tangent-density polytope is the tangent space at the vertex of the polytope associated to a probability density (the tangent space of the sphere providing a nice linear subspace if you like).

What this really is about, is precompiling a number of general relationships about a data structure, such as a certain kind of Orbitope so that the operations are effectively "parallel" across the various general relationships that are codified within the structure: to do this, it usually means you have to also come up with a way to associate a nicely computable manifold with the orbitope - that is where the hard work comes in.  However, once you can precompile an orbitope and its embedding, then some unique and powerful properties, including the ability to effectively approximate some specialized quantum operations, most notable of which are Topological Quantum Computing and the operations of braiding to build gates.

I will get into how this can be achieved as a sort of "poor-man's" surrogate for a real topological quantum computing fabric (pun intended) in which the gate processes are woven (punning again!) together to provide a computing model along the lines of permutational quantum computing.

An excercise for the reader is the following question: what orbitopes admit an analytic representation in terms of "good enough" on a manifold as embeddings for simplified calculations that are reversible?  More on this in the near future.  I have a conference talk to give and promised I would save this for later.

Quantum, Classical and Quantum Inspired Computing Revisited

Today, physical theory tend to dominate the progress in the field of quantum computing as theoretical quantum science is only really in its infancy. The basic thrust, unproven, is that real physically implemented quantum computers that run quantum algorithms will solve the computational complexity problems and open realms of possibilities beyond classical computing. Unfortunately it isn't so. 

The realms of possibilities still remain to be discovered in the classical realm, though perhaps, taking inspiration from the quantum world.

With respect to so-called pure or true quantum algorithms there are no proofs that I have found anywhere that show that any quantum algorithm will always outclass a well designed algorithm for the task.

If you want quantum-like computing then, perhaps, it will be achievable by new algorithms and methods as well as through more processor cores on a chip:  we still don't understand the dynamics of dense core communications, behaviours, quasi-chaos, distribution and access of resources in such systems.   Again, we are in our infancy.

Building a real hardware quantum computer is rife with experimental difficulties such as fault tolerance, scalability (beyond a few qubits) and a demonstration that entanglement can surmount complexity issues (since you can have classical systems that perform with quantization, superpositioning and parallelism - all that really makes purified quantum computing unique is entanglement).  Of course, some approaches, like Topological Quantum computing, promise to alleviate many issues.

But even for entanglement, we can ask if there are surrogate ideas in the form of correlation functions (not in the sense of quantum, but mimicking the fact that two observables can be strongly related) and whether or not these can be maximized in number to act-as-if there were deeper parallelism.

We suffer significant limitations even in classical complexity theory and no proofs to guide the design of algorithms for classically hard problems though there are lots of proofs for upper and lower bounds --- where we still have to innovate is in proofs about design. Proof of classical hardness is notoriously difficult and there have been many false starts but proofs about design are still non-existent (anyone out there know if this is truly the case? Any pointers welcome!).

Quantons

So in the realm of quantum-inspired, we are really forging a bridge between interconnected, strongly co-dependent data structures on which certain kinds of computations are extremely efficient and that mimic what our ideas might be about the benefits of quantum computing:  in other words, the hard work is about clever algorithm design by drawing upon analogies from the hard core science of quantum and field theoretic physics.

So what are quantons?

Well, my blog time is over for today but I promise to introduce and explore the quantum inspired concept of Quantons.

Until next time.