Nearly Optimal Measurement Scheduling for Partial Tomography of Quantum States

• Initial measurement bounds reached 10^13 repetitions for a 112-spin-orbital chemistry system, motivating more scalable tomography methods.Source: §I · p. 1
• k-body RDMs provide tractable information for estimating energies, gradients, multipole moments, spin correlations, and entanglement-related properties.Source: §I · p. 1
• Naive partial tomography requires O(N^4) unique measurement circuits because noncommuting observables require state re-preparation.Source: §I · p. 1
• Prior graph-based approaches offered limited scaling improvements, while the paper targets regularity in local qubit and fermionic commutation relations.Source: §I · p. 2
• The paper proposes qubit k-RDM schemes scaling as O(3^k log^(k−1)N), fermionic lower bounds and protocols, and anti-commuting measurement schemes with O(N^4/ω) measurements.Source: §I · p. 2

• Qubit k-RDMs contain expectation values of tensor products of k single-qubit Pauli operators, whereas fermionic k-RDMs contain products of k creation and k annihilation operators.Source: §II · p. 2
• Fermionic k-RDMs can equivalently be computed from expectation values of 2k-Majorana operators, such as four-Majorana terms for the fermionic 2-RDM.Source: §II · p. 2
• Repeated preparation and measurement estimates observables in parallel whenever they belong to a mutually commuting clique, making clique count the central tomography cost.Source: §II · p. 2
• The approach must differ between qubits and fermions because spatially separated qubit operators commute, while corresponding fermionic operators often do not.Source: §II · p. 2

Resource comparison

• Table I compares prior and proposed measurement partitions, circuit resources, classical costs, full-2-RDM coverage, and symmetry compatibility.Source: Table I · p. 3

Qubit operators

• Binary partitioning measures all k-local qubit operators using O(3^k log^(k−1)N) cliques, with 6⌈log N⌉+3 cliques for k=2.Source: §III · p. 3

Fermion operators

• Fermionic k-RDMs require more measurements because their 2k-Majorana operators anti-commute more extensively than local qubit operators.Source: §III · p. 3
• Theorem 1 gives a worst-case lower bound of Ω(ϵ^-2N^k) state preparations for fermionic k-RDM estimation using Clifford operations and computational-basis measurement.Source: §III · p. 3
• Majorana pairings form maximally sized commuting cliques, enabling simultaneous measurement through basis changes with circuit depth O(N).Source: §III · pp. 3–4
• For fermionic 2-RDMs, the scheme reaches 10^?N^2 cliques as rendered in the passage, leaving a factor 5/2 gap from the lower bound.Source: §III · p. 4

Symmetry constraints

• Symmetry constraints eliminate certain RDM terms and reduce the required clique count, with implementations converging quickly to the leading-order estimate for up to four symmetries.Source: §III · p. 4, Figure 1 · p. 4

IV. MEASURING ANTI-COMMUTING LINEAR COMBINATIONS OF LOCAL FERMIONIC OPERATORS

• Anti-commuting Majorana cliques contain 2N−3 operators, but covering all 4-Majorana operators requires at least Ω(N^3) such cliques.The lower bound follows because any anti-commuting Pauli or Majorana clique has at most 2N+1 elements.Source: §IV · p. 4
• A real linear combination of clique elements can be measured in one shot after unitary transformation to a chosen Pauli operator.The normalized combination is Hermitian, traceless, and squares to identity, enabling the Pauli-like transformation.Source: §IV · p. 4
• O(N^4/ω) subsets estimate arbitrary linear combinations of 4-Majorana operators using circuits with ω gates and depth ω.Using all operators in a clique requires depth N−2 + O(1), whereas restricting each subset to ω elements reduces the circuit cost.Source: §IV · pp. 4–5

V. CONCLUSION

• O(3^k log^(k−1) N) circuits measure all k-local qubit operators, giving a poly-logarithmic dependence on system size.The binary partition strategy produces an exponential improvement over previous qubit-tomography approaches.Source: §V · p. 5
• Ω(N^⌈k/2⌉) unique circuits are necessary for directly sampling all k-local fermionic operators, establishing an exponential separation from qubit systems.The lower bound applies to fermionic systems, while the paper reaches it for k = 2 and k = 4.Source: §V · p. 5
• O(N^2) circuits suffice to estimate the entire fermionic 2-RDM to constant error.This achieves the lower-bound scaling for the fermionic 2-RDM case.Source: §V · p. 5
• The measurement schemes target the tomography bottleneck that can make partial state characterization prohibitive on experimental quantum devices.The conclusion frames optimized measurement scheduling as important for near-term quantum simulation.Source: §V · p. 5

Appendix A: Schemes for partial state tomography of qubit k-RDMs

• Pauli words specify one X, Y, or Z measurement basis per qubit, and their cliques contain tensor-product operators using those selected bases.Sampling a word estimates every contained Pauli operator simultaneously because the operators are qubit-wise commuting.Source: Appendix A · p. 6
• For k = 2, binary partitions separate every pair of qubits, and basis assignments reduce the construction to 6⌈log N⌉ + 3 cliques.The binary representation of qubit indices guarantees that every distinct pair differs at some partition level.Source: Appendix A · pp. 6–7
• Figure 2 depicts the binary-partition construction for O(log N) two-qubit cliques and its O(log^2 N) extension to three-qubit cliques.The two panels correspond to the pair-separation scheme and the recursive three-index partitioning scheme.Source: Figure 2 · p. 7, Appendix A · p. 7
• For k = 3, the construction first splits the three indices into two subsets and recursively partitions the subset containing two indices.Because the two unsplit indices lie in a contiguous block, only earlier partition levels need to be iterated.Source: Appendix A · p. 7
• O(3^k log^(k−1) N) Pauli-word cliques contain all k-qubit operators generated by the partition scheme.At each partition level, the construction considers the possible ways to divide the k operator locations into nonempty subsets.Source: Appendix A · p. 7

Appendix B: Upper bounds on the size of commuting cliques of Majorana operators.

• The appendix defines M_l^k as the largest number of mutually commuting k-Majoranas formed from l unique Majorana terms.The bounds are developed inductively, beginning with the all-anticommuting one-Majorana case.Source: Appendix B · p. 7
• For even k, counting shared terms reduces the clique-size problem to commuting (k−1)-Majoranas on l−1 terms.The argument identifies a shared Majorana term among sufficiently many operators and removes it while preserving commutation.Source: Appendix B · p. 7
• For odd k, every operator must share at least one term with a chosen operator, enabling a reduction to a lower-order Majorana clique.In the large-l limit, the appendix further argues that the largest odd-k cliques must share a single common term.Source: Appendix B · pp. 7–8
• Pairing the 2N one-Majorana operators yields commuting cliques whose size is exactly the derived upper bound for even k in the large-N limit.Thus the pairing construction is optimal in the number of commuting 2k-Majorana operators per measurement circuit.Source: Appendix B · p. 8
• The bound is observed for k = 3 when l ≥ 315, while the authors expect the general threshold scaling to be substantially tighter than the worst-case k^2 estimate.The stated threshold corresponds to systems with more than eight fermions.Source: Appendix B · p. 8

Fermionic partition strategy

• Pairing all indices into non-overlapping pairs produces commuting cliques containing every 2-Majorana operator.The pairing scheme is optimal when N is a power of 2 and is modified for other N without changing the asymptotic scaling.Source: Appendix C · p. 8

General N

• For non-power-of-two N, unpaired elements are accounted for while preserving the optimal asymptotic scaling.The pairing-generation code is included in the OpenFermion package [31].Source: Appendix C · p. 8

4-Majorana coverage

• Each clique of commuting 2-Majorana operators contains commuting products, but additional cliques are required so every 4-Majorana operator is covered.The construction enlarges the clique family so each four-element Majorana set appears through two compatible pairings.Source: Appendix C · p. 8
• The case |I0|=2 is handled by parallel pairings across recursively defined blocks, requiring 4 × 4^(n−1) cliques at each scale.The |I0|=3 or |I0|=1 case requires iterating combinations of internal and external pairs across scales.Source: Appendix C · pp. 8–9

Fermionic partition strategy

• O(N^2) cliques suffice to contain all 4-Majorana operators under the partition strategy.The construction handles cases where subsets have sizes 1, 2, or 3 and combines pairings across recursively defined blocks.Source: Appendix C · p. 9, Figure 3 · p. 9

Symmetry-based reduction

• Symmetries partition Majorana operators into bins labeled by whether each operator commutes or anticommutes with every symmetry.A k-Majorana operator commutes with a symmetry when an even number of its constituent Majorana terms anticommute with it.Source: Appendix D · p. 9

Clique construction

• The symmetry-conserved 2-RDM is covered by cliques of 4-Majorana operators whose four labels form a binary parallelogram.The labels are s, s+δ, s+α, and s+α+δ in binary arithmetic.Source: Appendix D · p. 9
• Within-bin quadruples and between-bin pairings together cover all required symmetry-conserved 4-Majorana operators.The three possible zero-coordinate cases for α, δ, or α+δ determine which bin pairs are iterated.Source: Appendix D · p. 9

Scaling

• The total clique-cover cost is 2^(Nsym−1)(B^2 + 2B ln(B) + ln(B)^2), where B is the largest bin size.When symmetries divide the Majoranas evenly, B = 2^N × 2^(−Nsym).Source: Appendix D · p. 10

Implementation

• Algorithm D summarizes the symmetry-constrained iteration using Hamming-weight ordering and parallel iteration routines.The implementation relies on iterQuad, pairBetween, and parallelIterate.Source: Appendix D · p. 10

Parallel iteration

• L^2 iterations are achieved when K is smaller than the smallest factor of L, matching the lower bound for covering all cross-list pairs.The construction uses modular indexing across K lists.Source: Appendix E · p. 10

Padding strategy

• For composite L, padding to L′ adds only a logarithmic correction, giving runtime L^2 + 2L log(L) + log(L)^2.The prime number theorem gives L′ − L ∼ log(L) when K ≤ L.Source: Appendix E · p. 10

Scope

• The appendix hypothesizes that asymptotic L^2 iteration may be achievable for all K ≤ L but does not provide such a construction.The stated construction instead relies on the smallest-factor condition or padding.Source: Appendix E · p. 10

Measurement transformations

• Under Jordan-Wigner encoding, partial-swap rotations transform sums of anticommuting Majorana operators into a single measurable Majorana operator.After the rotations remove support on the other terms, the remaining operator can be measured in the final Pauli basis.Source: Appendix F · pp. 10–11

Swap-network measurement

• Majorana swap networks require maximum circuit depth 3N and total maximum gate depth 3N^2 before locally reading out the desired pairs.Each timestep has depth 3, and N timesteps suffice because each Majorana can move up to two positions per timestep.Source: Appendix F · pp. 10–11

Symmetry verification

• Swap gates preserve global parity, allowing parity to be measured alongside the target clique for symmetry verification.The parity can provide an error-mitigation check after the basis-change circuit.Source: Appendix F · p. 11

Bravyi-Kitaev alternative

• The Bravyi-Kitaev alternative maps local fermionic operators to O(log N)-qubit operators, yielding (3 log N)^(O(log N)) measurement settings with single-qubit rotations.The fermionic operator set is sparse, containing O(N^4) terms, which may permit further sparsification.Source: Appendix F · p. 11

Measurement transformations

• The resulting measurement circuits use linear gate count and depth on a line without ancillary qubits for the relevant operator sets.The circuit can remove terms from both ends in parallel, leaving one Majorana after N−2 layers.Source: Appendix F · p. 11

Anticommuting-clique bound

• An anticommuting clique of Pauli or Majorana operators has maximum size 2^N + 1 and is unitarily equivalent to the 2^N Majoranas plus global parity.The bound follows from partitioning Pauli operators by their commutation patterns.Source: Appendix F · p. 11

• Mi ∼ ϵ^-2 state preparations and measurements are required to estimate each 2k-Majorana expectation value to error ϵ in the worst case.The bound is tight for a state whose measurement variance reaches the upper limit.Source: Appendix H · p. 12
• Only commuting operators can be estimated in parallel, so the number of 2k-Majorana operators measurable per preparation is bounded by the commuting-operator partition result.The resulting preparation bound follows by combining this restriction with the per-operator measurement requirement.Source: Appendix H · p. 12
• Clifford circuits followed by computational-basis readout are equivalent to measuring commuting Pauli operators on the original state.This correspondence underlies the preparation-count lower bound for fermionic k-RDM estimation.Source: Appendix H · p. 12
• Adding ancillas prepared in |0⟩ cannot make non-commuting system Pauli operators simultaneously measurable through Clifford circuits.Ancilla-supported observables either provide no information or reproduce direct system-Pauli measurements; when both provide information, commutation on the system follows.Source: Appendix H · p. 12
• The worst-case tightness argument does not describe every state: N-representability can create beneficial covariance that lowers variance for some linear combinations.The maximally mixed state has uncorrelated measurements and attains Var(⟨Γi⟩) = 1/(4Mi).Source: Appendix H · p. 12