A novel linear representation for evolving matrices

Abstract

A number of problems from specifiers for Boolean networks to programs for quantum computers can be encoded as matrices. The paper presents a novel family of linear, generative representations for evolving matrices. The matrices can be general or restricted within special classes of matrices like permutation matrices, Hermitian matrices, or other groups of matrices with particular algebraic properties. These classes include unitary matrices which encode quantum programs. This representation avoids the brittleness that arises in direct representations of matrices and permits the researcher substantial control of the part of matrix space being searched. The representation is demonstrated on a relatively simple matrix problem in automatic content generation as well as Boolean map induction and automatic quantum programming. The automatic content generation problem yields interesting results; the generative matrix representation yields worse fitness but a substantially greater variety of outcomes than a direct encoding, which is acceptable when generating content. The Boolean map experiments extend and confirm results that demonstrate that the generative encoding is superior to a direct encoding for the transition matrix of a Boolean map. The quantum programming results are generally quite good, with poor performance on the simplest problems in two of the families of programming tasks studied. The viability of the new representation for evolutionary matrix induction is well supported.

Appendices

Appendix A: Results of evolving generative matrix representations

Figure 7 shows the results of evolving generative matrix representations of length 10 through 100.

Appendix B: Quantum fitness functions

For the five quantum program fitness functions discussed below, the term randomly generated pure quantum state is mentioned repeatedly; these randomly generated pure quantum states are vectors of dimension $2^{n}$, where n is the number of qubits; the real and imaginary components of each entry of these vectors are taken from a uniform distribution over the interval ($-1,1$). The entries of the vector are then divided by the $l_2$ norm of the vector so that it is normalized.

1.1 Appendix B.1: Identity problem

The goal of the algorithm for this problem is to do nothing at all. In order to properly test for this problem, a randomly generated pure quantum state is sent through a unitary matrix generated by the algorithm. The desired output state for this problem is a vector with the exact same entries as the vector before the unitary acted upon it. Solving this problem is expected to be incredibly easy and as such this test problem could be likened to the one-max problem that is often seen in other genetic algorithms.

1.2 Appendix B.2: Hadamard basis change

The goal of the algorithm for this problem is to take a quantum state that has a value of $\frac{1}{\sqrt{2^{n}}}$ in all of its entries; where n is the number of qubits in the quantum state. After the unitary is applied, it is rewarded fitness based on how high it makes the absolute value of the first entry in the vector. In terms of quantum information application, such a problem would involve switching the basis of the qubits in a quantum circuit into or out of the Hadamard basis where

$$\begin{aligned} |{+}\rangle =\left( \begin{array}{cc}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\\ \end{array}\right) \\ |{-}\rangle =\left( \begin{array}{cc}\frac{1}{\sqrt{2}} \\ \frac{-1}{\sqrt{2}}\\ \end{array}\right) \\ \end{aligned}$$

are the new zero and one bit respectively.

1.3 Appendix B.3: Amplitude problem

In this test problem, the algorithm is to take a randomly generated pure quantum state and maximize the likelihood of the initial entry with the highest amplitude. The algorithm will track this information by recording the address of the vector entry with the highest absolute value; such an address will be denoted entry j. With that recorded, the output state after the unitary operation is applied is to be a quantum state with a value of one in vector entry address j, up to a global phase factor. In terms of quantum information application, such a unitary that makes a quantum state favour a certain state of superposition could prove helpful in quantum programs that utilize quantum measurement while hoping for a specific outcome from the state after measuring it.

1.4 Appendix B.4: Entropy problem

For this test problem, the goal of the algorithm is to take a randomly generated pure quantum state. After applying the unitary, the outputted quantum state will be rewarded with higher fitness if it maximizes Shannon entropy. Within the context of quantum information, a pure quantum state that has a high Shannon entropy is in a higher state of superposition than other quantum states with less Shannon entropy.

1.5 Appendix B.5: Cloning problem

This problem was inspired by the no-cloning theorem of quantum information. The no-cloning theorem (Weigert 2009), states that there does not exist a quantum gate U such that $U(|{\psi }\rangle _{n} \otimes |{0}\rangle _{n}) = |{\psi }\rangle _{n} \otimes |{\psi }\rangle _{n}$ for arbitrary quantum states $|{\psi }\rangle$. For this test problem, the genetic algorithm will be given the zero qubit in the computational basis. A unitary created by the GBM will then be applied to it; fitness will be rewarded to a unitary that is able to make an output that can better replicate a randomly generated pure quantum state that was selected at the start of the algorithm’s run. With respect to quantum information application; the successful application of this GBM generated quantum gate could act as a sort of pseudo-cloning gate if it is ever figured out how to implement the genetic algorithm without measuring the state.