Quantum circuit design via dynamic Pauli constraints

Daniel Bultrini; James R. Wootton; Merlin Incerti-Medici; Pierre Fromholz

arxiv: 2605.22744 · v1 · pith:RFYIUIM3new · submitted 2026-05-21 · 🪐 quant-ph

Quantum circuit design via dynamic Pauli constraints

James R. Wootton , Merlin Incerti-Medici , Daniel Bultrini , Pierre Fromholz This is my paper

Pith reviewed 2026-05-22 05:35 UTC · model grok-4.3

classification 🪐 quant-ph

keywords quantum circuitsPauli observablesquantum state tomographyNISQBQPquantum softwarecoupling graph

0 comments

The pith

Gates defined by Pauli constraints and tomography are equivalent to coupling-graph-restricted circuits and universal for BQP with polynomial overhead.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a model for quantum computation where gates are specified through constraints on Pauli observables and each layer of disjoint gates is followed by pairwise or k-local quantum state tomography. It proves that this model has exactly the same power as the coupling-graph-restricted circuit model. The equivalence establishes that the new model is universal for BQP, with any depth-D circuit on N qubits simulable using at most O(D squared N log N) resources. This offers a practical way to design quantum programs using only physically measurable quantities, which matches the constraints of near-term hardware.

Core claim

We introduce a software-oriented model of quantum computation in which gates are specified by constraints expressed in terms of Pauli observables, with each disjoint layer of gates accompanied by a pairwise or k-local quantum state tomography of the device. We prove that the model is equivalent to the coupling-graph-restricted circuit model and hence universal for BQP, with a polynomial overhead: simulating a depth-D circuit on N qubits requires at most O(D squared N log N) complexity. The model formalizes an idiom shared by existing work ranging from quantum imaginary time evolution to procedural generation in games.

What carries the argument

The dynamic Pauli constraints model, in which gates are defined by constraints on Pauli observables and each layer includes accompanying tomography to capture the state in terms of observables.

If this is right

Quantum software can be designed entirely in terms of physically observable quantities.
The model supports universal quantum computation for BQP with only polynomial overhead.
It provides a natural interface for techniques such as quantum imaginary time evolution and game procedural generation.
The approach applies to both NISQ-era devices and fault-tolerant quantum computing.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This model could allow quantum algorithm designers to work directly with measurement outcomes rather than abstract gate sequences.
Hybrid quantum-classical workflows may benefit from built-in tomography steps that supply classical feedback at each layer.
Practical implementations could reduce tomography overhead by adapting the frequency or locality based on specific hardware topologies.

Load-bearing premise

That specifying gates via Pauli constraints plus the required tomography after each layer fully captures the computational power of coupling-graph-restricted circuits without hidden costs or information loss.

What would settle it

A concrete quantum circuit or algorithm that can be performed in the coupling-graph-restricted model but cannot be reproduced in the Pauli constraints model, or that requires more than polynomial overhead in the new model.

Figures

Figures reproduced from arXiv: 2605.22744 by Daniel Bultrini, James R. Wootton, Merlin Incerti-Medici, Pierre Fromholz.

read the original abstract

We introduce a novel software-oriented model of quantum computation motivated by the practical constraints of near-term quantum hardware. In this model, gates are specified by constraints expressed in terms of Pauli observables, with each disjoint layer of gates accompanied by a pairwise or $k$-local quantum state tomography of the device. We prove that the model is equivalent to the coupling-graph-restricted circuit model and hence universal for BQP, with a polynomial overhead: simulating a depth-$D$ circuit on $N$ qubits requires at most $O(D^2 N \log N)$ complexity. The model formalizes an idiom shared by existing work that ranges from quantum imaginary time evolution for the study of quantum systems to the use of quantum computers for procedural generation in games. It therefore provides a natural interface for designing quantum software entirely in terms of physically observable quantities, relevant for the NISQ era and into fault-tolerance.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper formalizes a Pauli-constraint plus post-layer tomography model for circuits and proves equivalence to coupling-graph restricted ones with O(D^2 N log N) overhead.

read the letter

The main thing to know is that this paper defines a circuit model where gates are set by dynamic Pauli constraints and each layer gets pairwise or k-local tomography afterward. They prove this matches the power of coupling-graph-restricted circuits, so it is BQP-universal, at a simulation cost of O(D^2 N log N) for depth D on N qubits. The equivalence is shown through explicit mappings rather than loose arguments. The O(D^2 N log N) bound follows from decomposing each gate into constraint-tomography blocks whose local statistics reconstruct the needed information with only log factors. No exponential hidden costs appear in the construction. What the paper does well is make explicit an idiom already used in quantum imaginary time evolution and in procedural generation work. Framing everything around observable constraints gives a more direct interface for NISQ software design than abstract gate lists. The stress-test note confirms the mappings are constructive and the complexity claim holds without post-hoc adjustments. One soft spot is that the model assumes the tomography steps capture everything without extra practical costs. On real hardware those measurements add overhead the theoretical bound does not fully price in, and the paper does not show concrete examples where the constraint view simplifies algorithm design over standard methods. This is for people working on NISQ circuit compilation and observable-based quantum programming. A reader who wants to organize existing techniques around measurable quantities will find it relevant. It deserves a serious referee because the equivalence is non-trivial and the motivation tracks hardware constraints. I would send it out for review.

Referee Report

0 major / 3 minor

Summary. The paper introduces a software-oriented model of quantum computation in which gates are specified via constraints on Pauli observables, with each disjoint layer accompanied by pairwise or k-local quantum state tomography. It proves equivalence to the coupling-graph-restricted circuit model (hence universality for BQP) and bounds the simulation overhead for a depth-D circuit on N qubits by O(D² N log N). The model is motivated by near-term hardware constraints and formalizes idioms appearing in quantum imaginary time evolution and procedural generation applications.

Significance. If the equivalence and overhead bound hold, the work supplies a concrete interface for designing quantum algorithms directly in terms of physically measurable quantities. This is relevant for NISQ-era software development and provides a polynomial-cost reduction to a standard universal model, thereby supporting both theoretical universality claims and practical hardware-aware circuit construction.

minor comments (3)

[Abstract] Abstract: the phrase 'pairwise or k-local quantum state tomography' leaves the choice of k and its scaling with N or D unspecified; a brief clarification of the locality parameter would improve readability.
[Main theorem statement] The claim of 'polynomial overhead' is stated as O(D² N log N); confirming that the hidden constants are independent of the particular coupling graph (as opposed to depending on its degree or diameter) would strengthen the result statement.
[Introduction] The manuscript references existing work on quantum imaginary time evolution and game procedural generation but does not include explicit citations for the 'idiom' being formalized; adding one or two representative references would help readers locate the connection.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the Pauli-constraint model, and recommendation for minor revision. We appreciate the recognition that the work provides a concrete interface for NISQ-era algorithm design in terms of measurable observables while establishing polynomial equivalence to the coupling-graph model.

Circularity Check

0 steps flagged

No significant circularity; equivalence proof is self-contained

full rationale

The paper establishes equivalence between the Pauli-constraint model and the independently defined coupling-graph-restricted circuit model through explicit constructive mappings and layered decompositions. The polynomial overhead bound is obtained by direct counting of constraint-tomography blocks per original gate, using only local observable statistics. No load-bearing step reduces to a fitted parameter, self-definition, or self-citation chain; the derivation remains independent of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper introduces a new modeling framework but rests on standard quantum information assumptions about observables, tomography, and circuit universality; no free parameters or new physical entities are introduced.

axioms (2)

domain assumption Quantum gates can be fully specified by constraints on Pauli observables.
Core modeling choice stated in the abstract as the basis for the new software-oriented model.
domain assumption Pairwise or k-local tomography after each layer is feasible and sufficient to characterize the state evolution.
Invoked as part of the model definition to accompany each disjoint layer of gates.

pith-pipeline@v0.9.0 · 5684 in / 1309 out tokens · 53390 ms · 2026-05-22T05:35:04.061033+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We prove that the model is equivalent to the coupling-graph-restricted circuit model and hence universal for BQP, with a polynomial overhead: simulating a depth-D circuit on N qubits requires at most O(D² N log N) complexity.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Gates are specified by providing a set of at most k-body target Pauli expectation values... The iteration U applied to the circuit maps the eigenstates of the stated tomography to those of the density matrix that corresponds to the targets.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

59 extracted references · 59 canonical work pages · 4 internal anchors

[1]

If each were given a sepa- rate measurement setting, an upper bound ofO(N k) set- tings would be required, however the complexity will typ- ically be much lower

Tomography The number ofk-body Pauli expectation values on Nqubits is N k (4k −1). If each were given a sepa- rate measurement setting, an upper bound ofO(N k) set- tings would be required, however the complexity will typ- ically be much lower. On a graph where each qubit has bounded connectivity, the number ofk-node connected subgraphs isO(N), each requi...

work page
[2]

Fromk-body expectation values one can construct all≤k-qubit re- duced density matrices (RDMs)

Gates via eigenstate transformation The hardware-native gates (most often single- and two- qubit gates only) applied at each step are determined jointly by the user-supplied target expectation values and the results of the most recent tomography. Fromk-body expectation values one can construct all≤k-qubit re- duced density matrices (RDMs). Given tomograph...

work page
[3]

This form of gate is primarily motivated by the arguments to be made in the next sec- tion, and so a full specification of this form of gate can be found in Sec

Gates via density matrix transformation The above-mentioned phase ambiguity can be resolved by working one level higher in the tomographic hierar- chy, withm-qubit gates determined with a tomography onk=m+ 1 qubits. This form of gate is primarily motivated by the arguments to be made in the next sec- tion, and so a full specification of this form of gate ...

work page
[4]

Consider a geometricℓ-local Hamil- tonianH= P m hm, where each of theMtermsh m acts on at mostℓneighbouring qubits of the coupling graphG

Gates via QITE A third realization of the gate-specification procedure arises from QITE [7]. Consider a geometricℓ-local Hamil- tonianH= P m hm, where each of theMtermsh m acts on at mostℓneighbouring qubits of the coupling graphG. Ground and thermal states ofHare approached through imaginary-time evolutione −βH |Ψ⟩/∥e−βH |Ψ⟩∥, which is approximated via a...

work page
[5]

The quantum computer runs a tomography of the circuit so far and supplies the results to the user

work page
[6]

The user chooses a method with which the interface computer will deduce the required gates (typically the same for each step)

work page
[7]

Using their own classical computer, the user re- constructs the matrix representation of thek-qubit RDMs for all qubits that will be targeted by their desired gateU

work page
[8]

This tomography is the new target supplied to the interface computer

The user’s classical computer then applies the ma- trix representation ofUto the RDM and deduces the resulting tomography. This tomography is the new target supplied to the interface computer. Since this requires only classical computation on single- or two-qubit matrices, the computational cost isO(1) per matrix

work page
[9]

The eigenvalues are used to identify pairs of corresponding initial and target eigenstates

The interface computer reconstructs the matrix representation of both the initial and target RDMs and diagonalizes them. The eigenvalues are used to identify pairs of corresponding initial and target eigenstates

work page
[10]

It then transpiles the matrix rep- resentation of ˜Uto quantum gates and adds it to the circuit

The interface computer deduces the unitary ˜U which provides an equivalent transformation of eigenstates toU. It then transpiles the matrix rep- resentation of ˜Uto quantum gates and adds it to the circuit. The details of equivalence with the circuit model depend on the method chosen by the user for the interface com- puter to reconstructU, as well as the...

work page
[11]

Gates via eigenstate transformation Let us first consider the use of gates via eigenstate transformation withk= 2 only, which represents the current implementation of theQuantumGraphpackage. As described above, single- and two-qubit gates can be added by taking the given single- or two-qubit tomogra- phy, deducing the resulting RDM and then transforming i...

work page
[12]

As seen above, the action of anm-qubit unitary on 2 m orthogonal rays (rather than vectors) is not enough to reconstructU

Gates via density matrix transformation Gates via density matrix transformation are specifi- cally designed to resolve the phase ambiguity in the case of a user who wishes to hack the Motte model into ap- plying a predefined unitary. As seen above, the action of anm-qubit unitary on 2 m orthogonal rays (rather than vectors) is not enough to reconstructU. ...

work page
[13]

This can be achieved via the Motte model fork= 2 if gates via eigenstate transformation and gates via density ma- trix transformation are combined

Combined gates atk= 2 Universality can be achieved via arbitrary single-qubit gates and a single entangling two-qubit gate [32]. This can be achieved via the Motte model fork= 2 if gates via eigenstate transformation and gates via density ma- trix transformation are combined. The latter allows per- fect implementations of any single-qubit gates by using a...

work page
[14]

Indeed, this is a problem more related to the intended usage of the Motte model

State preparation universality for gates via QITE Since equivalence with the circuit model has already been demonstrated withk= 2 andk= 3 for the above methods, for gates via QITE we will instead consider a related problem: efficient state preparation [34]. Indeed, this is a problem more related to the intended usage of the Motte model. By construction, Q...

work page
[15]

Specifically, we consider the target state for which ⟨Z⊗Z⊗I⟩=⟨Z⊗I⊗Z⟩=⟨I⊗Z⊗Z⟩=⟨X⊗X⊗X⟩= 1, with all other expectation values zero

Worked example: GHZ state preparation As an example of the Motte model emulating a quan- tum circuit, consider the preparation of a three qubit GHZ state via a Hadamard and two chained CNOT gates. Specifically, we consider the target state for which ⟨Z⊗Z⊗I⟩=⟨Z⊗I⊗Z⟩=⟨I⊗Z⊗Z⟩=⟨X⊗X⊗X⟩= 1, with all other expectation values zero. This is done from 7 the initial...

work page 2020
[16]

A. W. Cross, L. S. Bishop, J. A. Smolin, and J. M. Gam- betta, arXiv:1707.03429 [quant-ph] (2017)

work page internal anchor Pith review Pith/arXiv arXiv 2017
[17]

Preskill, Quantum2, 79 (2018)

J. Preskill, Quantum2, 79 (2018)

work page 2018
[18]

IBM Quantum, IBM quantum roadmap: Path to fault-tolerant quantum computing (2025), targets fault- tolerant quantum computing (Quantum Starling) by 2029

work page 2025
[19]

Quantinuum, Quantinuum unveils accelerated roadmap to achieve universal fault-tolerant quantum computing by 2030 (2024)

work page 2030
[20]

Y. Kim, A. Eddins, S. Anand,et al., Nature618, 500 (2023)

work page 2023
[21]

Boixo, V

S. Boixo, V. N. Smelyanskiy, A. Shabani, S. V. Isakov, M. Dykman, V. S. Denchev, H. Neven,et al., Nature Physics14, 595 (2018)

work page 2018
[22]

Motta, C

M. Motta, C. Sun, A. T. K. Tan, M. J. O’Rourke, E. Ye, A. J. Minnich, F. G. S. L. Brand˜ ao, and G. K.-L. Chan, Nature Physics16, 205 (2020)

work page 2020
[23]

J. R. Wootton, inProceedings of the IEEE Conference on Games 2020(2020)

work page 2020
[24]

Fromholz, S

P. Fromholz, S. Topel, and J. R. Wootton, Quantum backrooms: Level generation with utility-scale quantum hardware (2025), in preparation

work page 2025
[25]

A. B. Magann, K. M. Rudinger, M. D. Grace, and M. Sarovar, Physical Review Letters129, 250502 (2022), arXiv:2103.08619 [quant-ph]

work page arXiv 2022
[26]

J. B. Larsen, M. D. Grace, A. D. Baczewski, and A. B. Magann, Feedback-based quantum algorithm for ground state preparation of the fermi-hubbard model (2023), arXiv:2303.02917 [quant-ph]

work page arXiv 2023
[27]

Erle and B

J. Erle and B. Koczor, A shadow enhanced greedy quan- tum eigensolver (2026), arXiv:2602.17615 [quant-ph]

work page arXiv 2026
[28]

Z. C. Seskir, P. Migda l, C. Weidner, A. Anupam, N. Case, N. Davis, C. Decaroli, ˙I. Ercan, C. Foti, P. Gora, K. Jankiewicz, B. R. La Cour, J. Yago Malo, S. Maniscalco, A. Naeemi, L. Nita, N. Parvin, F. Scafir- imuto, J. F. Sherson, E. Surer, J. Wootton, L. Yeh, O. Zabello, and M. Chiofalo, Optical Engineering61, 10.1117/1.oe.61.8.081809 (2022)

work page doi:10.1117/1.oe.61.8.081809 2022
[29]

Kondappan, M

M. Kondappan, M. Chaudhary, E. O. Ilo-Okeke, V. Ivannikov, and T. Byrnes, Physical Review A107, 10.1103/physreva.107.042616 (2023)

work page doi:10.1103/physreva.107.042616 2023
[30]

H. M. Wiseman and G. J. Milburn,Quantum Measure- ment and Control(Cambridge University Press, 2009)

work page 2009
[31]

Sayrin, I

C. Sayrin, I. Dotsenko, X. Zhou, B. Peaudecerf, T. Rybarczyk, S. Gleyzes, P. Rouchon, M. Mirrahimi, H. Amini, M. Brune, J.-M. Raimond, and S. Haroche, Nature477, 73–77 (2011)

work page 2011
[32]

Garc´ ıa-P´ erez, M

G. Garc´ ıa-P´ erez, M. A. C. Rossi, B. Sokolov, E.-M. Bor- relli, and S. Maniscalco, Physical Review Research2, 10.1103/physrevresearch.2.023393 (2020)

work page doi:10.1103/physrevresearch.2.023393 2020
[33]

Uhlmann, Reports on Mathematical Physics9, 273 (1976)

A. Uhlmann, Reports on Mathematical Physics9, 273 (1976)

work page 1976
[34]

M. B. Hastings and T. Koma, Communications in Math- ematical Physics265, 781 (2006)

work page 2006
[35]

Peruzzo, J

A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, Nature Communications5, 4213 (2014)

work page 2014
[36]

A Quantum Approximate Optimization Algorithm

E. Farhi, J. Goldstone, and S. Gutmann, arXiv preprint arXiv:1411.4028 (2014), arXiv:1411.4028

work page internal anchor Pith review Pith/arXiv arXiv 2014
[37]

Larocca, S

M. Larocca, S. Thanasilp, S. Wang, K. Sharma, J. Bia- monte, P. J. Coles, L. Cincio, J. R. McClean, Z. Holmes, and M. Cerezo, Nature Reviews Physics7, 174 (2025)

work page 2025
[38]

Cerezo, M

M. Cerezo, M. Larocca, D. Garc´ ıa-Mart´ ın, N. L. Diaz, P. Braccia, E. Fontana, M. S. Rudolph, P. Bermejo, A. Ijaz, S. Thanasilp, E. R. Anschuetz, and Z. Holmes, Nature Communications16, 7907 (2025)

work page 2025
[39]

Quantum approximate optimization is computationally universal

S. Lloyd, arXiv preprint arXiv:1812.11075 (2018), arXiv:1812.11075

work page internal anchor Pith review Pith/arXiv arXiv 2018
[40]

Wootton, Circuit model of quantum computation (2024)

J. Wootton, Circuit model of quantum computation (2024)

work page 2024
[41]

Beals, S

R. Beals, S. Brierley, O. Gray, A. W. Harrow, S. Kutin, N. Linden, D. Shepherd, and M. Stather, Proceedings of the Royal Society A: Mathematical, Physical and Engi- neering Sciences469, 10.1098/rspa.2012.0686 (2013)

work page doi:10.1098/rspa.2012.0686 2012
[42]

L. Chen, Y. Ren, R. Fan, and A. Jaffe, npj Quantum Information11, 10.1038/s41534-025-01063-4 (2025)

work page doi:10.1038/s41534-025-01063-4 2025
[43]

Raussendorf and J

R. Raussendorf and J. Harrington, Physical Review Let- ters98, 10.1103/physrevlett.98.190504 (2007)

work page doi:10.1103/physrevlett.98.190504 2007
[44]

M. S. Sarandy and D. A. Lidar, Physical Review Letters 95, 10.1103/physrevlett.95.250503 (2005)

work page doi:10.1103/physrevlett.95.250503 2005
[45]

Quantum Computation by Adiabatic Evolution

E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution (2000), arXiv:quant-ph/0001106 [quant-ph]

work page internal anchor Pith review Pith/arXiv arXiv 2000
[46]

Barenco, C

A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, Physical Review A52, 3457 (1995)

work page 1995
[47]

Brylinski and R

J.-L. Brylinski and R. Brylinski, inMathematics of Quan- tum Computation, edited by R. Brylinski and G. Chen (Chapman & Hall/CRC, 2002) pp. 101–116

work page 2002
[48]

M. J. Bremner, C. M. Dawson, J. L. Dodd, A. Gilchrist, A. W. Harrow, D. Mortimer, M. A. Nielsen, and T. J. Osborne, Phys. Rev. Lett.89, 247902 (2002)

work page 2002
[49]

N. J. Ward, I. Kassal, and A. Aspuru-Guzik, The Journal of Chemical Physics130, 10.1063/1.3115177 (2009)

work page doi:10.1063/1.3115177 2009
[50]

Gomes, A

N. Gomes, A. Mukherjee, F. Zhang, T. Iadecola, C.-Z. Wang, K.-M. Ho, P. P. Orth, and Y.-X. Yao, Advanced Quantum Technologies4, 10.1002/qute.202100114 (2021)

work page doi:10.1002/qute.202100114 2021
[51]

Yeter-Aydeniz, R

K. Yeter-Aydeniz, R. C. Pooser, and G. Siopsis, Practi- cal quantum computation of chemical and nuclear energy levels using quantum imaginary time evolution and lanc- zos algorithms (2019)

work page 2019
[52]

Gomes, F

N. Gomes, F. Zhang, N. F. Berthusen, C.-Z. Wang, K.-M. Ho, P. P. Orth, and Y. Yao, Journal of Chemical Theory and Computation16, 6256 (2020). 10

work page 2020
[53]

Nishi, T

H. Nishi, T. Kosugi, and Y.-i. Matsushita, npj Quantum Information7, 10.1038/s41534-021-00409-y (2021)

work page doi:10.1038/s41534-021-00409-y 2021
[54]

Lloyd, Science273, 1073 (1996)

S. Lloyd, Science273, 1073 (1996). Appendix A: Adapt-H QITE’s universality We present here a more rigorous argument for the uni- versality of Adapt-H QITE, introduced in Sec. III B 3

work page 1996
[55]

At a point|ψ⟩, the tangent spaceT ψ is Tψ = |δψ⟩ ∈ H:⟨ψ|δψ⟩= 0 , i.e

The tangent space A pure state ofNqubits lives on the unit sphere of H= (C 2)⊗N, or, modulo the irrelevant global phase, in projective Hilbert spaceP(H). At a point|ψ⟩, the tangent spaceT ψ is Tψ = |δψ⟩ ∈ H:⟨ψ|δψ⟩= 0 , i.e. the orthogonal complement of|ψ⟩. Its complex di- mension is 2 N −1. Intuitively,T ψ collects the directions in which|ψ⟩can move while...

work page
[56]

Expanding to first order in ∆τ, |ψ′⟩=|ψ⟩ −∆τ hm − ⟨hm⟩ |ψ⟩+O(∆τ 2), so the infinitesimal motion is |δψ⟩=−∆τ(h m − ⟨hm⟩)|ψ⟩

The QITE step as a tangent-space projection A single QITE infinitesimal step on the Hamiltonian termh m with imaginary-time increment ∆τproduces the normalised state |ψ′⟩= e−∆τ hm|ψ⟩√c , c=⟨ψ|e −2∆τ hm |ψ⟩. Expanding to first order in ∆τ, |ψ′⟩=|ψ⟩ −∆τ hm − ⟨hm⟩ |ψ⟩+O(∆τ 2), so the infinitesimal motion is |δψ⟩=−∆τ(h m − ⟨hm⟩)|ψ⟩. WritingP ⊥ ψ =1− |ψ⟩⟨ψ|for...

work page
[57]

varyh m over e.g. all 2-local Hermitians, sweep out all tangent directions, conclude that adaptive-H QITE can move|ψ⟩wherever we like

Why one step does not spanT ψ It would be tempting to argue universality as follows: “varyh m over e.g. all 2-local Hermitians, sweep out all tangent directions, conclude that adaptive-H QITE can move|ψ⟩wherever we like.” However, this would be wrong. LetL 2 denote the real vector space of 2-local Hermi- tian operators supported on edges of the coupling g...

work page
[58]

This is the orbit of the initial state|ψ 0⟩under the Lie groupGgenerated by the unitaries{e −itA(h)|h∈ L2, t∈R}, whereA(h) denotes the operator that QITE constructs for the termh

Universality via Lie-algebra closure Consider the set of states reachable by sequences of QITE infinitesimal steps with adaptively chosenh m ∈ L2. This is the orbit of the initial state|ψ 0⟩under the Lie groupGgenerated by the unitaries{e −itA(h)|h∈ L2, t∈R}, whereA(h) denotes the operator that QITE constructs for the termh. The Lie algebragofGis the smal...

work page
[59]

Specifi- cally, any two-qubit gate involving connected qubits ac- cording toGwithin errorϵwill takeO(1/ϵ) adapt-H QITE steps (first-order Trotter-step error [39])

Cost: universality is not efficiency Any target state can be approached arbitrarily closely by some sequence of QITE micro-steps, but the length of that sequence may scale exponentially withN. Specifi- cally, any two-qubit gate involving connected qubits ac- cording toGwithin errorϵwill takeO(1/ϵ) adapt-H QITE steps (first-order Trotter-step error [39]). ...

work page

[1] [1]

If each were given a sepa- rate measurement setting, an upper bound ofO(N k) set- tings would be required, however the complexity will typ- ically be much lower

Tomography The number ofk-body Pauli expectation values on Nqubits is N k (4k −1). If each were given a sepa- rate measurement setting, an upper bound ofO(N k) set- tings would be required, however the complexity will typ- ically be much lower. On a graph where each qubit has bounded connectivity, the number ofk-node connected subgraphs isO(N), each requi...

work page

[2] [2]

Fromk-body expectation values one can construct all≤k-qubit re- duced density matrices (RDMs)

Gates via eigenstate transformation The hardware-native gates (most often single- and two- qubit gates only) applied at each step are determined jointly by the user-supplied target expectation values and the results of the most recent tomography. Fromk-body expectation values one can construct all≤k-qubit re- duced density matrices (RDMs). Given tomograph...

work page

[3] [3]

This form of gate is primarily motivated by the arguments to be made in the next sec- tion, and so a full specification of this form of gate can be found in Sec

Gates via density matrix transformation The above-mentioned phase ambiguity can be resolved by working one level higher in the tomographic hierar- chy, withm-qubit gates determined with a tomography onk=m+ 1 qubits. This form of gate is primarily motivated by the arguments to be made in the next sec- tion, and so a full specification of this form of gate ...

work page

[4] [4]

Consider a geometricℓ-local Hamil- tonianH= P m hm, where each of theMtermsh m acts on at mostℓneighbouring qubits of the coupling graphG

Gates via QITE A third realization of the gate-specification procedure arises from QITE [7]. Consider a geometricℓ-local Hamil- tonianH= P m hm, where each of theMtermsh m acts on at mostℓneighbouring qubits of the coupling graphG. Ground and thermal states ofHare approached through imaginary-time evolutione −βH |Ψ⟩/∥e−βH |Ψ⟩∥, which is approximated via a...

work page

[5] [5]

The quantum computer runs a tomography of the circuit so far and supplies the results to the user

work page

[6] [6]

The user chooses a method with which the interface computer will deduce the required gates (typically the same for each step)

work page

[7] [7]

Using their own classical computer, the user re- constructs the matrix representation of thek-qubit RDMs for all qubits that will be targeted by their desired gateU

work page

[8] [8]

This tomography is the new target supplied to the interface computer

The user’s classical computer then applies the ma- trix representation ofUto the RDM and deduces the resulting tomography. This tomography is the new target supplied to the interface computer. Since this requires only classical computation on single- or two-qubit matrices, the computational cost isO(1) per matrix

work page

[9] [9]

The eigenvalues are used to identify pairs of corresponding initial and target eigenstates

The interface computer reconstructs the matrix representation of both the initial and target RDMs and diagonalizes them. The eigenvalues are used to identify pairs of corresponding initial and target eigenstates

work page

[10] [10]

It then transpiles the matrix rep- resentation of ˜Uto quantum gates and adds it to the circuit

The interface computer deduces the unitary ˜U which provides an equivalent transformation of eigenstates toU. It then transpiles the matrix rep- resentation of ˜Uto quantum gates and adds it to the circuit. The details of equivalence with the circuit model depend on the method chosen by the user for the interface com- puter to reconstructU, as well as the...

work page

[11] [11]

Gates via eigenstate transformation Let us first consider the use of gates via eigenstate transformation withk= 2 only, which represents the current implementation of theQuantumGraphpackage. As described above, single- and two-qubit gates can be added by taking the given single- or two-qubit tomogra- phy, deducing the resulting RDM and then transforming i...

work page

[12] [12]

As seen above, the action of anm-qubit unitary on 2 m orthogonal rays (rather than vectors) is not enough to reconstructU

Gates via density matrix transformation Gates via density matrix transformation are specifi- cally designed to resolve the phase ambiguity in the case of a user who wishes to hack the Motte model into ap- plying a predefined unitary. As seen above, the action of anm-qubit unitary on 2 m orthogonal rays (rather than vectors) is not enough to reconstructU. ...

work page

[13] [13]

This can be achieved via the Motte model fork= 2 if gates via eigenstate transformation and gates via density ma- trix transformation are combined

Combined gates atk= 2 Universality can be achieved via arbitrary single-qubit gates and a single entangling two-qubit gate [32]. This can be achieved via the Motte model fork= 2 if gates via eigenstate transformation and gates via density ma- trix transformation are combined. The latter allows per- fect implementations of any single-qubit gates by using a...

work page

[14] [14]

Indeed, this is a problem more related to the intended usage of the Motte model

State preparation universality for gates via QITE Since equivalence with the circuit model has already been demonstrated withk= 2 andk= 3 for the above methods, for gates via QITE we will instead consider a related problem: efficient state preparation [34]. Indeed, this is a problem more related to the intended usage of the Motte model. By construction, Q...

work page

[15] [15]

Specifically, we consider the target state for which ⟨Z⊗Z⊗I⟩=⟨Z⊗I⊗Z⟩=⟨I⊗Z⊗Z⟩=⟨X⊗X⊗X⟩= 1, with all other expectation values zero

Worked example: GHZ state preparation As an example of the Motte model emulating a quan- tum circuit, consider the preparation of a three qubit GHZ state via a Hadamard and two chained CNOT gates. Specifically, we consider the target state for which ⟨Z⊗Z⊗I⟩=⟨Z⊗I⊗Z⟩=⟨I⊗Z⊗Z⟩=⟨X⊗X⊗X⟩= 1, with all other expectation values zero. This is done from 7 the initial...

work page 2020

[16] [16]

A. W. Cross, L. S. Bishop, J. A. Smolin, and J. M. Gam- betta, arXiv:1707.03429 [quant-ph] (2017)

work page internal anchor Pith review Pith/arXiv arXiv 2017

[17] [17]

Preskill, Quantum2, 79 (2018)

J. Preskill, Quantum2, 79 (2018)

work page 2018

[18] [18]

IBM Quantum, IBM quantum roadmap: Path to fault-tolerant quantum computing (2025), targets fault- tolerant quantum computing (Quantum Starling) by 2029

work page 2025

[19] [19]

Quantinuum, Quantinuum unveils accelerated roadmap to achieve universal fault-tolerant quantum computing by 2030 (2024)

work page 2030

[20] [20]

Y. Kim, A. Eddins, S. Anand,et al., Nature618, 500 (2023)

work page 2023

[21] [21]

Boixo, V

S. Boixo, V. N. Smelyanskiy, A. Shabani, S. V. Isakov, M. Dykman, V. S. Denchev, H. Neven,et al., Nature Physics14, 595 (2018)

work page 2018

[22] [22]

Motta, C

M. Motta, C. Sun, A. T. K. Tan, M. J. O’Rourke, E. Ye, A. J. Minnich, F. G. S. L. Brand˜ ao, and G. K.-L. Chan, Nature Physics16, 205 (2020)

work page 2020

[23] [23]

J. R. Wootton, inProceedings of the IEEE Conference on Games 2020(2020)

work page 2020

[24] [24]

Fromholz, S

P. Fromholz, S. Topel, and J. R. Wootton, Quantum backrooms: Level generation with utility-scale quantum hardware (2025), in preparation

work page 2025

[25] [25]

A. B. Magann, K. M. Rudinger, M. D. Grace, and M. Sarovar, Physical Review Letters129, 250502 (2022), arXiv:2103.08619 [quant-ph]

work page arXiv 2022

[26] [26]

J. B. Larsen, M. D. Grace, A. D. Baczewski, and A. B. Magann, Feedback-based quantum algorithm for ground state preparation of the fermi-hubbard model (2023), arXiv:2303.02917 [quant-ph]

work page arXiv 2023

[27] [27]

Erle and B

J. Erle and B. Koczor, A shadow enhanced greedy quan- tum eigensolver (2026), arXiv:2602.17615 [quant-ph]

work page arXiv 2026

[28] [28]

Z. C. Seskir, P. Migda l, C. Weidner, A. Anupam, N. Case, N. Davis, C. Decaroli, ˙I. Ercan, C. Foti, P. Gora, K. Jankiewicz, B. R. La Cour, J. Yago Malo, S. Maniscalco, A. Naeemi, L. Nita, N. Parvin, F. Scafir- imuto, J. F. Sherson, E. Surer, J. Wootton, L. Yeh, O. Zabello, and M. Chiofalo, Optical Engineering61, 10.1117/1.oe.61.8.081809 (2022)

work page doi:10.1117/1.oe.61.8.081809 2022

[29] [29]

Kondappan, M

M. Kondappan, M. Chaudhary, E. O. Ilo-Okeke, V. Ivannikov, and T. Byrnes, Physical Review A107, 10.1103/physreva.107.042616 (2023)

work page doi:10.1103/physreva.107.042616 2023

[30] [30]

H. M. Wiseman and G. J. Milburn,Quantum Measure- ment and Control(Cambridge University Press, 2009)

work page 2009

[31] [31]

Sayrin, I

C. Sayrin, I. Dotsenko, X. Zhou, B. Peaudecerf, T. Rybarczyk, S. Gleyzes, P. Rouchon, M. Mirrahimi, H. Amini, M. Brune, J.-M. Raimond, and S. Haroche, Nature477, 73–77 (2011)

work page 2011

[32] [32]

Garc´ ıa-P´ erez, M

G. Garc´ ıa-P´ erez, M. A. C. Rossi, B. Sokolov, E.-M. Bor- relli, and S. Maniscalco, Physical Review Research2, 10.1103/physrevresearch.2.023393 (2020)

work page doi:10.1103/physrevresearch.2.023393 2020

[33] [33]

Uhlmann, Reports on Mathematical Physics9, 273 (1976)

A. Uhlmann, Reports on Mathematical Physics9, 273 (1976)

work page 1976

[34] [34]

M. B. Hastings and T. Koma, Communications in Math- ematical Physics265, 781 (2006)

work page 2006

[35] [35]

Peruzzo, J

A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, Nature Communications5, 4213 (2014)

work page 2014

[36] [36]

A Quantum Approximate Optimization Algorithm

E. Farhi, J. Goldstone, and S. Gutmann, arXiv preprint arXiv:1411.4028 (2014), arXiv:1411.4028

work page internal anchor Pith review Pith/arXiv arXiv 2014

[37] [37]

Larocca, S

M. Larocca, S. Thanasilp, S. Wang, K. Sharma, J. Bia- monte, P. J. Coles, L. Cincio, J. R. McClean, Z. Holmes, and M. Cerezo, Nature Reviews Physics7, 174 (2025)

work page 2025

[38] [38]

Cerezo, M

M. Cerezo, M. Larocca, D. Garc´ ıa-Mart´ ın, N. L. Diaz, P. Braccia, E. Fontana, M. S. Rudolph, P. Bermejo, A. Ijaz, S. Thanasilp, E. R. Anschuetz, and Z. Holmes, Nature Communications16, 7907 (2025)

work page 2025

[39] [39]

Quantum approximate optimization is computationally universal

S. Lloyd, arXiv preprint arXiv:1812.11075 (2018), arXiv:1812.11075

work page internal anchor Pith review Pith/arXiv arXiv 2018

[40] [40]

Wootton, Circuit model of quantum computation (2024)

J. Wootton, Circuit model of quantum computation (2024)

work page 2024

[41] [41]

Beals, S

R. Beals, S. Brierley, O. Gray, A. W. Harrow, S. Kutin, N. Linden, D. Shepherd, and M. Stather, Proceedings of the Royal Society A: Mathematical, Physical and Engi- neering Sciences469, 10.1098/rspa.2012.0686 (2013)

work page doi:10.1098/rspa.2012.0686 2012

[42] [42]

L. Chen, Y. Ren, R. Fan, and A. Jaffe, npj Quantum Information11, 10.1038/s41534-025-01063-4 (2025)

work page doi:10.1038/s41534-025-01063-4 2025

[43] [43]

Raussendorf and J

R. Raussendorf and J. Harrington, Physical Review Let- ters98, 10.1103/physrevlett.98.190504 (2007)

work page doi:10.1103/physrevlett.98.190504 2007

[44] [44]

M. S. Sarandy and D. A. Lidar, Physical Review Letters 95, 10.1103/physrevlett.95.250503 (2005)

work page doi:10.1103/physrevlett.95.250503 2005

[45] [45]

Quantum Computation by Adiabatic Evolution

E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution (2000), arXiv:quant-ph/0001106 [quant-ph]

work page internal anchor Pith review Pith/arXiv arXiv 2000

[46] [46]

Barenco, C

A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, Physical Review A52, 3457 (1995)

work page 1995

[47] [47]

Brylinski and R

J.-L. Brylinski and R. Brylinski, inMathematics of Quan- tum Computation, edited by R. Brylinski and G. Chen (Chapman & Hall/CRC, 2002) pp. 101–116

work page 2002

[48] [48]

M. J. Bremner, C. M. Dawson, J. L. Dodd, A. Gilchrist, A. W. Harrow, D. Mortimer, M. A. Nielsen, and T. J. Osborne, Phys. Rev. Lett.89, 247902 (2002)

work page 2002

[49] [49]

N. J. Ward, I. Kassal, and A. Aspuru-Guzik, The Journal of Chemical Physics130, 10.1063/1.3115177 (2009)

work page doi:10.1063/1.3115177 2009

[50] [50]

Gomes, A

N. Gomes, A. Mukherjee, F. Zhang, T. Iadecola, C.-Z. Wang, K.-M. Ho, P. P. Orth, and Y.-X. Yao, Advanced Quantum Technologies4, 10.1002/qute.202100114 (2021)

work page doi:10.1002/qute.202100114 2021

[51] [51]

Yeter-Aydeniz, R

K. Yeter-Aydeniz, R. C. Pooser, and G. Siopsis, Practi- cal quantum computation of chemical and nuclear energy levels using quantum imaginary time evolution and lanc- zos algorithms (2019)

work page 2019

[52] [52]

Gomes, F

N. Gomes, F. Zhang, N. F. Berthusen, C.-Z. Wang, K.-M. Ho, P. P. Orth, and Y. Yao, Journal of Chemical Theory and Computation16, 6256 (2020). 10

work page 2020

[53] [53]

Nishi, T

H. Nishi, T. Kosugi, and Y.-i. Matsushita, npj Quantum Information7, 10.1038/s41534-021-00409-y (2021)

work page doi:10.1038/s41534-021-00409-y 2021

[54] [54]

Lloyd, Science273, 1073 (1996)

S. Lloyd, Science273, 1073 (1996). Appendix A: Adapt-H QITE’s universality We present here a more rigorous argument for the uni- versality of Adapt-H QITE, introduced in Sec. III B 3

work page 1996

[55] [55]

At a point|ψ⟩, the tangent spaceT ψ is Tψ = |δψ⟩ ∈ H:⟨ψ|δψ⟩= 0 , i.e

The tangent space A pure state ofNqubits lives on the unit sphere of H= (C 2)⊗N, or, modulo the irrelevant global phase, in projective Hilbert spaceP(H). At a point|ψ⟩, the tangent spaceT ψ is Tψ = |δψ⟩ ∈ H:⟨ψ|δψ⟩= 0 , i.e. the orthogonal complement of|ψ⟩. Its complex di- mension is 2 N −1. Intuitively,T ψ collects the directions in which|ψ⟩can move while...

work page

[56] [56]

Expanding to first order in ∆τ, |ψ′⟩=|ψ⟩ −∆τ hm − ⟨hm⟩ |ψ⟩+O(∆τ 2), so the infinitesimal motion is |δψ⟩=−∆τ(h m − ⟨hm⟩)|ψ⟩

The QITE step as a tangent-space projection A single QITE infinitesimal step on the Hamiltonian termh m with imaginary-time increment ∆τproduces the normalised state |ψ′⟩= e−∆τ hm|ψ⟩√c , c=⟨ψ|e −2∆τ hm |ψ⟩. Expanding to first order in ∆τ, |ψ′⟩=|ψ⟩ −∆τ hm − ⟨hm⟩ |ψ⟩+O(∆τ 2), so the infinitesimal motion is |δψ⟩=−∆τ(h m − ⟨hm⟩)|ψ⟩. WritingP ⊥ ψ =1− |ψ⟩⟨ψ|for...

work page

[57] [57]

varyh m over e.g. all 2-local Hermitians, sweep out all tangent directions, conclude that adaptive-H QITE can move|ψ⟩wherever we like

Why one step does not spanT ψ It would be tempting to argue universality as follows: “varyh m over e.g. all 2-local Hermitians, sweep out all tangent directions, conclude that adaptive-H QITE can move|ψ⟩wherever we like.” However, this would be wrong. LetL 2 denote the real vector space of 2-local Hermi- tian operators supported on edges of the coupling g...

work page

[58] [58]

This is the orbit of the initial state|ψ 0⟩under the Lie groupGgenerated by the unitaries{e −itA(h)|h∈ L2, t∈R}, whereA(h) denotes the operator that QITE constructs for the termh

Universality via Lie-algebra closure Consider the set of states reachable by sequences of QITE infinitesimal steps with adaptively chosenh m ∈ L2. This is the orbit of the initial state|ψ 0⟩under the Lie groupGgenerated by the unitaries{e −itA(h)|h∈ L2, t∈R}, whereA(h) denotes the operator that QITE constructs for the termh. The Lie algebragofGis the smal...

work page

[59] [59]

Specifi- cally, any two-qubit gate involving connected qubits ac- cording toGwithin errorϵwill takeO(1/ϵ) adapt-H QITE steps (first-order Trotter-step error [39])

Cost: universality is not efficiency Any target state can be approached arbitrarily closely by some sequence of QITE micro-steps, but the length of that sequence may scale exponentially withN. Specifi- cally, any two-qubit gate involving connected qubits ac- cording toGwithin errorϵwill takeO(1/ϵ) adapt-H QITE steps (first-order Trotter-step error [39]). ...

work page