Page of "EPIG" - the Evolutionary Pseudo-genetIc loGic synthesizer

NEWS and Timeline

• There is a Bug in the Synthesizer - will be fixed soon. When synthesizing circuits with 3 qubits or less it goes into a segmentation fault. This is due to the Accelerated Kronecker Product. The Kronecker Product is Matrix Sizes dependent and cannot handle such a small sizes.

• More configuration options have been added. run ./configure --help for the full list of options.
• All operations on matrices now can be done on CUDA (matrix multiplication, kronecker multiplication, vector-matrix multiplication)
• The plan is to externalize the CUDA-quantum matrix manipulation and add Matrix inversion directly on CUDA

• Format of the input file completely changed (Check it out).
• More of multivalued stuff added
• Two new features are added: forcing to go away from the Identity local minimum and the option to search for a complete match

• EpiG now allows to synthesize one-way QFMS
• In preparation Quantum boolean synthesis using multivalued quantum gates

The Evolutionary Synthesizer is now available for multivalued logic synthesis. The synthesizer allows now to design quantum or only permutative circuits for

• Single output completely defined functions
• Single output incompletely specified function.

• Multi-qubit measurement synthesis available for MPI clusters now.

The Evolutionary Synthesizer is now split to the follwing directions

• The primitive synthesiser - evolving n qubit circuits by comparing the unitary matrices of the unitary transformation.
• The (single qubit evolutionary synthesiser) SQES allows to evolve circuits for a single qubit output function. The output can be iether measured or not.
• The (mulit qubit evolutionary synthesiser) MQES allows to evolve multi-output quntum functions using Projective measurement. The process of measurement can be configured to behave as a more-general POVM.

Finally, the first release version 0.1rc of epig is available. It has upgraded reporting output (all local optima, error, fitness and cost reporting for up to 100000 generations). Multi-qubit measuremenets, partially defined function, etc.)

fully multithreaded upgraded with improved evaluation, controllable and fully adjustable measurement evaluation, incompletely specified functions, multiple fitness functions, and more.

• Added pulses, now mixed models (hardware and logic) can be synthesized.

• The synthesizer now can search for partially defined circuits in the matrix form.

Bugs solved and optimized version is provided. New features added: multi character gates encoding allowing the input size of the gates to be almost arbitrarily large. The practical limit is 128^3 ~ 2,000,000 gates as input.

October 10/09

some bugs have been discovered that creates problems during compilation for 64 or 32 bit version. If you experience any bugs please check back soon as it is being resolved currently

September 09/09

Bug fixes versions remained the same. Also a script circuitdecoder.pl was added (in the source distribution) that converts a given result file to both a readable format , to a circuit in the qcircuit format for LaTex as well as to a form that when proper macros are loaded to octave allows to calculate the matrix of the circuit.

General Information:

Portland Quantum Evolutionary Logic Synthesizer is a automated system for quantum circuit synthesis and optimization using evolutionary searh techniques. It is a Genetic Algorithm with various optimization functions and prameters. The idea is that as long as we can represent quantum circuit as a string of litterals we can apply classic genetic operators such as crossover of mutationi to binary individual allele.

Requirements:

• Most of Linux variants with recent kernel and stdlibs, POSIX threads and MPI(openMPI, MPICH, MPICH2, LAMMPI) if required.
• CUDA Libraries. Only CUDA libraries are required when acceleration on a GPU is not used. Otherwie both CUDA and CUDA SDK are required. minimum verion is 2.1
• the GSL (Gnu Scientific Libraries) containing the CBLAS interface to BLAS
• are required binaries are provided for x686, x86_64
• Good machine, Opteron, Athlon (> 2Ghz), dual Core or so.
• some 10 MB of HDD space and 250 MB of memory (per compute thread in the case of the MPI version).
• For HPC CUDA enbaled device with lots of memory
• Perl interpreter if you wants to run any of the helper scripts

Operational parts:

• CUDA acceleration - two version CUBLAS accelerated and NATIVE CUDA implementation.
• Quantum Finite State Machines Synthesis for Sequence Detection (only 1 - way QFSM's available now)

• Evolutionary Synthesizer
• Exhaustive search for local search - only used if results are not found after defined number of generations
• Synthesis for 2, 3 and 4 (tested for up to 6 on specific benchmarks) qubit circuits.
• Specific parametraization for groups of primitives - Single Qubit Gates, Two Qubit Gates, User Defined Macros, User Defined Gates, Multivalued/Binary.
• Don't care allowed - both in Matrix and Measurement Evaluation.
• Global and Local phases can be allowed during synthesis process.
• MPI version for multiple qubit synthesis allowing multi-qubit measurements
• Elitism and Threshold selection, Multi-qubit Measurement, Multi-Valued Measurements, Don't Cares.

Parts in development:

-- Bugfixes

Installation:

• download and unpack the package in a desired directory
• VERY IMPORTANT STEP:
  • Right now the GA and CUDA are configured to accept only binary or ternary logic. In order to use binary logic the Header file must initialize the BLOCK_SIZE to 2 and the BLOCK_MAX_SIZE to 16. If you want ternary logic change these variables to 3 and 9 respectively. It is possible to increase the BLOCK_MAX_SIZE to larger values but it depends on the size of the Memory on your GPGPU graphics card.
• run ./confgure --help and decide the options you desire. The required options are
  • --with-gslblas=path_to_gslblas
  • --with-cudart=path_to_cuda
  • The two above options alone will trigger the compilation of non accelerated EpiG using gsl. The CUDA libraries are used because the overall typesetting is using the cuda types.
  • By default the compilation will generate a 32 bit binary. If you wants to have a 64 bit binary edit the configure.in file and change AC_SUBST(BITAGE, "32") to AC_SUBST(BITAGE, "64")
  • Optional parameters are
    • --with-cudasdk=path_to_cuda_sdk, this option will trigger the compilation of a GPU accelerated software.
    • --with-stdr - switch to force the build to be done for standard release - maximum memory allocation - advised
    • --with-mpi=path_to_mpi - this option turns on mpi however with the addition of the CUDA libraries it has not been fully tested as of yet
    • --with-qmdd= path to the qmdd package. will trigger the QMDD based representation. By default should not be used with the --with-cudasdk option as well as the -m64 option as it will not compile due to addressing problems.
    • --prefix= path to a non standard installation folder (default /usr/local)
  • run ./configure [options] && make && make install
  • in the input/ folder are sets of input files. Look at them and be sure you pick up one with the righ amount of options otherwise the program will crash.
  • run epig [input_file] [output_path]

  some of the above parameters are not compatible thus let me know if something does not work

Usage:

the software comes in binary form. It runs directly from console. It takes one input file called 'gates.inn' which must be located in the same dirctory. The output file is automatically generated uwing the starting time as time stamp. the input file allows to configure the GA and is explained below.

The current version of the EpiG Quantum/reversible Logic synthesizer allows to design quantum circuits in these categories:

• single qubit quantum circuit synthesis

  The single qubit quantum logic synthesizer has all the features required to synthesise arbitrary completely or incompletely specified circuit (as long as it can be realized as reversible/quantum circuit - however ancilla bits can be specified) using either Matrix or Measure evaluation.

• multiple qubit quantum circuit synthesis

  The multiple qubit quantum logic synthesizer was built as a separate engine in order to optimize the code for multi-qubits operations and Measurement. This code is designed for a Cluster Processing using the MPI libraries for parralel computing.

• multivalued single qubit quantum circuit synthesis

  The multivalued logic synthesis (quantum systems with more than 2 states/qubit) is an extension of the qubit synthesiser to multi-valued observable quantum circuits. In order to design multivalued gates it is required all gates whether they are or not multivalued are embeded in the multi-valued space. this means that if one wants to design ternary circuits all gates must be 3^n * 3^n. To design a boolean logic in a multivalued specifications, specify the desired measurements or the input-output transitiosn only where desired.

• Quantum Finite State Machines specified by a quantum circuit and a sequence to be detected.

New Configuration :

This section explains the new (epig version > 1.2.4) input and conifugration file.

First, the folder input/ now contains two types of file: .inn and .par.

• The .inn file contains either a set of parameters for finding a particular function or a set of gates. There are three files with gates called gates.inn, gates3.inn and rotations.inn. The rest of files with postfix .inn are function definition files.
• The .par files contains the set of parameters to configure the GA. Each parameter is now prefixed by its name so it should be easy to understand which parameter stands for what feature.
• To run the EPIG program one needs to take the .par file and copy into it where indicated a set of gates. any number of gates can be inserted but the first inserted element must always be the total number of inserted gates. Once this is done, you should decide what you want to search for.
  • To do a matrix-based circuit search configure the number of desired wires, the valuedness of the logic (it must correspond to the used gates), if yes or no to push the circuit away form the Identity minimum, if yer or no to search for exact compariosn, etc. For this after configuring the GA, you must provide the desired gate in either a matrix form or in a cube/minterm form. To specify the output in the matrix form, look at the end of the file parameters.par. At the bottom is the matrix of the desired file, preceded by a 0 (should stay 0) and by 3 - the resulting number of circuit wires. Modify it so that it describes the function you are looking for and modify as well the number of wires if required. If you want to specify the resulting circuit in a cube form, open for instance the file 'major_2_qbts.inn' and replace the resulting matrix and the two parameters at the end of the file by the content of the file 'major_2_qbts.inn'. Each desired cube is specified by a pair of integers representing the input and the output (semi-column separated) state bit-encoded followed (column separated) by the probability of the output.
  • To do a measurement-based search configure the number of desired wires, the valuedness of the logic (it must correspond to the used gates), if yes or no to push the circuit away form the Identity minimum,etc. For this after configuring the GA, you must provide the desired gate in the form of measured output cubes. This can be seen in the file 'parameters.par' right above the '------' separator. The important lines for this configuration are the: use-measurement that indicates how many qubits you want to measure, measured-wires that indicates which wires you measure (indexes starting from 0) and measured samples that indicates how many measured results are you interested in. The measured results are shown as below these parameters. Each line represent a bit-encoded input (the first digit), and an qubit-measurement encoded output for each measured qubit. Observe that each qubit is given by a set fo two complex numbers representing the observation probabilities for |0> and |1> (in the cse of boolean quantum logic). Each qubit is separated by a coma.
  • To do an evolutionary search of sequential machines (1-way, many-measure quantum sequence detectors) the option sequential-synthesis must be set to 1, use-measurement must be 1 and measured-wires should be 0. To define a sequence open the file seq_detect_7_qbts_r.inn and look on how a sequence is defined. Each character in the sequence is either a 0 or a 1 and is followed by a probability of observation. The measured-sample variable must indicate the exact length of this sequence.
• now run the program by typing something like ./epig /path/to/config/file /path/to/output/dir'

Old Configuration :

- The following table explains the old (up to the version 1.2.4 of epig) configuration file and the parameters it contains: (Similar comments are generated as output byt the program). this table is working only for Epig of 2.1 and higher. Older version will not wok as new parameters have been added to the file. Examples of input data files are provided in the input directory of the compiled software - get it in the download section - or check these two-qubit combinatorial circuit synthesis input file, three-qubit combinatorial circuit synthesis input file, one-way circuit-based QFSM synthesis input file