Project 1
Statistical analysis of non linearity in synthesized circuits
GOAL: From a set of results make a detailed analysis, report your results, observations and findings
In this project you are asked to do a detailed analysis of the problem space based on the structure and internal relations of quantum circuits related to an evaluation function of an evolutionary or automated design method.
Figure 1 shows an example of the evolution of a run during a search for a quantum circuit. The correct circuit was found after 1500 generations, however the important fact to notice is the evolution of both the cost and the fitness function. Big variations can be observed especially in the cost of the searched circuits for example between the 300 and 500 generation or between 800 and 900. This alone should not be considered as a local optimum because the cost of the circuit is only an optimization measure and not the main goal of this synthesis. More important is the observation that during all the run the fitness function representing the correctness of the circuit is stacked in a local minimum at 0.94. This function can be written down as:
with Error is the one-to-one comparison of the matrix of the current and the resulting circuit (see slides). Bellow we present also another function that is formulated in order to improve the convergence based on fact that during the run a simple fitness is almost constant and consequently there is a big danger of finding a local.
with Cost is the cost of the circuit according to the rule adding one point for each 2-qbit gate and 0 for each 1 qbit one. The two factors α and β are scaling the weight of error and cost evaluation in the whole fitness function. And as can be seen from the red and pink curve on the figure these factors are able to make the fitness function less or more sensitive to both of these components.
The table below shows another aspect of this problem. It represents a sequential measurement of the fitness function for one circuit by steps of parallel blocks. This means if we measure the fitness of the first block in the circuit the result is 0.8815. Then adding one more block yields a different result and adding blocks one by one, we can evaluate internal complexity and non-linearity in the circuit according to the fitness function. A closer look to this table shows similar graph as figure 1.
Circuit (blocks) / Error (3) / CostSCg / Fitness (6)
a = 0.9
b = 0.1
1 / 5/128 / 5 / 0.8815
2, 3, 4 / 18/128 / 12, 18, 24 / 0.78, 0.778, 0.777
5, 6 / 4/128 / 30, 36 / 0.875, 0.874
7 (circuit completed) / 0/128 / 42 / 1
As you can see the sequential evaluation of the circuit reveals big inconsistencies between the fitness values at each step.
Consequently an evaluation function such as (fitness or any reward function) will have tendency to fluctuate during the construction of the circuit. This is not good for searching big problem space especially because it can lead the genetic algorithm to a local optimum without ever reaching the global one. Moreover as our optimization is not only based on the correctness of the circuit but also upon its cost and its length, the fitness function mirrors a deeper value than just a pure error measure. Consequently a better understanding of this measure is crucial for the construction of automated design methods used for quantum logic synthesis.
The goal of this project is to map all the non-linearity and to classify if possible all design classes according to statistical and complexity criteria. This classification should represent the difficulty of synthesis in quantum logic. Here follows the description and some hints on how to structure your approach to this classification. You will be given a set of gates: these will be already grouped by the number of wires, and the number of gates. Consequently the first category can be either the number of wires (not recommended because of the high number of gates in such a category) or by the number of gates and the number of wires. In each gate you have to map the fitness evolution according to one or more different measures of correctness (simple fitness function, fitness function including the cost, and so on), and note some major elements characterizing each circuit. This can be for example a maximum deviation of the error between the first and the last gate, the ratio between the rising cost/fitness and so on. You are also asked to think on this problem, to generate a hypothesis and to imagine what should be the solution and the reason for such a nonlinear evolution of circuit fitness. Also finding pattern between different circuits, between components of their structures and relations between them is very important to the success of this project.
GOAL:
- Mathematical analysis of results
- Description of relation (if any) between the nonlinearity in the fitness function, the cost and the individual gates
- Suggest what kind of function or what kind of evaluation of the circuits could remove such nonlinear fitness function
- Graphical representation of the results where each point on the x-axis is fitness function, y-axis the segment in consideration and z-axis is the number of circuits