qgame++.cpp

/***************************************************************************
 *   QGame++                                                               *
 *   =======                                                               *
 *   A Quantum Gate And Measurement Emulator.                              *
 *                                                                         *
 *   Copyright (C) 2003/04 by Manuel Nickschas                             *
 *   <qgame-devel@nickschas.de>                                            *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program 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 General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/

#include "qgame++.h"

using namespace std;
using namespace qgame;

ostream & qgame::operator<<(ostream &o, const Result &r) {
  o << "Misses: " << r.misses << endl;
  o << "Max error: " << r.maxError << endl;
  o << "Average error: " << r.avgError << endl;
  o << "Max expected oracles: " << r.maxExpOracles << endl;
  o << "Average expected oracles: " << r.avgExpOracles << endl;
  return o;
}
  

QSys::QSys() {
  prg = NULL;
  numQubits = 0;
  oracleTT = "";
}

QSys::~QSys() {
  delete prg;
}

void QSys::init (int numqb, QProgram *p, const string &tt) {
  prg = p;
  instrPnt = 0;
  oracleTT = tt;
  prob = 1;
  numQubits = numqb;
  reg = Qureg(numqb);
  prg->installOracle(tt);
  oracleCount = 0;
  execInstr.clear();
  measureHistory.clear();
  execInstr = vector<bool>(p->length(), true);
};

void QSys::setReg(const Qureg &r) {
  reg = r;
}

Qureg QSys::getReg() {
  return reg;
}

double QSys::getProb() {
  return prob;
}

void QSys::setProb(double p) {
  prob = p;
}

int QSys::getOracleCount() {
  return oracleCount;
}

void QSys::appendMeasurement(QubitList q, int outcome, double prob) {
  Measurement m;
  m.qubit = q[0];
  m.result = outcome;
  m.prob = prob;
  measureHistory.push_back(m);
}

QSys *QSys::clone(double p) {
  QSys *res = new QSys;
  res->prob      = p;
  res->instrPnt  = instrPnt;
  res->prg       = prg;
  res->oracleTT  = oracleTT;
  res->numQubits = numQubits;
  res->reg       = reg;
  res->oracleCount = oracleCount;
  res->execInstr = execInstr;
  res->measureHistory = measureHistory;
  return res;
}

void QSys::apply(QGate *gate, const QubitList &qubits) throw(Error) {
  if(gate->numQb() != qubits.size()) throw(Error(E_MISMATCH));
  vector<QuSubReg> subregs = reg.getSubRegs(qubits);
  for(int sr = 0; sr < subregs.size(); sr++) {
    gate->apply(subregs[sr]);
  }
}

void QSys::apply(const QInstr &instr) throw(Error) {
  if(!instr.gate) return;
  if(instr.type == ORACLE) oracleCount++;
  else if(instr.type == LIMITED_ORACLE) {
    if(oracleCount >= instr.extra) return;
    else oracleCount++;
  }
  apply(instr.gate, instr.qubits);
}

vector<QSys*> QSys::execute(int numqb, QProgram *p, const string &tt) throw(Error) {
  QSys *sys = new QSys;
  sys->init(numqb, p, tt);
  return sys->exec();
}

vector<QSys*> QSys::exec() throw(Error) {
  vector<QSys*> result;
  bool term = false;
  while(!term && instrPnt<prg->length()) {
    if(!execInstr[instrPnt]) { instrPnt++; continue; }
    QInstr *instr = (*prg)[instrPnt];
    if(instr->gate) {
      //cerr << "\napplying: "<< *instr;
      apply(*instr);
      instrPnt++;
    } else {
      instrPnt++;
      switch(instr->type) {
        case MEASURE: {
          vector<double> probs = reg.getProbabilities(instr->qubits);
          QSys *ifsys = NULL;
          QSys *elsys = NULL;
          if(probs[0]>0) elsys = this;
          if(probs[1]>0) {
            if(elsys) ifsys = clone(prob);
            else ifsys = this;
          }
          if(ifsys) { 
            ifsys->reg.collapse(instr->qubits, 1);
            ifsys->setProb(ifsys->getProb() * probs[1]);
            ifsys->appendMeasurement(instr->qubits, 1, probs[1]);
          }
          if(elsys) {
            elsys->reg.collapse(instr->qubits, 0);
            elsys->setProb(elsys->getProb() * probs[0]);
            elsys->appendMeasurement(instr->qubits, 0, probs[0]);
          }
          /* mark the appropriate branches as invalid by setting the execInstr[] flag to false */
          int i = instrPnt;
          int d = 0; 
          bool flg = false; bool branch = true;
          QSys *curSys = elsys;
          while(!flg && i<prg->length()) {
            if(curSys) curSys->execInstr[i] = false;
            switch((*prg)[i]->type) {
            case MEASURE:   // handle nested measurements
              d+=2; break;
            case END:
              if(d>0) d--;  // belongs to a nested measurement -> ignore
              else {
                if(branch) {
                  if(elsys) elsys->instrPnt = i+1;
                  if(!ifsys) flg = true;
                  else { branch = false; curSys = ifsys; }
                } else flg = true;  // we are done with marking...
              }
              break;
            }
            i++;
          }
          if(ifsys && elsys) {
            vector<QSys*> ifRes = ifsys->exec();  // execute if-branch
            for(int r = 0; r<ifRes.size(); r++) result.push_back(ifRes[r]);
          }
          break;
        }
        case HALT:
          term = true;
          break;
          
        case ORACLE:
          throw(Error(E_NOORACLE));
          break;
        
        case PRINTAMPS:
          //cout << "\nQuReg contents after measuring";
          //for(int i = 0; i<measureHistory.size(); i++) {
          //  cout << "\n  q" <<measureHistory[i].qubit << " = " << measureHistory[i].result
          //       << " (p = " << measureHistory[i].prob << ")";
          //}
          //cout << "\n" << reg;
          cout << *this;
          break;
        //default:
          
      }   
    }
  }
  result.push_back(this);
  return result;
}

Result QSys::testProgram(int numqb, QProgram *p, const std::vector<TestCase> &cases, 
                    const QubitList &finm, double thresh) throw(Error) {
  Result res;
  res.misses = 0;
  res.avgError = res.avgExpOracles = res.maxError = res.maxExpOracles = 0;
  double totalErr = 0;
  double totalExpOracles = 0;
  for(int c = 0; c < cases.size(); c++) {
    TestCase tcase = cases[c];
    vector<QSys*> systems = execute(numqb, p, tcase.oracleTT);
    double expOracles = 0;
    double rawerr = 1.0;
    for(int s=0; s<systems.size(); s++) {
      rawerr -= systems[s]->getReg().getProbabilities(finm)[tcase.desiredRes] * systems[s]->getProb();
      expOracles += systems[s]->getProb() * systems[s]->getOracleCount();  
    }
    if(rawerr<-0.000000001) { cerr << "\nWARNING: rawerr = "<<rawerr; } // DEBUG
    if(rawerr>thresh) res.misses++;
    totalErr += rawerr;
    if(rawerr > res.maxError) res.maxError = rawerr;
    totalExpOracles += expOracles;
    if(expOracles > res.maxExpOracles) res.maxExpOracles = expOracles;
  }
  res.avgError = totalErr / cases.size();
  res.avgExpOracles = totalExpOracles / cases.size();
  return res;
}

ostream& qgame::operator<<(std::ostream &o, const QSys &s) {
  o << "\n========================================================================";
  o << "\nQSys ("<<s.numQubits<<" qubits, prior prob = "<<s.prob<<")\n";
  o << "\nMeasurement History:";
  
  for(int i = 0; i<s.measureHistory.size(); i++) {
    o << "\n   q" <<s.measureHistory[i].qubit << " = " << s.measureHistory[i].result 
         << " (p = " << s.measureHistory[i].prob << ")";
  }
  o << "\nRegister:" << s.reg << "\n";
  
  return o;

}

/*****************************************************************************
 * Documentation - To be used by Doxygen. Please see the autogenerated
 * docs in the doc/ subdir for a formatted version of this ;-)
 *****************************************************************************/

---