Rare-regime discovery in parameterized dynamical systems is an active-search problem: find one verified parameter at which a scientifically defined qualitative threshold is crossed, even when acceptable candidates are rare, nonconvex, or fragmented. We introduce Quantum-Classical Phase-space and Stability-Threshold Search (QC-PHAST), an evidence-gated decision protocol and query-accounting framework for finite candidate libraries. A candidate induces a dynamical object, simulator-derived criticality score, and verified first-hit predicate. Scientific metadata and charged pilot evidence are used to assess whether equation-aware search, scalar-score active search, predicate-only search, or only a query-model comparison is admissible. The quantum row is the inherited Grover/Boyer--Brassard--Hoyer--Tapp (BBHT) unknown-$M$ marked-set query reference; it is not a new quantum-search theorem, materialized circuit, or hardware-speedup claim. The result is a regime map. Direct boundary constructions, geometry controls, online simulator loops, and learned-label accounting further identify when classical structure, false positives, calibration cost, or state preparation erases the query-model margin. QC-PHAST is therefore an auditable protocol for deciding when a finite-pool marked-set reference is informative and when classical or resource-aware search should dominate.
Rare-regime discovery in parameterized dynamical systems is an active-search problem: find one verified parameter at which a scientifically defined qualitative threshold is crossed, even when acceptable candidates are rare, nonconvex, or fragmented. We introduce Quantum-Classical Phase-space and Stability-Threshold Search (QC-PHAST), an evidence-gated decision protocol and query-accounting framework for finite candidate libraries. A candidate induces a dynamical object, simulator-derived criticality score, and verified first-hit predicate. Scientific metadata and charged pilot evidence are used to assess whether equation-aware search, scalar-score active search, predicate-only search, or only a query-model comparison is admissible. The quantum row is the inherited Grover/Boyer--Brassard--Hoyer--Tapp (BBHT) unknown-M marked-set query reference; it is not a new quantum-search theorem, materialized circuit, or hardware-speedup claim. The result is a regime map. Direct boundary constructions, geometry controls, online simulator loops, and learned-label accounting further identify when classical structure, false positives, calibration cost, or state preparation erases the query-model margin. QC-PHAST is therefore an auditable protocol for deciding when a finite-pool marked-set reference is informative and when classical or resource-aware search should dominate.
2M: The Geometry of Quantum Search – N as Minimum Orbit Length and a Structural Unification of BBBV and Classical Simulability Abstract: Document 2M provides a rigorous geometric derivation of quantum search complexity lower bounds within the ONE AXIOM framework. It demonstrates that the Ω(N) quantum query lower bound is not merely a limitation of computational models, but the minimum orbit length required by σ-contractive dynamics in the coherence search space (UM,dα) derived from Axiom M. The paper introduces and proves the Bridge Theorem (BT), which establishes a formal, bidirectional equivalence between the standard oracle query model and the σ-orbit model, preserving complexity across both tracks. By mapping queries to orbit steps, the Ω(N) lower bound is shown to follow from the geometric requirement of traversing a specific coherence angle to reach a target of measure 1/N. Key Contributions: Geometric Lower Bound (T3): A first-principles derivation of the N bound as a traversal fact in a conservative Orbital Coherence Flow (OCF) field. Grover Uniqueness (T4): Formally proves that Grover’s algorithm is the unique Tmin-optimal trajectory within the coherence geometry. BBBV–Schuster Unification (T8): Bridges the 27-year gap between the BBBV theorem (1997) and recent results on the classical simulability of noisy circuits (Schuster et al., 2024). It proves they are two regimes of a single structural condition: the maintenance or destruction of the coherence fixed point M(x∗)=x∗. The 13/64 Threshold (T8-III): Derives the algebraic boundary fF=13/64 (from the ABC 51:13 partition) as a structural upper bound on the ALLOWED region. The ALLOWED/FORBIDDEN dichotomy is proven independently of this value (Proposition CS-impl); the exact numerical identification of fF with the Schuster empirical threshold is an open calibration task. Context: Documents 0M: The M — One Axiom, ABC: Coherence, and 0A: Foundation
Quantum computing has advanced rapidly in recent years and has shown advantages in a variety of domains. In this paper, we investigate its potential for discrete simulation optimization in the fixed-confidence setting, a fundamental problem in the simulation literature. We first introduce a quantum simulation oracle that prepares a coherent superposition over all candidate solutions and provides the foundation for quantum algorithm design. Based on this oracle, we develop the first Grover-search-based quantum algorithm for discrete simulation optimization, called SOGAS. In particular, SOGAS uses a binary-search framework to progressively eliminate suboptimal solutions while carefully controlling the error probability, and eventually identifies a set of near-optimal solutions. We prove that SOGAS returns a near-optimal solution with probability at least the prescribed confidence level and achieves a quadratic speedup in the dependence of query complexity on the number of candidate solutions. Numerical experiments further show that SOGAS substantially outperforms classical benchmarks and provide empirical evidence for quantum advantage in discrete simulation optimization.
Large-scale predicate matching in big data systems—identifying all records that satisfy complex multi-attribute query conditions—represents one of the most computationally intensive tasks in modern data analytics. Classical approaches based on full table scans or index lookups face prohibitive scalability constraints as datasets grow into the petabyte range. Quantum computing, and Grover's search algorithm in particular, offers a theoretically quadratic speedup for unstructured search; however, the efficiency of any quantum search procedure depends critically on an accurate estimate of the number of matching records, known as the query cardinality. Inaccurate cardinality estimates cause the quantum circuit to operate at a suboptimal number of iterations, increasing both failure rates and missed matches. This paper proposes the Cardinality-Aware Quantum Retrieval (CAQR) framework, which integrates quantum amplitude estimation for adaptive cardinality inference with a Bayesian posterior update mechanism that continuously refines the cardinality estimate during query execution. CAQR constructs efficient quantum oracles for conjunctive and disjunctive predicate conditions and dynamically adjusts Grover iteration counts to maintain near-optimal success probabilities throughout the retrieval process. Simulation experiments over synthetic datasets with search spaces ranging from 2¹² to 2²⁴ demonstrate that CAQR reduces the fraction of missed predicate matches from between 6.1% and 14.8% (baseline) to below 0.82% across all tested configurations, while also reducing total oracle calls by approximately 14–17% compared to fixed-cardinality quantum retrieval. The framework is evaluated against classical, naive quantum, and learned-cardinality baselines, and its theoretical time and space complexity are analysed. These results establish CAQR as a competitive and practically relevant approach for quantum-assisted big data query processing.
Progress towards quantum utility in chemistry requires not only algorithmic advances, but also the identification of chemically meaningful problems whose electronic structure fundamentally challenges classical methods. Here, we introduce a curated hierarchy of chemically decisive benchmark systems designed to probe distinct regimes of electronic correlation relevant to molecular, bioinorganic, and heavy-element chemistry. Moving beyond minimal toy models, our benchmark set spans multireference bond breaking (N2), high-spin transition-metal chemistry (FeS), biologically relevant iron-sulfur clusters ([2Fe-2S]), and actinide-actinide bonding (U2), which exhibits extreme sensitivity to active-space choice, relativistic treatment, and correlation hierarchy even within advanced multireference frameworks. As a concrete realization, we benchmark a recently developed automated and adaptive quantum algorithm based on generator-coordinate-inspired subspace expansion,ADAPT-GCIM, using a black-box workflow that integrates entropy-based active-space selection via the ActiveSpaceFinder tool. Across this chemically diverse problem set, ADAPT-GCIM achieves high accuracy in challenging correlation regimes. Equally importantly, these benchmarks expose general failure modes and design constraints-independent of any specific algorithm-highlighting the necessity of problem-aware and correlation-specific strategies for treating strongly correlated chemistry on quantum computers. To support systematic benchmarking and reproducible comparisons, the Hamiltonians for all systems studied are made openly available.
We generalize quantum-classical PCPs, first introduced by Weggemans, Folkertsma and Cade (TQC 2024), to allow for q quantum queries to a polynomially-sized classical proof (QCPCPQ,c,s[q]). Exploiting a connection with the polynomial method, we prove that for any constant q, promise gap c−s=Ω(1/poly(n)) and δ>0, we have QCPCPQ,c,s[q]⊆QCPCP1−δ,1/2+δ[3]⊆BQ⋅NP, where BQ⋅NP is the class of promise problems with quantum reductions to an NP-complete problem. Surprisingly, this shows that we can amplify the promise gap from inverse polynomial to constant for constant query quantum-classical PCPs, and that any quantum-classical PCP making any constant number of quantum queries can be simulated by one that makes only three classical queries. Nevertheless, even though we can achieve promise gap amplification, our result also gives strong evidence that there exists no constant query quantum-classical PCP for QCMA, as it is unlikely that QCMA⊆BQ⋅NP, which we support by giving oracular evidence. In the (poly-)logarithmic query regime, we show for any positive integer c, there exists an oracle relative to which QCPCP[O(logcn)]⊊QCPCPQ[O(logcn)], contrasting the constant query case where the equivalence of both query models holds relative to any oracle. Finally, we connect our results to more general quantum-classical interactive proof systems.
Adiabatic quantum algorithms must evolve slowly enough to suppress non-adiabatic transitions while remaining fast enough to be practical. In open systems, this trade-off is reshaped by decoherence. For Hamiltonians subject to dephasing Lindbladians, Avron et al. [Phys. Rev. A 82, 040304(R) (2010)] showed that a unique timetable exists that maximizes the fidelity with a target state. This optimal schedule is characterized by a constant tunneling rate along the adiabatic path. In this work, we revisit their analysis and apply it to the adiabatic Grover search framework, obtaining closed-form expressions for the optimal evolution schedule, the minimum runtime, and the resulting achievable fidelity. Moreover, by invoking an energy-time uncertainty argument, we identify a critical dephasing threshold beyond which further noise-assisted acceleration is prohibited, showing that the apparent advantage of strong dephasing is a Zeno-type stabilization mechanism rather than a conventional algorithmic speedup over unitary Grover search.