Numerical investigation of a MST conjecture for random Haar matrices
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematical Physics. The day in mathematical physics: rigorous models of physical systems.
Kai: I'm Kai.
Mira: And I'm Mira, here with Lev.
Kai: We're looking at the paper: "Numerical investigation of a MST conjecture for random Haar matrices".
Mira: Here's the gist of the paper. The state-to-state control time of finite-dimensional conservative bilinear quantum systems is bounded by the weight of minimum spanning trees (MST) derived from the drift matrices The question addressed here is to predict the asymptotic behavior of τ(d)SS as d → ∞, relying only on the intrinsic properties of the spectral sequence Λ and for a generic interaction operator B(d) Control Time and Conjectures The paper investigates whether the state-to-state control time τ(d)SS vanishes as the dimension d → ∞, which remains an open problem due to global correlations imposed by the Haar measure The deterministic upper bound on τ(d)SS is controlled from above by a constant multiple of the MST weight Md In the polynomial regime λk = k a with a > 3/2, the typical edge weight scales as p(d/vd) ≍ d(1/2-a), so the MST weight decays like d(3/2-a) → 0 and the control time vanishes in probability as d → ∞ (’general decay’, made rigorous for the surrogate in Section 2 and confirmed numerically for the exact model) The critical case λk = k 3/2 remains open, where this decay becomes only logarithmic The Surrogate Model Framework To make these estimates applicable to a typical configuration, independently of pathological worst cases, the authors draw the control operator B(d) from a generic, isotropic ensemble By an isotropic random matrix we mean a random skew-Hermitian matrix B ∈ u(d) whose law is unitarily invariant and whose eigenvalues admit a joint continuous density with respect to the Lebesgue measure The joint distribution of A˜(d) is intractable due to trace and orthogonality constraints, so they introduce an independent (i.i.d.) Gaussian surrogate where the drift entries A˜(d)jk are mutually independent Asymptotic Scaling of the MST Weight The authors apply a mean-field approximation by substituting the true matrix A˜(d) with a completely independent isotropic Gaussian matrix G(d) possessing identical marginal variances Theorem 3 establishes that for this surrogate, Md(G) satisfies omegaP d(3/2) √vd ln d!
Kai: ≤ Md(G) ≤ OP d(3/2) √vd ln d!
Mira: The empirical variance vd = O(d 3), which implies σd ∼ 3(10/3) d and thus the surrogate limit Md(G) = OP(1/√ln d) Validation and Thermodynamic Limit Numerical investigations up to dimension d = 18101 validate the general decay, confirm that the exact Haar model and the independent surrogate are statistically indistinguishable in mean at all tested dimensions (d = 100 to 18101) The observable model residual ∆Md = Md − Miid d fluctuates around zero with no detectable systematic bias, confirming the statistical indistinguishability of the two models in mean The renormalized observable y(d) = Miid d √ln d approaches the thermodynamic limit 10/3 from below as x(d) → 0 Model Consistency The direct agreement between the two models in mean provides strong numerical evidence that the Haar measure’s global unitary constraints do not alter the leading-order MST statistics The renormalized observable y(d) = Md √ln d for the exact system approaches 10/3 from below in direct parallel with the surrogate, confirming the transfer of the ansatz as a well-supported conjecture Graph Theory Background The MST is extracted using Kruskal’s algorithm, where the dominant cost is O(E log E) = O(d squared log d) Lemma 4 links the maximal edge weight wmax of the MST to the global connectivity threshold of the graph The critical weight wmax is placed at pc ∼ (ln d)/d, i.e., wmax ∼ 1/(σd √ln d) Lemma 5 provides the inverse transform sampling for surrogate edge weights W = Z−1 = √1/√−σ2 ln U Renormalized Observables vs Finite-Size Scaling Parameter The renormalized observable y(d) is expanded as y(d) = dσd1 + A/ln d + o(1/ln d) The empirical means cluster around the scaling envelope Md ∝ (ln d)−1/2 for both models The distinct scaling of the variances confirms that the geometric correlations of the Haar measure alter the fluctuation regime Inverse Transform Sampling for Surrogate Edge Weights The cumulative distribution function (CDF) of R is obtained by integration, FR(r) = 1 − exp − r2/σ2 The edge weight W = R−1 has a CDF given by the Fréchet distribution: FW(w) = exp − 1/σ2w2 The simulation proceeds via U = exp − 1/σ2W2, leading to W = √1/√−σ2 ln U Macroscopic Validation and Asymptotic Decay The empirical distributions of Md and Miid d do not exhibit significant heavy tails, validating the use of the Central Limit Theorem for the estimation of the expected limits The log-log regressions confirm the (ln d)−1/2 scaling envelope for both models The negative slopes obtained from the regressions support the macroscopic decay of the observables towards zero, which is consistent with Conjecture 1 Thermodynamic Limit Extraction on the Surrogate Model The renormalized observable y(d) = Miid d √ln d is expanded as a polynomial y(d) = α + βx(d) + γx(d)2 and fitted by a Weighted Least Squares Regression (WLSR) Under successive truncations of the lower dimensions, the extrapolated intercept α rises monotonically and stably toward the thermodynamic value 10/3 predicted by the surrogate model Model Consistency The residual ∆Md fluctuates around zero with no detectable systematic bias, confirming that the exact system and the independent surrogate share the same (ln d)−1/2 scaling and the same thermodynamic limit This direct agreement between the two models in mean provides strong numerical evidence that the Haar measure’s global unitary constraints do not alter the leading-order MST statistics The renormalized observable y(d) = Md √ln d for the exact system approaches 10/3 from below in direct parallel with the surrogate, confirming the transfer of the ansatz as a well-supported conjecture Numerical Investigation The computational protocol for the exact Haar model involves generating a random unitary matrix P ∈ U(d) according to the Haar measure and computing A˜(d) = P†A(d)P The computational bottleneck lies in the dense linear algebra operations which scale as O(d3), while the MST extraction scales only as O(d2) or O(d2ln d) For the independent surrogate model, this bottleneck is bypassed by directly instantiating edge weights via inverse transform sampling, scaling as O(d2ln d) The large-scale sampling up to d = 18101 was achieved with minimal computational overhead Graph Theory Background The MST is extracted using Kruskal’s algorithm, where every edge e ∈ E has a distinct continuous random weight We Lemma 4 links the maximal edge weight wmax of the MST to the global connectivity threshold of the graph The critical weight wmax is placed at pc ∼ (ln d)/d, i.e., wmax ∼ 1/(σd √ln d) Lemma 5 provides the inverse transform sampling for surrogate edge weights W = Z−1 = √1/√−σ2 ln U Numerical Investigation The computational protocol for the exact Haar model involves generating a random unitary matrix P ∈ U(d) according to the Haar measure and computing A˜(d) = P†A(d)P The computational bottleneck lies in the dense linear algebra operations which scale as O(d3) while the MST extraction scales only as O(d2) or O(d2ln d) For the independent surrogate model, this bottleneck is bypassed by directly instantiating edge weights via inverse transform sampling, scaling as O(d2ln d) The large-scale sampling up to d = 18101 was achieved with minimal computational overhead Graph Theory Background The MST is extracted using Kruskal’s algorithm, where every edge e ∈ E has a distinct continuous random weight We Lemma 4 links the maximal edge weight wmax of the MST to the global connectivity threshold of the graph The critical weight wmax is placed at pc ∼ (ln d)/d, i.e.
Paper summary: Kai: So we're looking at this paper here called "Numerical investigation of an MST conjecture for random Haar matrices". It’s about figuring out if the time it takes to steer one quantum state to another, which they call the state-to-state control time, vanishes as the dimension, d, gets really big.
Mira: Yeah, and they are trying to predict that behavior by looking at something called the minimum spanning tree weight derived from those drift matrices. The main thing they're tackling is whether this control time actually goes to zero when you have these global correlations imposed by the Haar measure.
Lev: From an engineering standpoint, what matters here is that if this control time vanishes, it means we can steer states very quickly, which implies we can do things with real hardware. But they're using a surrogate model to make these estimates work for a typical case rather than just worst-case scenarios.
Kai: Right. The paper sets up two conjectures about how the MST weight, which they call Md, should behave as the dimension d grows. They suggest one is that it decays to zero in general, and the other suggests a scaling based on this independent Gaussian surrogate model.
Mira: And they use this surrogate model because dealing with the exact Haar measure constraints is way too hard for a typical setup. They draw the control operator B from a generic, isotropic ensemble, which means it's random and has no preferred axis in Hilbert space.
Lev: I wonder how that relates to what we actually build. If we use this surrogate model, does it give us a realistic idea of the overhead when we try to run these kinds of control algorithms on real superconducting qubits?
Kai: They do, and they use a specific approximation where they replace the true drift matrix with an independent Gaussian matrix G that has identical marginal variances. This gives them an upper bound on Md(G) that scales like d to the power of three over square root of d times the logarithm of d.
Mira: That scaling leads to the idea that for this surrogate, the typical MST weight, Md(G), actually decays like one over the square root of log d. This is a big step because it suggests a general decay to zero in probability as the dimension goes up.
Paper summary: Lev: If we take that scaling, what does that mean for us in terms of actual computation? Is this decay fast enough to be practical, or is it still too slow for the overhead we see on real quantum computers?
Kai: The paper shows numerical investigations up to dimension d equal to eighteen thousand one hundred and eleven. They found that the exact Haar model and this independent surrogate model are statistically indistinguishable in mean across all those tested dimensions.
Mira: That statistical indistinguishability is key, because it suggests that the global constraints of the Haar measure don't mess with the leading-order statistics of these MST weights. The renormalized observable y of d, when scaled by the square root of log d, approaches a specific value from below as the scaling parameter x goes to zero.
Lev: So if we take that limit they find, that this value is one ten over three. That’s what you get when you look at the thermodynamic limit on this surrogate model. But does getting to one ten over three really translate into something useful for controlling quantum systems?
Kai: The authors confirm that the exact system's observable, y of d times the square root of log d, also approaches one ten over three from below in parallel with the surrogate model results. This direct agreement gives strong support to their conjecture that this scaling is correct.
Mira: It really suggests that for systems scaling with k to the power of three over two, this decay to zero is happening in a predictable way dictated by the spectral sequence alone. It’s not just some accidental feature of the specific interaction operator B you pick.
Lev: The paper also talks about graph theory stuff here, like how they link the maximum edge weight of the MST to a critical weight pc that scales like log d over d. That means the maximum connection in this structure is getting relatively small as d increases.
Kai: And they use inverse transform sampling for their surrogate edge weights, which gives them a way to calculate those weights directly instead of relying on complex integrations, scaling that calculation at two to the k times log n complexity for the surrogate model.
Paper summary: Mira: The numerical results show that the empirical distributions of Md and this independent one do not have heavy tails, so they can trust using things like the central limit theorem for estimating those limits. The log-log plots confirm a one over square root of d scaling envelope for both models, which supports the macroscopic decay toward zero.
Lev: What they don't explicitly cover is how this applies to systems where k is exactly three over two, because that’s the critical case where the decay slows down to something logarithmic instead of vanishing entirely.
Kai: They did mention that for a spectrum scaling as k to the power of three over two, the decay becomes only logarithmic, which they say remains an open problem. That's where they leave things for future investigation.
Mira: So to wrap up this paper on "Numerical investigation of an MST conjecture for random Haar matrices", the main thrust is that numerical evidence strongly supports the idea that the state-to-state control time vanishes as the dimension d increases, provided we use a generic interaction operator B.
Kai: They showed this by comparing their exact Haar model against an independent Gaussian surrogate model, and they found both models agreed statistically in mean across dimensions up to d equal to eighteen thousand one hundred and eleven. This suggests the global constraints don't change the leading-order scaling behavior of the minimum spanning tree weight.
Lev: From my side, what this means is that if we are designing error correction protocols, we can probably rely on this general decay trend for large systems, even though I still have to worry about how fast that decay actually translates into a useful control time for real hardware.
Mira: Exactly. The paper extracts a thermodynamic limit of one ten over three from the surrogate model, and this value is approached by both the exact system and the surrogate from below once you use the correct scaling variable. It confirms that for systems with k to the power of three over two, we are looking at a specific type of decay dictated by the spectral sequence itself.
Kai: So, in short, they've numerically validated a conjecture about how quantum control time scales with dimension, showing it decays toward zero under generic conditions. That’s what this paper is about.
Conclusion: Kai: So this paper, "Numerical investigation of a MST conjecture for random Haar matrices," it's basically checking if the time it takes to move between quantum states gets smaller as you add more dimensions, d.
Mira: Yeah, they are looking at that minimum spanning tree weight and whether it actually goes to zero when those global constraints from the Haar measure are in play.
Kai: They use this surrogate model—that independent random matrix setup—to make the math manageable because the exact Haar model is just too complicated for a typical lab setting.
Mira: And what they found is that across a huge range of dimensions, say up to eighteen thousand one hundred and eleven, their exact system and their surrogate model are statistically indistinguishable in mean.
Kai: That means the global rules of quantum mechanics aren't messing up the basic statistical idea of how those connections form in the matrix structure.
Mira: Exactly. And they confirmed that both models follow this same scaling envelope where a certain observable approaches one ten over three from below as the dimension scales down to zero.
Kai: So, if you listen to this and don't get too lost in all the notation, it means we have numerical evidence supporting that state-to-state control time does vanish for generic interaction operators.
Mira: It suggests that for systems where the interaction strength scales like k to the power of three over two, this decay is predictable based on the spectral sequence itself.
Kai: Right. But there's still that critical case where it gets logarithmic instead of vanishing, which is what they left open as future work.
Mira: That’s where we need to look next—how those specific interaction operators affect that critical scaling behavior.
T. Chambrion, C. Mendico
Institut de Recherche Mathématique Avancée UMR 7501, University of Strasbourg · Université Bourgogne Europe, CNRS
math-ph, math.MP, math.OC
Submitted: 2026-11-10
Updated: 2026-11-10
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 81/100
The gist: The state-to-state control time of finite-dimensional conservative bilinear quantum systems is bounded by the weight of minimum spanning trees (MST) derived from the drift matrices The question…
Key concepts
- State-to-state control time $\tau(d)SS$
- This measures how long it takes to control one quantum state to another. The paper explores if this time goes to zero as the system size $d$ becomes very large, which is a key open question in the field.
- Minimum Spanning Tree (MST) Weight $M_d$
- The MST is a structure connecting all points in a graph with the minimum total edge weight. The paper uses its weight to bound the control time. The typical edge weights scale in a way that suggests this weight decays as $d^{3/2-a}$, leading to vanishing control time.
- Haar Measure vs. Gaussian Surrogate
- The Haar measure represents the true, complex constraints of random quantum matrices. The Gaussian surrogate uses independent, identically distributed entries for approximation. The key finding is that these two models are statistically indistinguishable in mean and share the same scaling limits, implying the global constraints have a minor effect on leading-order MST statistics.
Terminology
Summary
The state-to-state control time of finite-dimensional conservative bilinear quantum systems is bounded by the weight of minimum spanning trees (MST) derived from the drift matrices The question addressed here is to predict the asymptotic behavior of τ(d)SS as d → ∞, relying only on the intrinsic properties of the spectral sequence Λ and for a generic interaction operator B(d)
Control Time and Conjectures
The paper investigates whether the state-to-state control time τ(d)SS vanishes as the dimension d → ∞, which remains an open problem due to global correlations imposed by the Haar measure The deterministic upper bound on τ(d)SS is controlled from above by a constant multiple of the MST weight Md In the polynomial regime λk = k a with a > 3/2, the typical edge weight scales as p(d/vd) ≍ d(1/2-a), so the MST weight decays like d(3/2-a) → 0 and the control time vanishes in probability as d → ∞ (’general decay’, made rigorous for the surrogate in Section 2 and confirmed numerically for the exact model) The critical case λk = k 3/2 remains open, where this decay becomes only logarithmic
The Surrogate Model Framework
To make these estimates applicable to a typical configuration, independently of pathological worst cases, the authors draw the control operator B(d) from a generic, isotropic ensemble By an isotropic random matrix we mean a random skew-Hermitian matrix B ∈ u(d) whose law is unitarily invariant and whose eigenvalues admit a joint continuous density with respect to the Lebesgue measure The joint distribution of A˜(d) is intractable due to trace and orthogonality constraints, so they introduce an independent (i.i.d.) Gaussian surrogate where the drift entries A˜(d)jk are mutually independent
Asymptotic Scaling of the MST Weight
The authors apply a mean-field approximation by substituting the true matrix A˜(d) with a completely independent isotropic Gaussian matrix G(d) possessing identical marginal variances Theorem 3 establishes that for this surrogate, Md(G) satisfies omegaP d(3/2) √vd ln d! ≤ Md(G) ≤ OP d(3/2) √vd ln d! The empirical variance vd = O(d 3), which implies σd ∼ 3(10/3) d and thus the surrogate limit Md(G) = OP(1/√ln d)
Validation and Thermodynamic Limit
Numerical investigations up to dimension d = 18101 validate the general decay, confirm that the exact Haar model and the independent surrogate are statistically indistinguishable in mean at all tested dimensions (d = 100 to 18101) The observable model residual ∆Md = Md − Miid d fluctuates around zero with no detectable systematic bias, confirming the statistical indistinguishability of the two models in mean The renormalized observable y(d) = Miid d √ln d approaches the thermodynamic limit 10/3 from below as x(d) → 0
Model Consistency
The direct agreement between the two models in mean provides strong numerical evidence that the Haar measure’s global unitary constraints do not alter the leading-order MST statistics The renormalized observable y(d) = Md √ln d for the exact system approaches 10/3 from below in direct parallel with the surrogate, confirming the transfer of the ansatz as a well-supported conjecture
Graph Theory Background
The MST is extracted using Kruskal’s algorithm, where the dominant cost is O(E log E) = O(d squared log d) Lemma 4 links the maximal edge weight wmax of the MST to the global connectivity threshold of the graph The critical weight wmax is placed at pc ∼ (ln d)/d, i.e., wmax ∼ 1/(σd √ln d) Lemma 5 provides the inverse transform sampling for surrogate edge weights W = Z−1 = √1/√−σ2 ln U
Renormalized Observables vs Finite-Size Scaling Parameter
The renormalized observable y(d) is expanded as y(d) = dσd1 + A/ln d + o(1/ln d) The empirical means cluster around the scaling envelope Md ∝ (ln d)−1/2 for both models The distinct scaling of the variances confirms that the geometric correlations of the Haar measure alter the fluctuation regime
Inverse Transform Sampling for Surrogate Edge Weights
The cumulative distribution function (CDF) of R is obtained by integration, FR(r) = 1 − exp − r2/σ2 The edge weight W = R−1 has a CDF given by the Fréchet distribution: FW(w) = exp − 1/σ2w2 The simulation proceeds via U = exp − 1/σ2W2, leading to W = √1/√−σ2 ln U
Macroscopic Validation and Asymptotic Decay
The empirical distributions of Md and Miid d do not exhibit significant heavy tails, validating the use of the Central Limit Theorem for the estimation of the expected limits The log-log regressions confirm the (ln d)−1/2 scaling envelope for both models The negative slopes obtained from the regressions support the macroscopic decay of the observables towards zero, which is consistent with Conjecture 1
Thermodynamic Limit Extraction on the Surrogate Model
The renormalized observable y(d) = Miid d √ln d is expanded as a polynomial y(d) = α + βx(d) + γx(d)2 and fitted by a Weighted Least Squares Regression (WLSR) Under successive truncations of the lower dimensions, the extrapolated intercept α rises monotonically and stably toward the thermodynamic value 10/3 predicted by the surrogate model
The residual ∆Md fluctuates around zero with no detectable systematic bias, confirming that the exact system and the independent surrogate share the same (ln d)−1/2 scaling and the same thermodynamic limit This direct agreement between the two models in mean provides strong numerical evidence that the Haar measure’s global unitary constraints do not alter the leading-order MST statistics The renormalized observable y(d) = Md √ln d for the exact system approaches 10/3 from below in direct parallel with the surrogate, confirming the transfer of the ansatz as a well-supported conjecture
Numerical Investigation
The computational protocol for the exact Haar model involves generating a random unitary matrix P ∈ U(d) according to the Haar measure and computing A˜(d) = P†A(d)P The computational bottleneck lies in the dense linear algebra operations which scale as O(d3), while the MST extraction scales only as O(d2) or O(d2ln d) For the independent surrogate model, this bottleneck is bypassed by directly instantiating edge weights via inverse transform sampling, scaling as O(d2ln d) The large-scale sampling up to d = 18101 was achieved with minimal computational overhead
The MST is extracted using Kruskal’s algorithm, where every edge e ∈ E has a distinct continuous random weight We Lemma 4 links the maximal edge weight wmax of the MST to the global connectivity threshold of the graph The critical weight wmax is placed at pc ∼ (ln d)/d, i.e., wmax ∼ 1/(σd √ln d) Lemma 5 provides the inverse transform sampling for surrogate edge weights W = Z−1 = √1/√−σ2 ln U
The computational protocol for the exact Haar model involves generating a random unitary matrix P ∈ U(d) according to the Haar measure and computing A˜(d) = P†A(d)P The computational bottleneck lies in the dense linear algebra operations which scale as O(d3) while the MST extraction scales only as O(d2) or O(d2ln d) For the independent surrogate model, this bottleneck is bypassed by directly instantiating edge weights via inverse transform sampling, scaling as O(d2ln d) The large-scale sampling up to d = 18101 was achieved with minimal computational overhead
The MST is extracted using Kruskal’s algorithm, where every edge e ∈ E has a distinct continuous random weight We Lemma 4 links the maximal edge weight wmax of the MST to the global connectivity threshold of the graph The critical weight wmax is placed at pc ∼ (ln d)/d, i.e.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Enhanced Control Time Prediction for Quantum Systems: The improved system can predict whether state-to-state control time vanishes as dimension d approaches infinity by comparing empirical MST weights against theoretical scaling predictions derived from both exact Haar models and independent Gaussian surrogate models.
-
Robust Asymptotic Limit Determination: The AI can reliably determine the thermodynamic limit alpha = 10/3 for the spectral scaling k 3/2 by analyzing how both the exact Haar model and the surrogate model approach this value from below once the correct scaling variable 1 over ln d is adopted.
-
Model Consistency Verification: The improved system can statistically confirm that global unitary constraints imposed by the Haar measure do not alter leading-order MST statistics by calculating a signal to noise ratio for the residual difference between empirical means of the exact and surrogate models, which remains below 1.7 across tested dimensions.
Sources
Related papers
- Existence of a fluid phase for the two-dimensional one-component plasma
- The Huang-Yang conjecture for the low-density Fermi gas
- Anderson localisation in infinite and finite resonator crystals with long-range interactions
- Free energy and spectral edge of the SYK model
- Anderson localization for 1-d quasi-periodic Schr"odinger operators with degenerate weights
- Irregular SLE(4) martingales and isomonodromic deformations