Generalization of quantum computing ?

This is not particularly related to quantum computing itself but rather to the notion of extending the manipulating a single value to manipulating a linear combination of such values, having the combinations denote the amplitude of measurement of a single value. One extension approach would be to consider non-linear combinations, but that's not what I mean here. I am asking what if this was generalized somehow to the linear combinations of such linear combinations ? What is the possible operations we could do in a manner similar to that of quantum computing and what useful outcomes would that mean to us ? Quantum computing allowed things not thought to be possible like sub-linear search complexity (Grover's algorithm) and others like Shor's algorithm. What would further generalizations like the proposed one allow us to do that we didn't think was possible with quantum computing ? Another research direction I may want to pursue after PhD en shaa Allah =)

Algebra view point on computation ??

Today I was trying to make a theoretical model for my peer to peer network simulator. Basically its a network of peers which is modified each loop according to certain rules (either random peer sampling or according to similarity-based clustering). The network is modeled as an adjacency matrix and to modify this matrix I may multiply it by a certain matrix; since the network is closed then it is possible to utilize a permutation matrix for that (peers exchange neighbors with each others). I also use a randomization matrix between each two operations to account for randomness in choice. So if we denote the network (adjacency matrix of the network graph) at cycle $n$ as $G(n)$, then the operation that happens in each cycle of the simulation is $$G(n+1) \leftarrow E \times R \times G(n) .$$ Where $R$ is the random permutation matrix and $E$ is the exchange matrix.

Okay, here comes an observation. Matrix multiplication is not commutative, and hence it allows us to express a sequence of operations (operators) and to express an adaptive computation. So it was fair enough to ask my self a question, non-commutativity actually added more power in this case, unlike the view common in algebras where it gets less interesting as you lose properties. So I though, what if I use Cayley-Dickson construction to make a higher algebra that is not even associative ? What would we get ? Well, I am not if this will be clear to you but I can clearly see that this allows us easily to express a tree, not just a sequence, of operations. The nature of operations might be different than a permutation or rotation, I am not sure of that, but the open question now is since a tree resembles recursion (in some sense), then could this allow us to construct a sort of universal recursive function (which would be turing-complete) ? Even more interestingly, can we construct a certain algebra in such a way to express all and only all such computations that can recognize a certain language, i.e. given a class of languages or a turing machine that recognizes them, can we construct an algebra equivalent to this machine ?

Why would this be interesting ? well, one reason that might occur to me is that if we were able to explicitly construct an algebra for $P$ and another for $NP$ then we might have another way to attack the famous $P=NP$ problem, which would then be equivalent to whether the two algebras are equivalent. This might be an interesting research direction for me, and in fact, I wrote this article as a sort of a TODO to remind me of this idea later when I finish my PhD and be able to pursue a research direction of my own. Thanks for reading and any comments or references are welcome!

The shortest sequence of bits that deterministically reveal the full state of a pseudo-random number generator

A pseudo-random number generator (PRNG) is a deterministic object, with a finite internal state, usually initialized by some short seed. The seed may be truly random. However since the PRNG has a finite state, then it will eventually start repeating the entire sequence again. A computationally limited adversary may not be able to compute the entire sequence for a given seed. However it interests me to consider the case of an all-powerful probabilistic adversary (call that adversary Eve) that is able to compute the all the possible sequences for all the possible seeds (since seeds are finite as well).

Eve has a black-box access to a PRNG, and is able to initialize it with any seed and recover the whole sequence. It doesn't know a priori the length of the sequence but lets arguably assume the existence of a method to deterministically know the sequence length given only the black-box access to the PRNG.

Then consider this following game between Alice and Eve. Alice, a computationally limited Turing machine, also has a black-box access to the same PRNG as Eve, and also has a truly random short seed (S) as input. Alice initializes the PRNG with S and then generates a sequence of bits from the PRNG, of length $\ell$. Alice then chooses any sub-sequence of length $\ell^{\prime}$ and sends it to Eve. Eve should then, using her knowledge of the PRNG, and some random coin tosses, output $S^{\prime}$, her guess of the random input of Alice. There is some probability of getting it right, over the random input of Alice, the coin tosses of Eve, given a certain PRNG and a certain $\ell^{\prime}$. Call that probability $P(S^{\prime} = S)$.

The question is then, given a certain PRNG, what is the least $\ell^{\prime}$ such that $P(S^{\prime} = S)=1$.

I don't know if this has been researched before but I am just recording the question here for me to investigate later. If you have any references if this problem has been tackled before, please share it in the comments :) Thanks.

The class scheduling problem at FCIH and Graph Theory !

The graph scheduling problem in FCIH apparently is not easy to solve. There is many classes, many subjects, student-subject relationship is complicated as it is fine-grained after the credit hours system has been deployed. This result in the schedule being unstable and modified a lot. In this article we seek to model this problem using Graph Theory and see possible solutions, or at least know the exact reason for the problem and the absolute minimum number of resources (time slots, rooms, etc.) needed.

Lets say that our undirected graph consists of vertices representing subjects, and edges representing student-subject relationship. In particular an edge $(i,j)$ is present between subjects $i$ and $j$ is there is a student taking both subjects.

We are going now to assign each vertex a "label" or a "color" representing its time slot (e.g. color$(i)=$ "4th time slot in Monday". We put a restriction that two neighboring vertices (i.e. having an edge between them: a student is taking them both) cannot have the same color; because the student taking both can not attend more than one subject in a time slot. This is the graph vertex coloring problem: given a graph, color its vertices such that no neighboring vertices have the same color. The trivial solution is to give each vertex a unique color. But this is not an interesting solution because you have limited number of color (time slots) and many subject; usually more than the number of time slots.

We might be interested in minimizing the number of colors used. The minimum number of colors needed to color a graph is called the graph's chromatic number, and computing that number is an NP-complete problem, and so there is no efficient algorithm to solve it exactly in the worst case unless P=NP. We may be interested though in a way to approximate it, there is an algorithm to approximate the chromatic number within a multiplicative factor. Notice that knowing the minimum number of colors doesn't mean we found such a coloring.