GreedyPauliOptimisation.hpp

Go to the documentation of this file.

// Copyright Quantinuum
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
 
#pragma once
 
#include <atomic>
 
#include "Transform.hpp"
#include "tket/Circuit/Circuit.hpp"
#include "tket/Clifford/UnitaryTableau.hpp"
 
namespace tket {
 
namespace Transforms {
 
namespace GreedyPauliSimp {
 
class GreedyPauliSimpError : public std::logic_error {
 public:
  explicit GreedyPauliSimpError(const std::string& message)
      : std::logic_error(message) {}
};
 
enum class TQEType : unsigned {
  XX = 0,
  XY,
  XZ,
  YX,
  YY,
  YZ,
  ZX,
  ZY,
  ZZ,
};
 
enum class PauliNodeType {
  // Pauli rotation
  PauliRotation,
  // Defines how a Pauli X and a Pauli Z on the same qubit
  // get propagated from right to left through a Clifford operator.
  PauliPropagation,
  // Conditional Pauli rotations
  ConditionalBlock,
  // Classical operation
  ClassicalNode,
  // Mid-circuit measurement
  MidMeasure,
  // Reset
  Reset,
};
 
enum class CommuteType : unsigned {
  // Both are (I)dentity
  I,
  // (A)nti-commute
  A,
  // (C)ommute and not both identity
  C,
};
 
enum class BitType : unsigned {
  READ,
  WRITE,
};
 
struct TQE {
  TQEType type;
  unsigned a;
  unsigned b;
  bool operator<(const TQE& other) const {
    return std::tie(type, a, b) < std::tie(other.type, other.a, other.b);
  }
};
 
struct Rotation2Q {
  Pauli p_a;
  Pauli p_b;
  unsigned a;
  unsigned b;
  Expr angle;
  unsigned index;
  bool operator<(const Rotation2Q& other) const { return index < other.index; }
};
 
struct CommuteInfo {
  std::vector<std::vector<Pauli>> paulis;
  // We use UnitID to differentiate between Bit and WasmState
  std::vector<std::pair<UnitID, BitType>> bits_info;
};
 
class PauliNode {
 public:
  virtual PauliNodeType get_type() const = 0;
  virtual unsigned tqe_cost() const = 0;
  virtual int tqe_cost_increase(const TQE& tqe) const = 0;
  virtual void update(const TQE& tqe) = 0;
  virtual void update(const OpType& sq_cliff, const unsigned& a);
  virtual void swap(const unsigned& a, const unsigned& b);
  virtual CommuteInfo get_commute_info() const = 0;
  virtual std::vector<TQE> reduction_tqes() const = 0;
  virtual ~PauliNode();
};
 
typedef std::shared_ptr<PauliNode> PauliNode_ptr;
 
class SingleNode : public PauliNode {
 public:
  SingleNode(std::vector<Pauli> string, bool sign);
 
  unsigned tqe_cost() const override;
 
  int tqe_cost_increase(const TQE& tqe) const override;
 
  void update(const TQE& tqe) override;
 
  std::vector<TQE> reduction_tqes() const override;
 
  std::pair<unsigned, Pauli> first_support() const;
 
  bool sign() const { return sign_; };
 
  const std::vector<Pauli>& string() const { return string_; };
 
 protected:
  std::vector<Pauli> string_;
  bool sign_;
  // extra cached data used by greedy synthesis
  unsigned weight_;
};
 
class ACPairNode : public PauliNode {
 public:
  ACPairNode(
      std::vector<Pauli> z_string, std::vector<Pauli> x_string, bool z_sign,
      bool x_sign);
 
  unsigned tqe_cost() const override;
 
  int tqe_cost_increase(const TQE& tqe) const override;
 
  void update(const TQE& tqe) override;
 
  void update(const OpType& sq_cliff, const unsigned& a) override;
 
  void swap(const unsigned& a, const unsigned& b) override;
 
  std::vector<TQE> reduction_tqes() const override;
 
  std::tuple<unsigned, Pauli, Pauli> first_support() const;
 
  bool z_sign() const { return z_sign_; };
 
  bool x_sign() const { return x_sign_; };
 
  const std::vector<Pauli>& z_string() const { return z_string_; };
 
  const std::vector<Pauli>& x_string() const { return x_string_; };
 
 protected:
  std::vector<Pauli> z_string_;
  std::vector<Pauli> x_string_;
  bool z_sign_;
  bool x_sign_;
  // extra cached data used by greedy synthesis
  std::vector<CommuteType> commute_type_vec_;
  unsigned n_commute_entries_;
  unsigned n_anti_commute_entries_;
};
 
class ClassicalNode : public PauliNode {
 public:
  ClassicalNode(std::vector<UnitID> args, Op_ptr op);
 
  PauliNodeType get_type() const override {
    return PauliNodeType::ClassicalNode;
  };
 
  unsigned tqe_cost() const override { return 0; };
  int tqe_cost_increase(const TQE& /*tqe*/) const override { return 0; };
  void update(const TQE& /*tqe*/) override { return; };
  std::vector<TQE> reduction_tqes() const override { return {}; };
  std::vector<UnitID> args() const { return args_; };
  Op_ptr op() const { return op_; };
 
  CommuteInfo get_commute_info() const override;
 
 protected:
  const std::vector<UnitID> args_;
  const Op_ptr op_;
};
 
class PauliRotation : public SingleNode {
 public:
  PauliRotation(std::vector<Pauli> string, bool sign, Expr theta);
 
  PauliNodeType get_type() const override {
    return PauliNodeType::PauliRotation;
  };
 
  Expr angle() const { return sign_ ? theta_ : -theta_; };
 
  CommuteInfo get_commute_info() const override;
 
 protected:
  const Expr theta_;
};
 
class MidMeasure : public SingleNode {
 public:
  MidMeasure(std::vector<Pauli> string, bool sign, unsigned bit);
 
  PauliNodeType get_type() const override { return PauliNodeType::MidMeasure; };
  CommuteInfo get_commute_info() const override;
  unsigned bit() const { return bit_; };
 
 protected:
  const unsigned bit_;
};
 
class ConditionalBlock : public PauliNode {
 public:
  ConditionalBlock(
      std::vector<std::tuple<std::vector<Pauli>, bool, Expr>> rotations,
      std::vector<unsigned> cond_bits, unsigned cond_value);
 
  unsigned tqe_cost() const override;
 
  int tqe_cost_increase(const TQE& tqe) const override;
 
  void update(const TQE& tqe) override;
 
  std::vector<TQE> reduction_tqes() const override { return {}; };
 
  std::vector<unsigned> cond_bits() const { return cond_bits_; };
  unsigned cond_value() const { return cond_value_; };
 
  PauliNodeType get_type() const override {
    return PauliNodeType::ConditionalBlock;
  };
 
  CommuteInfo get_commute_info() const override;
 
  void append(const ConditionalBlock& other);
 
  const std::vector<std::tuple<std::vector<Pauli>, bool, Expr>>& rotations()
      const {
    return rotations_;
  };
 
 protected:
  std::vector<std::tuple<std::vector<Pauli>, bool, Expr>> rotations_;
  const std::vector<unsigned> cond_bits_;
  const unsigned cond_value_;
  // extra cached data used by greedy synthesis
  unsigned total_weight_;
};
 
class PauliPropagation : public ACPairNode {
 public:
  PauliPropagation(
      std::vector<Pauli> z_string, std::vector<Pauli> x_string, bool z_sign,
      bool x_sign, unsigned qubit_index);
 
  PauliNodeType get_type() const override {
    return PauliNodeType::PauliPropagation;
  };
 
  CommuteInfo get_commute_info() const override;
 
  unsigned qubit_index() const { return qubit_index_; };
 
 private:
  const unsigned qubit_index_;
};
 
class Reset : public ACPairNode {
 public:
  Reset(
      std::vector<Pauli> z_string, std::vector<Pauli> x_string, bool z_sign,
      bool x_sign);
 
  PauliNodeType get_type() const override { return PauliNodeType::Reset; };
  CommuteInfo get_commute_info() const override;
};
 
typedef boost::adjacency_list<
    boost::listS, boost::listS, boost::bidirectionalS,
    // indexing needed for algorithms such as topological sort
    boost::property<boost::vertex_index_t, int, PauliNode_ptr>>
    GPDAG;
 
typedef boost::graph_traits<GPDAG>::vertex_descriptor GPVert;
typedef boost::graph_traits<GPDAG>::edge_descriptor GPEdge;
 
typedef sequence_set_t<GPVert> GPVertSet;
typedef sequence_set_t<GPEdge> GPEdgeSet;
 
typedef boost::adj_list_vertex_property_map<
    GPDAG, int, int&, boost::vertex_index_t>
    GPVIndex;
 
class GPGraph {
 public:
  GPGraph(qubit_vector_t qubits, bit_vector_t bits);
 
  GPVertSet get_successors(const GPVert& vert) const;
 
  GPVertSet get_predecessors(const GPVert& vert) const;
 
  std::vector<GPVert> vertices_in_order() const;
 
  std::tuple<
      std::vector<std::vector<PauliNode_ptr>>, std::vector<PauliNode_ptr>,
      boost::bimap<unsigned, unsigned>>
  get_sequence(std::shared_ptr<std::atomic<bool>> stop_flag);
 
  void apply_gate_at_end(
      const Command& cmd, bool conditional = false,
      std::vector<unsigned> cond_bits = {}, unsigned cond_value = 0);
 
 private:
  void apply_paulis_at_end(
      const std::vector<std::pair<std::vector<Pauli>, Expr>>& rotations,
      const qubit_vector_t& qbs, bool conditional = false,
      std::vector<unsigned> cond_bits = {}, unsigned cond_value = 0);
 
  void apply_node_at_end(PauliNode_ptr& node);
 
  mutable GPDAG graph_;
  const unsigned n_qubits_;
  const unsigned n_bits_;
 
  UnitaryRevTableau cliff_;
  boost::bimap<unsigned, unsigned> end_measures_;
 
  GPVertSet start_line_;
  GPVertSet end_line_;
};
 
std::tuple<std::vector<PauliNode_ptr>, std::vector<PauliNode_ptr>>
gpg_from_unordered_set(const std::vector<SymPauliTensor>& unordered_set);
 
Circuit greedy_pauli_graph_synthesis_flag(
    const Circuit& circ, std::atomic<bool>& stop_flag,
    double discount_rate = 0.7, double depth_weight = 0.3,
    unsigned max_lookahead = 500, unsigned max_tqe_candidates = 500,
    unsigned seed = 0, bool allow_zzphase = false);
 
Circuit greedy_pauli_graph_synthesis(
    const Circuit& circ, double discount_rate = 0.7, double depth_weight = 0.3,
    unsigned max_lookahead = 500, unsigned max_tqe_candidates = 500,
    unsigned seed = 0, bool allow_zzphase = false);
 
Circuit greedy_pauli_set_synthesis(
    const std::vector<SymPauliTensor>& unordered_set, double depth_weight = 0.3,
    unsigned max_lookahead = 500, unsigned max_tqe_candidates = 500,
    unsigned seed = 0, bool allow_zzphase = false);
 
}  // namespace GreedyPauliSimp
 
Transform greedy_pauli_optimisation(
    double discount_rate = 0.7, double depth_weight = 0.3,
    unsigned max_lookahead = 500, unsigned max_tqe_candidates = 500,
    unsigned seed = 0, bool allow_zzphase = false,
    unsigned thread_timeout = 100, unsigned trials = 1);
 
}  // namespace Transforms
 
}  // namespace tket