OAI/Computability/QuantumFactoring/OccurrenceQueue.lean

GitHub source file

17 declarations, 0 contain sorry, 0 declared as axioms

  1. def OAI.ExactQuantumFactoring.AuxiliaryTree.preorder line 19

    Source documentation

    The full occurrence preorder; equal labels under different parents are retained as different list elements. This is only a correctness invariant, never used as the modulus-input physical circuit's initializer.

    def preorder (m : ℕ) : List ℕ :=
…
  2. lemma OAI.ExactQuantumFactoring.AuxiliaryTree.preorder_eq line 24
  3. lemma OAI.ExactQuantumFactoring.AuxiliaryTree.visits_eq_preorder line 29
  4. lemma OAI.ExactQuantumFactoring.AuxiliaryTree.preorder_length_le line 40
  5. lemma OAI.ExactQuantumFactoring.AuxiliaryTree.preorder_nonempty line 45
  6. def OAI.ExactQuantumFactoring.AuxiliaryTree.forest line 49
  7. def OAI.ExactQuantumFactoring.AuxiliaryTree.advance line 51
  8. lemma OAI.ExactQuantumFactoring.AuxiliaryTree.forest_advance line 55
  9. lemma OAI.ExactQuantumFactoring.AuxiliaryTree.queue_length_le line 59
  10. def OAI.ExactQuantumFactoring.AuxiliaryTree.run line 70
  11. lemma OAI.ExactQuantumFactoring.AuxiliaryTree.forest_run line 74
  12. lemma OAI.ExactQuantumFactoring.AuxiliaryTree.forest_eq_nil_iff line 83
  13. theorem OAI.ExactQuantumFactoring.AuxiliaryTree.run_complete line 94

    Source documentation

    Exactly the polynomial clock used by the physical queue suffices for EVERY occurrence, not just every distinct label.

    theorem run_complete {m n : ℕ} (hm : 2 ≤ m) (hb : m < 2^n) : run (2*n^2) [m]=[] := by
…

    Mentions: OAI.ExactQuantumFactoring.AuxiliaryTree.run

  14. lemma OAI.ExactQuantumFactoring.AuxiliaryTree.run_queue_length line 101
  15. lemma OAI.ExactQuantumFactoring.AuxiliaryTree.advance_bounds line 109
  16. lemma OAI.ExactQuantumFactoring.AuxiliaryTree.run_bounds line 121
  17. lemma OAI.ExactQuantumFactoring.AuxiliaryTree.run_succ_right line 127