Schrodinger graph construction is O(layers^2): every append front-inserts into a std::vector

[robertodr]

🤖 AI text below 🤖

What

In the Schrödinger picture every graph layer is inserted at the front of a std::vector, making
graph construction quadratic in the layer count.

cpp/include/monoprop/MPGraph.h:56-58

auto append_position() -> LayerIterator {
    return schrodinger_ ? active_begin_iterator() : active_end_iterator();
}

auto append_layer(Layer layer) -> void { layers_.emplace(append_position(), std::move(layer)); }

active_begin_iterator() is layers_.begin() + front_offset_, so each Schrödinger append
move-assigns every layer already in the vector.

Why this is a problem

Layer (cpp/monoprop/detail/graph/MPGraphLayers.h) is a shared_ptr<const LayerCore> plus an
optional<CosMask>, and CosMask owns a vector<pair<size_t, uint64_t>> — so each move is a real
move-assignment, not a memmove. Building an L-layer Schrödinger graph therefore costs
L(L-1)/2 move-assignments:

layers	move-assignments
1 000	~5·10^5
10 000	~5·10^7
100 000	~5·10^9

Heisenberg appends at the back and is unaffected, so this only bites deep Schrödinger-picture
circuits — but those are exactly the ones where layer counts get large.

Suggested fix

Change layers_ to std::deque<Layer> and push at the appropriate end. Touch points:

• cpp/include/monoprop/MPGraph.h — the LayerIterator/ConstLayerIterator typedefs, the
  std::vector<Layer> constructor overload, append_layer.
• cpp/monoprop/detail/graph/MPGraphViews.h:57,78 — MPGraphView's container reference and pointer.
• cpp/monoprop/MPGraph.cpp — maybe_compact_layers:33 (deque erase from the front is already
  cheap), slice_graph:61, and storage_memory_usage, which uses layers_.capacity(); a deque has
  no capacity(), so use size().
• cpp/monoprop/detail/pare/PareGraph.cpp:119 and cpp/tests/mp_graph_tests.cpp:120, which build a
  std::vector<Layer> to hand to the MPGraph constructor.

Alternative considered and not recommended. Always push_back and reverse on read, reusing the
reverse_ flag MPGraphView already has. This is a smaller diff on paper but riskier: every
MPGraph::get_layer(i) caller assumes index 0 is first-in-replay-order — graph_gate_arrays_,
set_parameter_mapping, n_gates, cos_index_count_, graph_data, build_cos_callbacks — and each
would need its indexing inverted for the Schrödinger case. Prefer the deque.

Verification

• Time build_graph on a deep Schrödinger circuit (a few thousand layers) before and after; the curve
  should flatten from quadratic to linear.
• just test, just test-mpi "1;2;4", just test-wide — this touches graph storage, which the MPI
  and wide-index legs both cover.

---

Found by a code-reading review of the repository at 29a8050. No build tree was available, so the
analysis is from source inspection and should be confirmed by measurement.