The BBBV lower bound applies only to unitary quantum algorithms. Near an n-th order exceptional point EP_n, a perturbation of strength ε causes eigenvalue splitting Δλ ~ ε^(1/n) rather than the generic Δλ ~ ε. Placing EP_2 at the wrong-answer subspace of a search graph yields distinguishable amplitude after O(N^(1/4)) steps — a quadratic improvement over Grover's O(√N). The non-Hermitian evolution is implemented via Naimark dilation (system doubled to 2n qubits), and the overhead of doubling does not cancel the EP_2 gain: total gate count beats Grover for N > 16. The mechanism is connected to the SNAP opcode of the Origami ISA framework firing at the Maslov-Gibbs snap threshold.
The BBBV lower bound applies only to unitary quantum algorithms. Near an n-th order exceptional point EP_n, a perturbation of strength ε causes eigenvalue splitting Δλ ~ ε^(1/n) rather than the generic Δλ ~ ε. Placing EP_2 at the wrong-answer subspace of a search graph yields distinguishable amplitude after O(N^(1/4)) steps — a quadratic improvement over Grover's O(√N). The non-Hermitian evolution is implemented via Naimark dilation (system doubled to 2n qubits), and the overhead of doubling does not cancel the EP_2 gain: total gate count beats Grover for N > 16. The mechanism is connected to the SNAP opcode of the Origami ISA framework firing at the Maslov-Gibbs snap threshold.
Exceptional points (EPs) — the snap thresholds of the Maslov-Gibbs Einsum free energy — are identified as a universal organising principle across five domains where PT symmetry has not previously been recognised: (i) quantum chemistry, where DFT failure is an EP crossing detected by the Weyl index c₂; (ii) quantum error correction, where canonical code distances correspond to EP orders and EP₂ search beats Grover for N > 16; (iii) ranking algorithms, where RavenRank is PT-symmetric ranking near the EP of the comparison Laplacian; (iv) enzyme catalysis and biological self-organisation, where k_cat operates at the Curzon-Ahlborn EP of the kinetic Lindbladian; and (v) information geometry, where the Fisher metric degenerates at EP₂ and the Cramér-Rao bound saturates there. The 38-fold way classifies all PT-symmetric phases of matter.
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
In this paper, we study decoherence in Grover's quantum searching algorithm using a perturbative method. We assume that each two-state system (qubit) suffers ${\ensuremath{\sigma}}_{z}$ error with probability p(0<p<1) independently at every step in the algorithm. Considering an n-qubit density operator to which Grover's operation is applied M times, we expand it in powers of 2Mnp and derive its matrix element order by order under the $\stackrel{\ensuremath{\rightarrow}}{n}\ensuremath{\infty}$ limit. (In this large-n limit, we assume p is small enough, so that 2Mnp(>0) can take any real positive value or 0.) This approach gives us an interpretation about creation of new modes caused by ${\ensuremath{\sigma}}_{z}$ error and an asymptotic form of an arbitrary-order correction. Calculating the matrix element up to the fifth-order term numerically, we investigate a region of 2Mnp (perturbative parameter), where the algorithm finds the correct item with a threshold of probability Pth or more. It satisfies $2Mnp<(8/5)(1\ensuremath{-}{P}_{\mathrm{th}})$ around $2Mnp\ensuremath{\simeq}0$ and ${P}_{\mathrm{th}}\ensuremath{\simeq}1,$ and this linear relation is applied to a wide range of Pth approximately. This observation is similar to a result obtained by Bernstein and Vazirani concerning accuracy of quantum gates for general algorithms. We cannot investigate a quantum-to-classical phase transition of the algorithm, because it is outside the reliable domain of our perturbation theory.
Fixed-point quantum search algorithms succeed at finding one of M target items among N total items even when the run time of the algorithm is longer than necessary. While the famous Grover's algorithm can search quadratically faster than a classical computer, it lacks the fixed-point property---the fraction of target items must be known precisely to know when to terminate the algorithm. Recently, Yoder, Low, and Chuang [Phys. Rev. Lett. 113, 210501 (2014)] gave an optimal gate-model search algorithm with the fixed-point property. Previously, it had been discovered by Roland and Cerf [Phys. Rev. A 65, 042308 (2002)] that an adiabatic quantum algorithm, operating by continuously varying a Hamiltonian, can reproduce the quadratic speedup of gate-model Grover search. We ask, can an adiabatic algorithm also reproduce the fixed-point property? We show that the answer depends on what interpolation schedule is used, so as in the gate model, there are both fixed-point and non-fixed-point versions of adiabatic search, only some of which attain the quadratic quantum speedup. Guided by geometric intuition on the Bloch sphere, we rigorously justify our claims with an explicit upper bound on the error in the adiabatic approximation. We also show that the fixed-point adiabatic search algorithm can be simulated in the gate model with neither loss of the quadratic Grover speedup nor of the fixed-point property. Finally, we discuss natural uses of fixed-point algorithms such as preparation of a relatively prime state and oblivious amplitude amplification.
In this paper, we study decoherence in Grover's quantum search algorithm using a perturbative method. We assume that each two-state system (qubit) that belongs to a register suffers a phase-flip error (${\ensuremath{\sigma}}_{z}$ error) with probability p independently at every step in the algorithm, where $0\ensuremath{\leqslant}p\ensuremath{\leqslant}1$. Considering an n-qubit density operator to which Grover's iterative operation is applied M times, we expand it in powers of 2Mnp and derive its matrix element order by order under the large-n limit. [In this large-n limit, we assume p is small enough, so that 2Mnp can take any real positive value or zero. We regard $x\ensuremath{\equiv}2Mnp$ $(\ensuremath{\geqslant}0)$ as a perturbative parameter.] We obtain recurrence relations between terms in the perturbative expansion. By these relations, we compute higher orders of the perturbation efficiently, so that we extend the range of the perturbative parameter that provides a reliable analysis. Calculating the matrix element numerically by this method, we derive the maximum value of the perturbative parameter x at which the algorithm finds a correct item with a given threshold of probability Pth or more. (We refer to this maximum value of x as xc, a critical point of x.) We obtain a curve of xc as a function of Pth by repeating this numerical calculation for many points of Pth and find the following facts: a tangent of the obtained curve at Pth=1 is given by $x=(8∕5)(1\ensuremath{-}{P}_{\mathrm{th}})$, and we have ${x}_{\mathrm{c}}>\ensuremath{-}(8∕5){\mathrm{log}}_{e}\phantom{\rule{0.2em}{0ex}}{P}_{\mathrm{th}}$ near Pth=0.
Higher-order exceptional points (EPs) in non-Hermitian systems have attracted great interest due to their advantages in sensitive enhancement and distinct topological features. However, realization of such EPs is still a challenge because more fine-tuning parameters are generically required in quantum systems, compared to the second-order EP (EP2). Here, we propose a non-Hermitian three-mode optomechanical system in the blue-sideband regime for predicting the third-order EP (EP3). By deriving the pseudo-Hermitian condition for the proposed system, one cavity with loss and the other with gain must be required. Then we show that EP3 or EP2 can be observed when the mechanical resonator (MR) is neutral, loss, or gain. For the neutral MR, we find that two degenerate or two nondegenerate EP3s can be predicted by tuning system parameters in the parameter space, while four nondegenerate EP2s can be observed when the system parameters deviate from EP3s, which is distinguished from the previous study in the red-detuned optomechanical system. For the gain (loss) MR, we find that only two degenerate EP3s or EP2s can be predicted by tuning enhanced coupling strength. Our proposal provides a potential way to predict higher-order EPs or multiple EP2s and study multimode quantum squeezing around EPs using blue-detuned non-Hermitian optomechanical systems.