// Copyright (c) 2012 Vadym Kliuchnikov sqct(dot)software(at)gmail(dot)com, Dmitri Maslov, Michele Mosca
//
// This file is part of SQCT.
//
// SQCT is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// SQCT is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with SQCT. If not, see .
//
#ifndef OPTSEQUENCEGENERATOR_H
#define OPTSEQUENCEGENERATOR_H
#include "matrix2x2.h"
#include
#include
#include
#include
/// \brief Node of a Breadth First Search tree
struct optNode
{
int gen_id; ///< id of unitary used to get this node
const optNode* parent; ///< parent of the node
matrix2x2 unitary; ///< value of the node
int cost; ///< total cost of the circuit required to get the node
};
/// \brief Node of priority queue used in Breadth First Search
struct pqoptNode
{
const optNode* node;
int cost;
};
/// \brief Order on priority queue nodes base on cost
struct pqoptNodeCompare
{
bool operator() ( const optNode* a , const optNode* b ) const
{
return a->cost > b->cost;
}
};
/// \brief Order on BFS nodes base on order of unitaries that they contain
struct optNodeCompare
{
typedef std::shared_ptr ptr;
bool operator() ( const ptr& a, const ptr& b) const
{
return a->unitary < b->unitary;
}
};
/// \brief Uses Breadth First Search (BFS) to find optimal sequences generated by a set of
/// gates, starting from sode initial unitaries with given cost
class optSequenceGenerator
{
public:
/// \brief Matrix type used to store found unitaries
typedef matrix2x2 m;
std::vector m_generators;///< Unitaries from gate library that is used
std::vector m_cost; ///< Cost assosisated with each generator
std::vector m_initial; ///< Initial unitaries ( root(s) of BFS tree(forest) )
std::vector m_initial_cost;///< Cost of each initial element
typedef std::priority_queue< const optNode* ,std::vector< const optNode*>,pqoptNodeCompare> pq;
typedef std::shared_ptr nodeptr ;
/// \brief Type of set of all found elements
typedef std::set< nodeptr ,optNodeCompare> nset;
optSequenceGenerator();
/// \brief Function that is called for all unique unitaries found.
/// If function returns true BFS will stop
virtual bool processMatrix( const optNode& val, int counter );
/// \brief Runs BFS until priority queue is empty or processMatrix returns true
void generate();
virtual ~optSequenceGenerator();
/// \brief Returns set of all unique elements found
const nset& unique_elements() const;
private:
nset m_set;///< set of all unique elements
pq m_pq; ///< priority queue used during BFS
};
/// \brief Breadth First Search (BFS) that gathers statistics of
/// \f$ sde(|\cdot|^2) \f$ of found elements and terminates
/// when requested quantity of unitaries with given values of
/// \f$ sde(|\cdot|^2) \f$ was found.
class optSequenceGeneratorSdeLim : public optSequenceGenerator
{
public:
/// \brief Upper bound of \f$ sde(|\cdot|^2) \f$
static const int max_sde = 100;
/// \brief Number of found unitaries per \f$ sde(|\cdot|^2) \f$
std::vector m_sde_found;
/// \brief Number of requested unitaries per \f$ sde(|\cdot|^2) \f$
std::vector m_sde_required;
/// \brief Minimal cost of found unitaries per \f$ sde(|\cdot|^2) \f$
std::vector m_min_cost;
/// \brief Maximal cost of found unitaries per \f$ sde(|\cdot|^2) \f$
std::vector m_max_cost;
optSequenceGeneratorSdeLim() :
m_sde_found( max_sde ),
m_sde_required( max_sde ),
m_min_cost( max_sde, max_sde * 4000 ),
m_max_cost( max_sde, -1 )
{}
/// \brief Updates statistics per \f$ sde(|\cdot|^2) \f$ and terminates
/// search when all requested unitaries were found
virtual bool processMatrix( const optNode& val, int counter );
};
#endif // OPTSEQUENCEGENERATOR_H