Skip to content

Add measurement-based decomposition to Adjoint(QROMLoad) and Adjoint(SelectSwap) - #10363

Open
dwierichs wants to merge 55 commits into
split-qromfrom
adj-qrom-decomp
Open

dwierichs wants to merge 55 commits into
split-qromfrom
adj-qrom-decomp

Conversation

@dwierichs

@dwierichs dwierichs commented Oct 21, 2026 •

Copy link
Copy Markdown
Contributor

Context:
We can un-load a QROMLoad with measurement-based uncomputation, and that will be cheaper than re-loading it.
This method is described in App. C in Berry et al. https://arxiv.org/abs/1902.02134.

We can also un-load a garbage-state producing loading op, namely SelectSwap, with a variation of this that measures out the swap wires as well.

Description of the Change:
Add new decompositions to Adjoint(QROMLoad) and Adjoint(SelectSwap) that use this technique.

Benefits:
Cheaper decompositions.

Possible Drawbacks:

Related GitHub Issues:

Comment thread pennylane/templates/subroutines/qrom.py Resolved
Comment thread pennylane/templates/subroutines/qrom.py Resolved
@dwierichs
dwierichs marked this pull request as ready for review October 22, 2026 13:07
dwierichs and others added 5 commits October 23, 2026 14:51
…its Catalyst tests

Split out of #10363. Prepared with the help of an AI assistant.

Co-authored-by: Cursor <cursoragent@cursor.com>
Base automatically changed from ppm-qrom-resources to main October 28, 2026 15:14
G26karthik pushed a commit to G26karthik/pennylane that referenced this pull request Oct 29, 2026
**Context:**
Split out of PennyLaneAI#10363. 
We have a PPM-based decomposition rule for `QROM` but it does not report
its resources faithfully (even when acknowledging that we set
`exact=False`).

- Not all sizes of PPMs that can occur in the decomposition (they depend
on the `bitstrings` data) are included in the resources.
- The control logic is not reported correctly

**Description of the Change:**
- Rework `_qrom_measurement_resources`: count CNOTs per iterator
variant, count the flag-gated load as a controlled `MultiX`, include the
adjoint of the flag `X`, and spread the X-type joint measurements
binomially over their widths instead of assuming the worst-case width.
- Simplify `_flag_resources` accordingly.
- Remove the `pl2do` markers from the Catalyst tests, xfail the one case
blocked by PennyLaneAI/catalyst#3366 and PennyLaneAI/catalyst#3376, and
make `test_no_phases_error` compare the full state.

**Benefits:**
Resource estimates that match the decomposition.

**Possible Drawbacks:**
The widths of the X-type measurements are an estimate that assumes
uniformly random bitstrings We will only be able to fix this once we
have an umbrella op for flexible-sized PPMs.


This PR was prepared with the help of an AI assistant.

---------

Co-authored-by: Cursor <cursoragent@cursor.com>
@dwierichs
dwierichs marked this pull request as draft October 29, 2026 18:26
Port the measurement-based uncomputation from Appendix C of arXiv:1902.02134
onto `Adjoint(QROMLoad)` after splitting `QROM` into `QROM` and `QROMLoad`.
The fixup lookup is a plain `QROM` and receives all remaining work wires.

This commit was authored with the help of an AI assistant (Cursor).

Co-authored-by: Cursor <cursoragent@cursor.com>
@dwierichs
dwierichs changed the base branch from main to split-qrom November 10, 2026 10:55
The cost estimate in `_adjoint_qrom_load_one_hot_size` creates abstract
operators, which bound `symbolic_array` placeholders into the captured
program and broke compilation under `qjit`. Pause capture while estimating.
Remove the xfail of `test_qjit`, as Catalyst #3376 is merged.

This commit was authored with the help of an AI assistant (Cursor).

Co-authored-by: Cursor <cursoragent@cursor.com>
@dwierichs
dwierichs marked this pull request as ready for review November 10, 2026 14:26
dwierichs and others added 4 commits November 11, 2026 11:12
…ecomp

Co-authored-by: Cursor <cursoragent@cursor.com>

# Conflicts:
#	doc/releases/changelog-dev.md
#	pennylane/numeric_hamiltonians.py
#	pennylane/templates/subroutines/qrom.py
#	tests/templates/subroutines/test_qrom.py
Co-authored-by: Cursor <cursoragent@cursor.com>

# Conflicts:
#	doc/releases/changelog-dev.rst
#	pennylane/templates/subroutines/qrom_load.py
#	tests/templates/subroutines/test_qrom_load.py
After the measure-and-reset step, the target wires are clean, so they now
join the work wires as auxiliary wires for the one-hot register and the
fixup `QROM`. The rule no longer requires work wires, and with exactly
c - 1 work wires it now beats inverting `QROMLoad`.

Also regenerate the thumbnail without background, fold the changelog
entry into the `QROMLoad` feature entry, document the control wire
requirement, and test that the graph chooses the rule.

This commit was authored with the help of an AI assistant (Cursor).

Co-authored-by: Cursor <cursoragent@cursor.com>
@dwierichs dwierichs changed the title Add measurement-based decomposition to Adjoint(QROM) Add measurement-based decomposition to Adjoint(QROMLoad) Nov 11, 2026
@dwierichs

Copy link
Copy Markdown
Contributor Author

Review by Opus 5.5 on high effort, after multiple iterations.

Verdict: ready to merge.

This PR adds _adjoint_qrom_load_measurement, a decomposition of Adjoint(QROMLoad) for qjit(capture=True) and clean=True, following Appendix C of arXiv:1902.02134. The target wires are measured in the X basis and reset. The resulting phases $(-1)^{m\cdot b_j}$ are then undone by a QROM of $\lceil L/k\rceil$ entries, which targets a one-hot encoding of the low address bits in $k$ auxiliary wires (the reset target wires, then the work wires).

What was checked:

  • Correctness: the phase bookkeeping, the one-hot construction from TemporaryAND + CNOT (Figures 6 and 8–10), the split of the address bits, and padding and extra control wires. test_correctness covers every X-measurement outcome, and an additional 90-case sweep (1–3 targets, 0–2 work wires, with and without an extra control wire) passes.
  • Safety: the rule contains measurements, so the graph never wraps it automatically in ctrl or adjoint.
  • Cost: the graph picks the rule and the estimated T-count drops sharply. For 256 bitstrings with 8 targets and 20 work wires it goes from 1012 to 112. With exactly $c-1$ work wires (256 bitstrings, 2 targets, 7 work wires), reusing the target wires takes it from 1012 to 256.
  • One-hot size heuristic: it picked the size with the lowest T-count in all 210 configurations swept against graph estimates for every possible size.
  • Docs: the decomposition table's example counts match compute_resources, and the thumbnail matches the example.
  • CI on 93c7aeb: the Catalyst tests (all five qjit cases), documentation examples, lint and tach pass.

@dwierichs dwierichs added the review-ready 👌 PRs which are ready for review by someone from the core team. label Nov 11, 2026
dwierichs and others added 10 commits November 16, 2026 11:18
Resolve conflicts by keeping the QROM/QROMLoad split and adapting the
Adjoint(QROM) measurement-based uncomputation onto QROM without clean.

Co-authored-by: Cursor <cursoragent@cursor.com>
…ecomp

Prefer remote Adjoint(QROMLoad) measurement uncomputation over the local
Adjoint(QROM) variant after the QROM/QROMLoad split.

Co-authored-by: Cursor <cursoragent@cursor.com>
Resolve test_qrom_load conflict by taking the updated select-swap T-count
check from split-qrom and keeping the Adjoint(QROMLoad) tests.

Co-authored-by: Cursor <cursoragent@cursor.com>
@dwierichs dwierichs changed the title Add measurement-based decomposition to Adjoint(QROMLoad) Add measurement-based decomposition to Adjoint(QROMLoad) and Adjoint(SelectSwap) Nov 19, 2026
@dwierichs

Copy link
Copy Markdown
Contributor Author

Re-review by Opus 5.5 on high effort (because SelectSwap needs the new rule as well after the base branch introduced it)

Verdict: ready to merge.

This PR adds measurement-based uncomputation (Appendix C of arXiv:1902.02134) for Adjoint(QROMLoad) and Adjoint(SelectSwap). Both rules require program capture and at least one control wire, and are chosen by the graph when PauliMeasure is in the gate set.

What was checked:

  • Correctness: the one-hot encoding, the phase fixup on the $|\pm\rangle$ one-hot wires, the SelectSwap permutations of the SWAP network, and the padded fixup table.
  • Graph selection: both rules are chosen when PauliMeasure is available. Otherwise, the graph falls back to the inverse decompositions.
  • Tests: exact resource counts, correctness against postselected measurement outcomes, capture, and qjit. The relevant tests pass locally and CI is green.

Not independently verified: the one-hot size heuristic sweeps and the reported T-count reductions.

@KetpuntoG KetpuntoG left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It is so nice that we can do this kind of decomposition!
Leaving some comments

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I see other images has been updated to the new temporaryAND drawing but this one is still using the previous one

Comment on lines +576 to +578
i.e., of the inverted SWAP network of Select-SWAP. They are not obtained from ``_swap_ops``,
because the latter applies generic controlled SWAPs and cannot make use of ``y`` being in
the :math:`|0\rangle` state."""

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

what is this doing? we are saving 1 cnot per cswap?

Comment on lines +665 to +668
X(one_hot_wires[0])
for control, x, y in triples:
TemporaryAND([control, x, y])
CNOT([y, x])

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

are these the controlled SWAPs with target 0? it would help to add a one-line comment if so

Comment on lines +720 to +721
t0: ──┤↗X├──┤↗Z├──X──X─────────────├●─╭X─├●─╭X─│───H────├QROM(M0)──H──────│─╭X──●┤─╭X──●┤──X─┤
t1: ─────────────────┤↗X├──┤↗Z├──X─╰⊕─╰●─│──│──├●─╭X──H─├QROM(M0)──H─╭X──●┤─│────│─╰●──⊕╯────┤

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

where do these initial measurements come from? should I be looking to fig5?

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ah okey, those are the Hadamard + measurement
but you are using X directly 👍

target_wires = base.target_wires
outcomes = _measure_and_reset(target_wires)
fixups = math.dot(bitstrings, math.cast(math.stack(outcomes), int)) % 2
_phase_fixup(fixups, base.control_wires, Wires(target_wires) + Wires(base.work_wires))

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

In the paper Im seen the hadamard+hadamard + cnot, is this here somewhere?

Screenshot 2026-11-19 at 1 53 02 PM

)


class SelectSwap(Operator2):

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I was not aware that this was already merged
To double check, SelectSwap is the QROMLoad version, right? (input 0)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

review-ready 👌 PRs which are ready for review by someone from the core team.

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants