diff 383c171..34246b0 qma_coulomb_hardness_v2.txt
diff --git a/qma_coulomb_hardness_v2.txt b/qma_coulomb_hardness_v2.txt
index ec42008..118471a 100644
--- a/qma_coulomb_hardness_v2.txt
+++ b/qma_coulomb_hardness_v2.txt
@@ -1,171 +1,78 @@
-Conventions. Atomic units throughout. |A| is the volume of A. p(n,D) is some polynomial in the named variables with absolute constants; it can be enlarged from line to line. E(H) is the bottom of the spectrum of H.
+Conventions. Atomic units. |A| is the volume of A. p(n,D) is any polynomial in its arguments, enlarged as needed. E(H) is the bottom of the spectrum.
-A single electron near a proton has a lowest energy; any fixed nuclear configuration gives one real number whose exact computation is hard, and even its threshold decision is extraordinarily hard.
+A single electron near a proton has a lowest energy; any fixed nuclear configuration yields one real number, extraordinarily hard to compute and equally hard to threshold.
QMA is the class of decision problems whose YES instances admit a polynomial-size quantum proof. It contains NP; no efficient algorithm is known for QMA-hard problems.
-Aharonov-Naveh 2002, arXiv:quant-ph/0210077. Kitaev-Shen-Vyalyi 2002, AMS Grad Studies 47.
-
-Feynman (1982) and Lloyd (1996) framed physical simulation as a natural quantum-computational task; QMA-hardness is the case where even this remains intractable.
-
-Feynman, R. P., "Simulating physics with computers", Int. J. Theor. Phys.
-21 (1982), 467-488. https://doi.org/10.1007/BF02650179
-
-Lloyd, S., "Universal quantum simulators", Science 273 (1996), 1073-1078.
-https://doi.org/10.1126/science.273.5278.1073
-
-The problem decided. Given N electrons interacting with M nuclei of charge
-exactly one, positioned at pairwise distinct rational triples, and given
-two rational thresholds a < b with b - a >= 1/L where L is the input
-length, decide whether the electronic ground energy E_0 lies in
-(-inf, a] or in [b, inf). The promise excludes energies strictly between
-a and b. Deciding this is QMA-hard under deterministic classical
-polynomial-time many-one reductions. The reduction produces polynomially
-many nuclei and electrons, rational positions and thresholds whose bit
-lengths are polynomial in the source length, and a threshold separation
-b - a >= 1.
-
-What makes the statement sharp. The nuclei are genuine point charges of
-charge one, not an invented potential with wells and oscillators built
-in. The minimization is over every continuum many-electron state of
-either spin, not over a supplied finite basis. No magnetic field, extra
-external potential, neutrality, binding, existence of a ground
-eigenvector, or excitation-gap assumption is imposed. Membership in QMA
-is not asserted.
-
-Schuch and Verstraete (2009) proved QMA-completeness for the Hubbard model
-with local magnetic fields and outlined a continuum realization using
-designed scalar and spin-dependent potentials. O'Gorman, Irani, Whitfield,
-and Fefferman (2022) proved QMA-completeness for electronic structure in a
-supplied finite orbital basis, which fixes the Hilbert space in advance.
-Cubitt, Montanaro, and Piddock (2019) proved QMA-hardness of the signed
-exchange problem on finite square-lattice graphs, which provides the
-starting point. Each relaxation is removed at once: the free continuum,
-with real unit point nuclei, reached from the same signed-exchange source.
-
-Schuch, N. and Verstraete, F., "Computational complexity of interacting
-electrons and fundamental limitations of density functional theory",
-Nature Physics 5 (2009), 732-735. arXiv:0712.0483.
-local: 0712.0483.pdf
-
-O'Gorman, B., Irani, S., Whitfield, J., and Fefferman, B., "Intractability
-of electronic structure in a fixed basis", PRX Quantum 3 (2022), 020322.
-doi:10.1103/PRXQuantum.3.020322.
-
-Cubitt, T., Montanaro, A., and Piddock, S., "Universal quantum Hamiltonians",
-pnas 115 (2018), 9497-9502. arXiv:1701.05182v4.
-local: 1701.05182v4.pdf
-
-Electrons in R^3. Each electron also has a spin, which is a direction in a
-two-dimensional complex space C^2. So one electron lives in L^2(R^3) tensor
-c^2. n electrons live in the N-fold antisymmetric tensor power
+Aharonov-Naveh 2002, arXiv:quant-ph/0210077. Kitaev-Shen-Vyalyi 2002, AMS GTM 47.
- H_N = Lambda^N ( L^2(R^3) tensor C^2 ).
+Feynman (1982) and Lloyd (1996) framed physical simulation as a natural quantum-computational task; QMA-hardness is that task's intractable limit.
-"Antisymmetric" means two electrons may not occupy the same (position,spin)
-state: the wavefunction changes sign when you swap two electrons. Position
-and spin are swapped together, not separately. No spin sector is fixed.
+Feynman, R. P., "Simulating physics with computers", Int. J. Theor. Phys. 21 (1982), 467-488. Lloyd, S., "Universal quantum simulators", Science 273 (1996), 1073-1078.
-For M nuclei at positions R_1,...,R_M with charges Z_alpha (here all equal
-to 1) the electronic Hamiltonian in atomic units is
+The problem: given N electrons and M charge-one nuclei at distinct rational triples, and rational thresholds a < b with b - a >= 1/L, decide whether E_0 lies in (-inf, a] or in [b, inf). This is QMA-hard under deterministic classical polynomial-time many-one reductions, producing polynomially many nuclei and electrons, polynomial-length rational thresholds, and b - a >= 1.
- H = -1/2 sum_{i=1}^N Delta_{x_i}
- - sum_{i=1}^N sum_{alpha=1}^M 1/|x_i - R_alpha|
- + sum_{1<=i<j<=N} 1/|x_i - x_j| . (1)
+What makes the statement sharp: nuclei are genuine point charges of charge one, not a designed potential; minimization is over every continuum many-electron state of either spin, not a supplied finite basis.
-The three pieces are: electron kinetic energy; electron-nucleus attraction;
-electron-electron repulsion. The nuclear repulsion sum_{alpha<beta}
-Z_alpha Z_beta/|R_alpha-R_beta| is a fixed number once the nuclei are fixed,
-so it is omitted. The energy in (1) is the electronic energy. This is
-the convention used everywhere below.
+Schuch-Verstraete (2009) proved QMA-completeness for a Hubbard model with local magnetic fields and gave a continuum realization via designed scalar and spin-dependent potentials. O'Gorman, Irani, Whitfield, Fefferman (2022) proved QMA-completeness for electronic structure in a supplied finite orbital basis, which fixes the Hilbert space in advance. Cubitt, Montanaro, Piddock (2019) proved QMA-hardness of the signed exchange problem on finite square-lattice graphs, providing the starting point. Each relaxation is removed at once, giving the free continuum with real unit point nuclei from the same signed-exchange source.
-The natural space of states is the H^1 form domain
+Schuch, N. and Verstraete, F., "Computational complexity of interacting electrons and fundamental limitations of density functional theory", Nature Physics 5 (2009), 732-735. local: 0712.0483.pdf
- Q_N = H^1(R^{3N};(C^2)^{tensor N}) intersect H_N .
+O'Gorman, B., Irani, S., Whitfield, J., and Fefferman, B., "Intractability of electronic structure in a fixed basis", PRX Quantum 3 (2022), 020322.
-H is unbounded below on all of L^2 if this is careless, but on Q_N it is
-bounded below and has a well-defined self-adjoint realization obtained from
-the closed Coulomb quadratic form. Write
+Cubitt, T., Montanaro, A., and Piddock, S., "Universal quantum Hamiltonians", PNAS 115 (2018), 9497-9502. local: 1701.05182v4.pdf
- E_0 = inf spec H = inf{ <psi,H psi> : psi in Q_N, ||psi|| = 1 },
+Electrons in R^3. Each carries a spin in C^2, so one electron lives in L^2(R^3) tensor C^2 and N electrons live in the N-fold antisymmetric tensor power
+
+ H_N = Lambda^N ( L^2(R^3) tensor C^2 ).
-whether or not the infimum is attained by an actual eigenvector. This
-"form" viewpoint is exactly what is needed later: energies are compared
-by testing the quadratic form on arbitrary trial states, never assuming
-that a ground eigenvector exists.
+"Antisymmetric" means two electrons may not share the same (position,spin) state: the wavefunction flips sign when two are swapped (position and spin together). No spin sector is fixed.
-Teschl, G., "Mathematical Methods in Quantum Mechanics with Applications
-to Schrodinger Operators", Graduate Studies in Mathematics 99, AMS, 2009.
-https://www.mat.univie.ac.at/~gerald/ftp/book-schroe/
+For M nuclei at positions R_1,...,R_M with all charges Z_alpha = 1, the electronic Hamiltonian in atomic units is
-Reed, M. and Simon, B., "Methods of Modern Mathematical Physics, Vol. II:
-Fourier Analysis, Self-Adjointness", Academic Press, 1975.
-ISBN: 978-0125850025.
+ H = -1/2 sum_{i=1}^N Delta_{x_i}
+ - sum_{i=1}^N sum_{alpha=1}^M 1/|x_i - R_alpha|
+ + sum_{1<=i<j<=N} 1/|x_i - x_j| . (1)
-A "promise problem" is a decision question that is only asked on inputs
-obeying some rule (the promise). The inputs are described exactly here.
+The three terms are electron kinetic energy, electron-nucleus attraction, and electron-electron repulsion. Nuclear repulsion is constant for fixed nuclei and is omitted; (1) is the electronic energy.
- Input
- M >= 1 nuclear positions R_1,...,R_M in Q^3, pairwise distinct.
- All charges Z_alpha = 1.
- N >= 1 electrons, written in unary (N ones, so a large N costs length N).
- Two rational numbers a < b, the thresholds.
+The natural space of states is the H^1 form domain
- encoding
- Each rational is a signed binary numerator over a positive binary
- denominator, in lowest terms, inside a fixed self-delimiting encoding.
+ Q_N = H^1(R^{3N};(C^2)^{tensor N}) intersect H_N .
- length L
- Total bit length of all the above (the unary count contributes N).
+On Q_N the operator is bounded below, self-adjoint via the closed Coulomb quadratic form. Write
- Promise
- b - a >= 1/L.
+ E_0 = inf spec H = inf{ <psi,H psi> : psi in Q_N, ||psi|| = 1 },
- Answer
- YES if E_0 <= a. NO if E_0 >= b.
- (The promise b-a >= 1/L makes the two cases disjoint.)
+whether or not attained. Energies are compared by testing this form on arbitrary trial states, never assuming an eigenvector exists.
-The promise b - a >= 1/L concerns decision precision, not a molecular spectral gap; the theorem assumes no excitation gap, binding, neutrality, or existence of a ground eigenvector.
+Teschl, G., "Mathematical Methods in Quantum Mechanics with Applications to Schrodinger Operators", Graduate Studies in Mathematics 99, AMS, 2009.
-Energy convention: electronic energy; nuclear repulsion omitted.
+Reed, M. and Simon, B., "Methods of Modern Mathematical Physics, Vol. II: Fourier Analysis, Self-Adjointness", Academic Press, 1975.
-Main theorem. The promise problem is QMA-hard under deterministic classical polynomial-time many-one reductions, with output consisting of polynomially many unit-charge rational nuclei at distinct positions, polynomially many unary electrons, and polynomial-length rational thresholds at separation b - a >= 1. Thus Z_max = 1 and c = 1; membership in QMA is not asserted; and neither b - a >= 1 nor the input gap 1/L constrains the molecular excitation gap. Each stage preserves the promise because every energy error is inverse-polynomially small relative to gamma, and gamma itself is inverse-polynomial in source length.
+ Input. M >= 1 distinct rational nuclear positions in Q^3, all charges one; N >= 1 electrons in unary; rational thresholds a < b.
+ Encoding. Rationals are signed binary numerator over positive denominator in lowest terms, fixed self-delimiting.
+ Length L. Total bit length of the above (unary N gives N).
+ Promise. b - a >= 1/L.
+ Answer. YES if E_0 <= a, NO if E_0 >= b; the promise makes the cases disjoint.
-The proof starts from a QMA-hard problem about spins.
+Main theorem. The promise problem is QMA-hard. Each stage preserves the source promise, since its energy error is inverse-polynomially small relative to gamma (itself inverse-polynomial in source length). Charge bound Z_max = 1, precision c = 1; neither output gap b - a >= 1 nor input gap 1/L constrains molecular excitation; membership in QMA is not asserted.
-The spin source (Cubitt-Montanaro-Piddock, 2018/2019).
- Consider a finite square-lattice graph (vertices are cells of Z^2, edges
- join cells at distance 1), possibly with some signed real couplings J_e.
- The Hamiltonian is
+Cubitt-Montanaro-Piddock (2018/2019) source: a finite square-lattice graph (vertices are cells of Z^2, edges join cells at distance 1) with signed real couplings J_e. The Hamiltonian is
- H_in = sum_e J_e h^s_{LR}, h^s_{LR} = sigma_L . sigma_R, (2)
+ H_in = sum_e J_e h^s_{LR}, h^s_{LR} = sigma_L . sigma_R, (2)
- where sigma = (sigma_x,sigma_y,sigma_z) are the Pauli matrices acting on
- a spin-1/2 at each site, and sigma_L . sigma_R means
- sigma_x_L sigma_x_R + sigma_y_L sigma_y_R + sigma_z_L sigma_z_R. There
- are no one-site terms.
+where sigma = (sigma_x,sigma_y,sigma_z) is the Pauli vector on a spin-1/2 site and sigma_L . sigma_R = sigma_x_L sigma_x_R + sigma_y_L sigma_y_R + sigma_z_L sigma_z_R. There are no one-site terms.
-The cited result supplies three facts, not re-proved here: deciding the ground-energy threshold of (2) is QMA-hard with inverse-polynomial promise gap; the lattice has polynomially many vertices and edges and polynomially bounded couplings; and the couplings are real with polynomially many nonzero entries. The incoming instance is only reshaped to a clean rational format.
+The cited result gives: deciding the ground-energy threshold of (2) is QMA-hard with inverse-polynomial promise gap; polynomially many vertices, edges, and nonzero bounded real couplings.
-Identity of h^s. On two spins, h^s = sigma . sigma = 2 SWAP - I, where
-swap exchanges the two spins. Its eigenvalues are
- +1 on the three triplet states (total spin 1),
- -3 on the singlet state (total spin 0).
-So h^s favors singlets when positive, triplets when negative.
+Identity of h^s. On two spins, h^s = 2 SWAP - I, where SWAP exchanges the two spins; eigenvalues +1 on the triplet (total spin 1) and -3 on the singlet (total spin 0). So h^s favors singlets when positive, triplets when negative.
Normalizing the source to rationals.
-Step 1: a rational lower bound on the gap. Because the source gap is
-inverse polynomial in the input size, there is a rational delta > 0, known
-in advance and inverse polynomial, with delta <= (source gap).
+Step 1: a rational lower bound on the gap. Since the source gap is inverse-polynomial in input size, a known inverse-polynomial rational delta > 0 satisfies delta <= (source gap).
-Step 2: rational couplings and thresholds. Let q be the number of
-weighted edges. Set eps_0 = delta/100. Round each coupling J_e to a
-rational within eps_0/max(1,q). The total change in Hamiltonian norm
-(supremum over unit vectors of |change|) is at most q * (3 * eps_0/max(1,q))
-= 3 eps_0, since |h^s_{LR}| has operator norm 3. Write the incoming
-instance's scalar as c_0 I (c_0 = 0 if there is none) and its thresholds
-as a_0 < b_0. Round c_0, a_0, b_0 within eps_0 to rationals c~, a~, b~.
+Step 2: rational couplings and thresholds. Let q be the number of weighted edges. Set eps_0 = delta/100. Round each coupling J_e to a rational within eps_0/max(1,q), changing the operator norm by at most q * 3 * eps_0/max(1,q) = 3 eps_0 (since |h^s_{LR}| has operator norm 3). Write the scalar as c_0 I and thresholds a_0 < b_0; round c_0, a_0, b_0 within eps_0 to rationals c~, a~, b~.
The rounded Hamiltonian H~_in = sum J~_e h^s_{LR} obeys
@@ -175,44 +82,24 @@ Define rational thresholds
a_s = a~ - c~ + 5 eps_0 , b_s = b~ - c~ - 5 eps_0 . (4)
-Then YES/NO of the source stays intact: the 5-eps_0 shifts absorb the
-3 eps_0 of Hamiltonian rounding plus eps_0 each for the scalar and the
-threshold. And
+Then YES/NO stays intact: 5-eps_0 shifts absorb 3-eps_0 rounding plus eps_0 for the scalar and eps_0 for the threshold. And
b_s - a_s >= (b_0 - a_0) - 2 eps_0 - 10 eps_0 >= delta - 12 eps_0
= 0.88 delta > 0 . (5)
-Step 3: geometric extent. A connected component of the square grid with V
-vertices has coordinate diameter at most V-1 (walk along lattice edges).
-Translating components into disjoint horizontal strips leaves all weighted
-graphs unchanged and keeps the total coordinate range polynomial. So the
-normalized instance lives in a polynomial-size bounding box.
+Step 3: geometric extent. A connected component of the square grid with V vertices has coordinate diameter at most V-1 (walk along lattice edges). Translating components into disjoint horizontal strips keeps all weighted graphs unchanged and the coordinate range polynomial; the normalized instance lives in a polynomial-size box.
Finally set
n = max(2, source input size), gamma = min(1, b_s - a_s). (6)
-From now on, "the source instance" means the rational signed Heisenberg
-Hamiltonian H_in with thresholds a_s < b_s and gap gamma. One may assume
-there is at least one vertex (add a free spin if the source is empty) and
-one may drop couplings of zero. All magnitudes and inverse gaps
-encountered later are polynomially bounded in n.
-
-The source couplings J_e can be positive or negative. The orbital
-construction naturally produces positive exchange (the electron kinetic
-energy prefers singlets). So first convert the signed
-source into a positive-exchange spin model. The tool is a "singlet-pair
-mediator": a fresh pair of spins forced into a singlet, with weak links to
-the original spins. Its effective coupling to the two ends has the sign one chooses.
-
-This is the mechanism of Piddock and Montanaro Lemma 5. The needed rule: eliminate excited states and keep second order. The quantitative statement, with fewer hypotheses than the usual Schrieffer-Wolff theorem and no requirement that the first-order block pbp vanish, follows.
-
-Schrieffer, J. R. and Wolff, P. A., "Relation between the Anderson and
-Kondo Hamiltonians", Phys. Rev. 149 (1966), 491-492.
-https://doi.org/10.1103/PhysRev.149.491
-Bravyi, S., DiVincenzo, D. P., and Loss, D., "Schrieffer-Wolff
-transformation for many-body systems", Ann. Physics 326 (2011),
-2793-2823. arXiv:1105.0675.
-local: 1105.0675.pdf
+Henceforth "the source instance" means the rational signed Heisenberg Hamiltonian H_in with thresholds a_s < b_s and gap gamma; a free spin covers the empty case, zero couplings drop, and all magnitudes and inverse gaps are polynomially bounded in n.
+
+Couplings J_e can be positive or negative; the orbital construction yields only positive exchange (kinetic energy prefers singlets). So convert the signed source to a positive-exchange spin model using a "singlet-pair mediator" - a fresh spin pair forced into a singlet and weakly linked to the original spins - whose effective coupling to the two ends has either sign.
+
+The mechanism is Piddock-Montanaro Lemma 5: eliminate excited states, keep second order. A quantitative form with fewer hypotheses than the standard Schrieffer-Wolff theorem (no first-order-block vanishing required) follows.
+
+Schrieffer, J. R. and Wolff, P. A., "Relation between the Anderson and Kondo Hamiltonians", Phys. Rev. 149 (1966), 491-492.
+Bravyi, S., DiVincenzo, D. P., and Loss, D., "Schrieffer-Wolff transformation for many-body systems", Ann. Physics 326 (2011), 2793-2823. local: 1105.0675.pdf
Lemma 1 (second-order bottom energy).
Let A and B be self-adjoint operators on a finite-dimensional Hilbert
@@ -1479,7 +1366,7 @@ errors costs a polynomial factor over the entire fermion space.
Identifying the retained operator. In this representation, the retained
two-body term is
- (U/2) sum_i n_i (n_i - 1) + sum_{i<j} v_{ij} n_i n_j ,
+ (U/2) sum_i n_i (n_i - 1) + sum_{i<j} v_{ij} n_i n_j , (79)
and the retained one-body diagonal is