Scaling the Deterministic Spectral Manifold to Post-Quantum Query Standards

We initiate the study of a new model of query complexity of Boolean functions where, in addition to 0 and 1, the oracle can answer queries with ``unknown''. The query algorithm is expected to output the function value if it can be conclusively determined by the partial information gathered, and it must output ``unknown'' if not. We formalize this model by using Kleene's strong logic of indeterminacy on three variables to capture unknowns. We call this model the `u-query model'. We relate the query complexity of functions in the new u-query model with their analogs in the standard query model. We show an explicit function that is exponentially harder in the u-query model than in the usual query model. We give sufficient conditions for a function to have u-query complexity asymptotically the same as its query complexity. Using u-query analogs of the combinatorial measures of sensitivity, block sensitivity, and certificate complexity, we show that deterministic, randomized, and quantum u-query complexities of all total Boolean functions are polynomially related to each other, just as in the usual query models.We initiate the study of a new model of query complexity of Boolean functions where, in addition to 0 and 1, the oracle can answer queries with ``unknown''. The query algorithm is expected to output the function value if it can be conclusively determined by the partial information gathered, and it must output ``unknown'' if not. We formalize this model by using Kleene's strong logic of indeterminacy on three variables to capture unknowns. We call this model the `u-query model'. We relate the query complexity of functions in the new u-query model with their analogs in the standard query model. We show an explicit function that is exponentially harder in the u-query model than in the usual query model. We give sufficient conditions for a function to have u-query complexity asymptotically the same as its query complexity. Using u-query analogs of the combinatorial measures of sensitivity, block sensitivity, and certificate complexity, we show that deterministic, randomized, and quantum u-query complexities of all total Boolean functions are polynomially related to each other, just as in the usual query models.

arXiv:2412.06395Dec 9, 20240 citations

Quantum Log-Determinant Methods for Torsion-Sensitive Topological Data Analysis

Dimitrios Thanos, Caesnan Leditto, Adam Wesolowski +2 more

Betti numbers are central to topological data analysis but fail to capture torsion in integral homology. Torsion can distinguish topological structures with identical Betti numbers, and examples from classical topological data analysis show that it can affect the topology inferred from data. Related torsion-sensitive quantities are also known to have practical applications in graph-based machine learning, including biomedical applications. We investigate how quantum spectral methods can access this additional information. Log pseudodeterminants, obtained by summing the logarithms of the nonzero boundary-Laplacian eigenvalues, summarize spectral information about a simplicial complex. Under explicit topological assumptions, an alternating combination of these quantities gives the size of a higher critical group, the higher-dimensional analogue of a graph sandpile group. With stronger certification, a related construction recovers the size of the torsion subgroup in homology itself. This is, to our knowledge, the first provably correct quantum estimator of integral-homology torsion order. We give a new quantum algorithm for estimating these quantities, with explicit dependence on how the input is queried, the required accuracy, and the spectral gaps. Exact spectra for balanced multipartite clique complexes provide favorable gaps, and a related construction gives an explicit torsion-bearing benchmark. With compact query access, the algorithm need not construct the exponentially large boundary matrices explicitly. For a restricted torsion-bearing family, a tailored amplitude-estimation routine uses quadratically fewer queries than any randomized classical algorithm given comparable access when estimating the log pseudodeterminant. Estimating the full, unnormalized quantity to fixed additive error still costs in proportion to the candidate-space dimension $D$ .Betti numbers are central to topological data analysis but fail to capture torsion in integral homology. Torsion can distinguish topological structures with identical Betti numbers, and examples from classical topological data analysis show that it can affect the topology inferred from data. Related torsion-sensitive quantities are also known to have practical applications in graph-based machine learning, including biomedical applications. We investigate how quantum spectral methods can access this additional information. Log pseudodeterminants, obtained by summing the logarithms of the nonzero boundary-Laplacian eigenvalues, summarize spectral information about a simplicial complex. Under explicit topological assumptions, an alternating combination of these quantities gives the size of a higher critical group, the higher-dimensional analogue of a graph sandpile group. With stronger certification, a related construction recovers the size of the torsion subgroup in homology itself. This is, to our knowledge, the first provably correct quantum estimator of integral-homology torsion order. We give a new quantum algorithm for estimating these quantities, with explicit dependence on how the input is queried, the required accuracy, and the spectral gaps. Exact spectra for balanced multipartite clique complexes provide favorable gaps, and a related construction gives an explicit torsion-bearing benchmark. With compact query access, the algorithm need not construct the exponentially large boundary matrices explicitly. For a restricted torsion-bearing family, a tailored amplitude-estimation routine uses quadratically fewer queries than any randomized classical algorithm given comparable access when estimating the log pseudodeterminant. Estimating the full, unnormalized quantity to fixed additive error still costs in proportion to the candidate-space dimension $D$.

quant-pharXiv:2609.40216Oct 1, 20260 citations

Evaluation of exact quantum query complexities by semidefinite programming

Kıvanç Uyanık

Quantum Information ProcessingApr 26, 20190 citations

A Five-Part Validation-Grade Resolution of BPP = P through Ricci Flow, Spectral Equivalence, and Holographic Entropy Bounding

Forrest Forrest M. Anderson

A Five-Part Validation-Grade Resolution of BPP = P through Ricci Flow, Spectral Equivalence, and Holographic Entropy Bounding This suite presents a complete, five-part validation-grade resolution of the \bm{\text{BPP} = \text{P}} (derandomization) conjecture. Moving beyond traditional, pseudorandom generator (PRG) approximations which suffer from structural verification gaps, this framework translates discrete computational complexity into continuous geometric topology. By embedding the execution trajectories of a bounded-error probabilistic polynomial-time (\bm{\text{BPP}}) machine into a 5-dimensional Lorentzian manifold, computational randomness is mathematically formalized as unmapped curvature and solenoidal noise. Through the systematic application of a dissipative Ricci flow, this noise is annihilated, forcing chaotic state-branching to collapse into a stable, unique deterministic geodesic. The structural integrity of this reduction is validated by proving an exact spectral equivalence between the randomized transition operators and the deterministic execution pathways. Using a holographic interlock, the bulk computational entropy is bounded to a 4-dimensional boundary surface, demonstrating zero loss of algorithmic information. Temporal monotonicity and non-anticipatory information flux are rigorously enforced via a causal seal, restricting all valid computation strictly within the input's light-cone. Finally, an observer-independent Agnostic Replication Interface (ARI) is established, mapping the global boundary states to a universal parity scalar (\bm{\Xi_{obs} = 1}). This five-part suite provides the definitive mathematical infrastructure required for the absolute derandomization of randomized polynomial-time algorithms, rendering the equivalence universally replicable across any computational architecture. Global Architecture: How the 5-Package Suite Resolves, Validates, Seals, and Replicates The resolution operates as a continuous pipeline across five distinct mathematical layers. Rather than treating the packages as isolated proofs, they form a unified, chronological sequence where the outputs of the preceding layer dictate the boundary conditions of the next. [Package A: Initial Manifold] — Dissipates Noise via Ricci Flow [Package B: Topological Lift] → Constrains Paths via Flow Governor [Package C: Spectral Interlock] → Audits Information via Boundary Matching [Package D: Causal Seal] Temporal Monotonicity & Light-Cones > Enforces V [Package E: Agnostic Interface] → Outputs Universal Parity Scalar (E _obs = 1) I. Resolution Mechanics (Packages A & B) The core resolution focuses on eliminating the combinatorial explosion of a randomized algorithm's branching state-space. • Package A initializes a smooth, regular 5D Lorentzian manifold (\bm{\mathcal{M}}) and establishes an epistemic noise floor. It treats probabilistic variance as localized geometric curvature (\bm{R_{\mu\nu}}). By introducing the Harmonic Scrubber (\bm{\Psi_{det}}), it runs a geometric Ricci flow equation (\bm{\frac{\partial}{\partial t}g_{ij} = -2R_{ij}}) that mathematically "smooths out" this curvature, cooling the system into a stable, flat invariant baseline (\bm{\gamma}). • Package B performs a topological lift, mapping the discrete Boolean circuit logic directly onto this smoothed manifold. To prevent the computational pathways from cross-intersecting or splitting into new randomized branches, it deploys the Laminar Flow Governor (\bm{\Gamma}). This enforces a strict solenoidal constraint (\bm{\nabla \cdot \mathbf{v} = 0}), transforming a highly chaotic probabilistic vector field into a collection of laminar, unique, and parallel deterministic geodesics. II. Validation Mechanics (Package C) To prove that the smoothing and flattening performed by the resolution did not alter the fundamental logic or correctness of the underlying algorithm, an exact informational audit is required. • Package C establishes this validation through the Spectral Verifier (\bm{\Xi}) and the Holographic Interlock (\bm{\Lambda}). It constructs a transition operator (\bm{T}) for both the randomized and deterministic systems and demonstrates that their eigenvalue spectra are identical (\bm{\text{Spec}(T_M) \equiv \text{Spec}(T_D)}). • To ensure no computational states "leaked" out of the system during the transition, it applies the Bekenstein-Hawking entropy limit, locking the internal bulk computational entropy directly to the surface boundary (\bm{\partial\mathcal{M}}). Because the boundary entropy perfectly balances (\bm{S_{bulk} = S_{\partial}}), the deterministic path is validated as the absolute mathematical ground state of the computation. III. Sealing Mechanics (Package D) Once the deterministic paths are validated, the system must be physically and chronologically protected from external stochastic drift or retrocausal paradoxes. • Package D applies the Causal Seal (\bm{\Omega}). It models the computational circuit timeline by treating execution depth as a strict timelike coordinate (\bm{t}). It projects a physical light-cone (\bm{\mathcal{L}_x}) originating precisely from the input string (\bm{x}). • The Causal Seal acts as a strict projection operator, filtering out and discarding any execution path or state fluctuation that originates outside this causal horizon. By enforcing temporal monotonicity (\bm{\partial_t \Phi_i \ge 0}), it guarantees that the deterministic simulation is entirely non-anticipatory and structurally sealed against unphysical branching. IV. Replication Mechanics (Package E) The final stage bridges the gap between pure mathematical physics and real-world implementation, allowing the global scientific community to verify the proof without architectural bias. Package E constructs the Agnostic Replication Interface (ARI) by creating a quotient Hilbert space (HARI). This space groups all internalhardware variations together, isolating only the invariant boundary signatures. It defines the Agnostic Verification Operator(Y). When any external verification node-whether running on classical silicon, quantum simulators, or optical clusters—queries the boundary density matrices (P), the operatorcomputes a global determinant. If the spectral and causal constraints of Packages A through D are maintained, the system returns an exact, invariant parity scalar: This digital certificate allows peer reviewers to perform a rapid, local polynomial-time check of the boundary states, confirming that the BPP = P reductir * Is true universally and independently of the unserver. --- Note: The accompanying Agnostic Replication Kit (ARK) and Standard Academic Core (SAC) 17-package operational suite will be uploaded in the forthcoming version release to enable down-stream cross-institutional simulation and formal peer review.A Five-Part Validation-Grade Resolution of BPP = P through Ricci Flow, Spectral Equivalence, and Holographic Entropy Bounding This suite presents a complete, five-part validation-grade resolution of the \bm{\text{BPP} = \text{P}} (derandomization) conjecture. Moving beyond traditional, pseudorandom generator (PRG) approximations which suffer from structural verification gaps, this framework translates discrete computational complexity into continuous geometric topology. By embedding the execution trajectories of a bounded-error probabilistic polynomial-time (\bm{\text{BPP}}) machine into a 5-dimensional Lorentzian manifold, computational randomness is mathematically formalized as unmapped curvature and solenoidal noise. Through the systematic application of a dissipative Ricci flow, this noise is annihilated, forcing chaotic state-branching to collapse into a stable, unique deterministic geodesic. The structural integrity of this reduction is validated by proving an exact spectral equivalence between the randomized transition operators and the deterministic execution pathways. Using a holographic interlock, the bulk computational entropy is bounded to a 4-dimensional boundary surface, demonstrating zero loss of algorithmic information. Temporal monotonicity and non-anticipatory information flux are rigorously enforced via a causal seal, restricting all valid computation strictly within the input's light-cone. Finally, an observer-independent Agnostic Replication Interface (ARI) is established, mapping the global boundary states to a universal parity scalar (\bm{\Xi_{obs} = 1}). This five-part suite provides the definitive mathematical infrastructure required for the absolute derandomization of randomized polynomial-time algorithms, rendering the equivalence universally replicable across any computational architecture. Global Architecture: How the 5-Package Suite Resolves, Validates, Seals, and Replicates The resolution operates as a continuous pipeline across five distinct mathematical layers. Rather than treating the packages as isolated proofs, they form a unified, chronological sequence where the outputs of the preceding layer dictate the boundary conditions of the next. [Package A: Initial Manifold] — Dissipates Noise via Ricci Flow [Package B: Topological Lift] → Constrains Paths via Flow Governor [Package C: Spectral Interlock] → Audits Information via Boundary Matching [Package D: Causal Seal] Temporal Monotonicity & Light-Cones > Enforces V [Package E: Agnostic Interface] → Outputs Universal Parity Scalar (E _obs = 1) I. Resolution Mechanics (Packages A & B) The core resolution focuses on eliminating the combinatorial explosion of a randomized algorithm's branching state-space. • Package A initializes a smooth, regular 5D Lorentzian manifold (\bm{\mathcal{M}}) and establishes an epistemic noise floor. It treats probabilistic variance as localized geometric curvature (\bm{R_{\mu\nu}}). By introducing the Harmonic Scrubber (\bm{\Psi_{det}}), it runs a geometric Ricci flow equation (\bm{\frac{\partial}{\partial t}g_{ij} = -2R_{ij}}) that mathematically "smooths out" this curvature, cooling the system into a stable, flat invariant baseline (\bm{\gamma}). • Package B performs a topological lift, mapping the discrete Boolean circuit logic directly onto this smoothed manifold. To prevent the computational pathways from cross-intersecting or splitting into new randomized branches, it deploys the Laminar Flow Governor (\bm{\Gamma}). This enforces a strict solenoidal constraint (\bm{\nabla \cdot \mathbf{v} = 0}), transforming a highly chaotic probabilistic vector field into a collection of laminar, unique, and parallel deterministic geodesics. II. Validation Mechanics (Package C) To prove that the smoothing and flattening performed by the resolution did not alter the fundamental logic or correctness of the underlying algorithm, an exact informational audit is required. • Package C establishes this validation through the Spectral Verifier (\bm{\Xi}) and the Holographic Interlock (\bm{\Lambda}). It constructs a transition operator (\bm{T}) for both the randomized and deterministic systems and demonstrates that their eigenvalue spectra are identical (\bm{\text{Spec}(T_M) \equiv \text{Spec}(T_D)}). • To ensure no computational states "leaked" out of the system during the transition, it applies the Bekenstein-Hawking entropy limit, locking the internal bulk computational entropy directly to the surface boundary (\bm{\partial\mathcal{M}}). Because the boundary entropy perfectly balances (\bm{S_{bulk} = S_{\partial}}), the deterministic path is validated as the absolute mathematical ground state of the computation. III. Sealing Mechanics (Package D) Once the deterministic paths are validated, the system must be physically and chronologically protected from external stochastic drift or retrocausal paradoxes. • Package D applies the Causal Seal (\bm{\Omega}). It models the computational circuit timeline by treating execution depth as a strict timelike coordinate (\bm{t}). It projects a physical light-cone (\bm{\mathcal{L}_x}) originating precisely from the input string (\bm{x}). • The Causal Seal acts as a strict projection operator, filtering out and discarding any execution path or state fluctuation that originates outside this causal horizon. By enforcing temporal monotonicity (\bm{\partial_t \Phi_i \ge 0}), it guarantees that the deterministic simulation is entirely non-anticipatory and structurally sealed against unphysical branching. IV. Replication Mechanics (Package E) The final stage bridges the gap between pure mathematical physics and real-world implementation, allowing the global scientific community to verify the proof without architectural bias. Package E constructs the Agnostic Replication Interface (ARI) by creating a quotient Hilbert space (HARI). This space groups all internalhardware variations together, isolating only the invariant boundary signatures. It defines the Agnostic Verification Operator(Y). When any external verification node-whether running on classical silicon, quantum simulators, or optical clusters—queries the boundary density matrices (P), the operatorcomputes a global determinant. If the spectral and causal constraints of Packages A through D are maintained, the system returns an exact, invariant parity scalar: This digital certificate allows peer reviewers to perform a rapid, local polynomial-time check of the boundary states, confirming that the BPP = P reductir * Is true universally and independently of the unserver. --- Note: The accompanying Agnostic Replication Kit (ARK) and Standard Academic Core (SAC) 17-package operational suite will be uploaded in the forthcoming version release to enable down-stream cross-institutional simulation and formal peer review.

May 22, 20260 citations

Optimal kernel functions for linear combination of Hamiltonian simulation

Harriet Apel, Bjorn K. Berntson

Linear combination of Hamiltonian simulation (LCHS) provides an asymptotically optimal framework for the quantum simulation of linear non-unitary dynamics. The LCHS approach approximately implements the Peano--Baker propagator through an integral representation determined by a kernel function. We establish an LCHS approximation theorem for a broadened class of admissible kernel functions, defined by natural complex-analytic conditions. In the standard time-independent block-encoding access model, we explicitly construct, for each target error $\varepsilon$ , the unique kernel function in this class minimizing the query-cost functional and show that the minimum of this functional has the asymptotic expansion $\tfrac{2\mathrm{e}}π\big(\log\frac{1}{\varepsilon}-\log\log\frac{1}{\varepsilon}+o(1)\big)$ as ${\varepsilon\downarrow0}$ . The provably optimal leading coefficient $2\mathrm{e}/π$ improves by a factor of approximately 2.1 on the coefficient obtained empirically by Low and Somma through numerical minimization over their family of optimally scaling kernel functions. We construct a spectrally convergent quadrature with explicit bounds on operator error and linear combination of unitaries (LCU) subnormalization, proving that this asymptotic improvement persists after discretization into a finite linear combination of unitaries suitable for implementation. Our results are based on Hardy space theory and convex analysis.Linear combination of Hamiltonian simulation (LCHS) provides an asymptotically optimal framework for the quantum simulation of linear non-unitary dynamics. The LCHS approach approximately implements the Peano--Baker propagator through an integral representation determined by a kernel function. We establish an LCHS approximation theorem for a broadened class of admissible kernel functions, defined by natural complex-analytic conditions. In the standard time-independent block-encoding access model, we explicitly construct, for each target error $\varepsilon$, the unique kernel function in this class minimizing the query-cost functional and show that the minimum of this functional has the asymptotic expansion $\tfrac{2\mathrm{e}}π\big(\log\frac{1}{\varepsilon}-\log\log\frac{1}{\varepsilon}+o(1)\big)$ as ${\varepsilon\downarrow0}$. The provably optimal leading coefficient $2\mathrm{e}/π$ improves by a factor of approximately 2.1 on the coefficient obtained empirically by Low and Somma through numerical minimization over their family of optimally scaling kernel functions. We construct a spectrally convergent quadrature with explicit bounds on operator error and linear combination of unitaries (LCU) subnormalization, proving that this asymptotic improvement persists after discretization into a finite linear combination of unitaries suitable for implementation. Our results are based on Hardy space theory and convex analysis.

quant-pharXiv:2610.03669Oct 5, 20260 citations

D

\varepsilon

, the unique kernel function in this class minimizing the query-cost functional and show that the minimum of this functional has the asymptotic expansion

\tfrac{2\mathrm{e}}π\big(\log\frac{1}{\varepsilon}-\log\log\frac{1}{\varepsilon}+o(1)\big)

{\varepsilon\downarrow0}

. The provably optimal leading coefficient

2\mathrm{e}/π

improves by a factor of approximately 2.1 on the coefficient obtained empirically by Low and Somma through numerical minimization over their family of optimally scaling kernel functions. We construct a spectrally convergent quadrature with explicit bounds on operator error and linear combination of unitaries (LCU) subnormalization, proving that this asymptotic improvement persists after discretization into a finite linear combination of unitaries suitable for implementation. Our results are based on Hardy space theory and convex analysis.