More Like this

1. Improved Merlin–Arthur Protocols for Central Problems in Fine-Grained Complexity

   https://doi.org/10.1007/s00453-023-01102-6  

   Akmal, Shyan; Chen, Lijie; Jin, Ce; Raj, Malvika; Williams, Ryan (February 2023, Algorithmica)

   Abstract In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include:Certifying that a list ofnintegers has no 3-SUM solution can be done in Merlin–Arthur time$$\tilde{O}(n)$$ $\tilde{O}\left(n\right)$. Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in$$\tilde{O}(n^{1.5})$$ $\tilde{O}\left(n^{1.5}\right)$time (that is, there is a proof system with proofs of length$$\tilde{O}(n^{1.5})$$ $\tilde{O}\left(n^{1.5}\right)$and a deterministic verifier running in$$\tilde{O}(n^{1.5})$$ $\tilde{O}\left(n^{1.5}\right)$time).Counting the number ofk-cliques with total edge weight equal to zero in ann-node graph can be done in Merlin–Arthur time$${\tilde{O}}(n^{\lceil k/2\rceil })$$ $\tilde{O}\left(n^{\lceil k/2\rceil }\right)$(where$$k\ge 3$$ $k\ge 3$). For oddk, this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm-edge graph can be done in Merlin–Arthur time$${\tilde{O}}(m)$$ $\tilde{O}\left(m\right)$. Previous Merlin–Arthur protocols by Williams [CCC’16] and Björklund and Kaski [PODC’16] could only countk-cliques in unweighted graphs, and had worse running times for smallk.Computing the All-Pairs Shortest Distances matrix for ann-node graph can be done in Merlin–Arthur time$$\tilde{O}(n^2)$$ $\tilde{O}\left(n^2\right)$. Note this is optimal, as the matrix can have$$\Omega (n^2)$$ $\Omega \left(n^2\right)$nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an$$\tilde{O}(n^{2.94})$$ $\tilde{O}\left(n^{2.94}\right)$nondeterministic time algorithm.Certifying that ann-variablek-CNF is unsatisfiable can be done in Merlin–Arthur time$$2^{n/2 - n/O(k)}$$ $2^{n/2-n/O\left(k\right)}$. We also observe an algebrization barrier for the previous$$2^{n/2}\cdot \textrm{poly}(n)$$ $2^{n/2}·\text{poly}\left(n\right)$-time Merlin–Arthur protocol of R. Williams [CCC’16] for$$\#$$ $\#$SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol fork-UNSAT running in$$2^{n/2}/n^{\omega (1)}$$ $2^{n/2}/n^{\omega \left(1\right)}$time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol.Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time$$2^{4n/5}\cdot \textrm{poly}(n)$$ $2^{4n/5}·\text{poly}\left(n\right)$. Previously, the only nontrivial result known along these lines was an Arthur–Merlin–Arthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running in$$2^{2n/3}\cdot \textrm{poly}(n)$$ $2^{2n/3}·\text{poly}\left(n\right)$time.Due to the centrality of these problems in fine-grained complexity, our results have consequences for many other problems of interest. For example, our work implies that certifying there is no Subset Sum solution tonintegers can be done in Merlin–Arthur time$$2^{n/3}\cdot \textrm{poly}(n)$$ $2^{n/3}·\text{poly}\left(n\right)$, improving on the previous best protocol by Nederlof [IPL 2017] which took$$2^{0.49991n}\cdot \textrm{poly}(n)$$ $2^{0.49991n}·\text{poly}\left(n\right)$time. 

   more » « less
2. A case study of SMEFT $$ \mathcal{O}\left(1/{\Lambda}^4\right) $$ effects in diboson processes: pp → W±(ℓ±ν)γ

   https://doi.org/10.1007/JHEP05(2024)223  

   Martin, Adam (May 2024, Journal of High Energy Physics)

   A<sc>bstract</sc> In this paper we explorepp→W^±(ℓ^±ν)γto$$ \mathcal{O}\left(1/{\Lambda}^4\right) $$ $O\left(1/{\Lambda }^4\right)$in the SMEFT expansion. Calculations to this order are necessary to properly capture SMEFT contributions that grow with energy, as the interference between energy-enhanced SMEFT effects at$$ \mathcal{O}\left(1/{\Lambda}^2\right) $$ $O\left(1/{\Lambda }^2\right)$and the Standard Model is suppressed. We find that there are several dimension eight operators that interfere with the Standard Model and lead to the same energy growth, ~$$ \mathcal{O}\left({E}^4/{\Lambda}^4\right) $$ $O\left(E^4/{\Lambda }^4\right)$, as dimension six squared. While energy-enhanced SMEFT contributions are a main focus, our calculation includes the complete set of$$ \mathcal{O}\left(1/{\Lambda}^4\right) $$ $O\left(1/{\Lambda }^4\right)$SMEFT effects consistent with U(3)⁵flavor symmetry. Additionally, we include the decay of theW^±→ ℓ^±ν, making the calculation actually$$ \overline{q}{q}^{\prime}\to {\ell}^{\pm}\nu \gamma $$ $\overline{q}{q}^{\prime }\to {\ell }^{\pm }\mathrm{\nu \gamma }$. As such, we are able to study the impact of non-resonant SMEFT operators, such as$$ \left({L}^{\dagger }{\overline{\sigma}}^{\mu }{\tau}^IL\right)\left({Q}^{\dagger }{\overline{\sigma}}^{\nu }{\tau}^IQ\right) $$ $\left(L^{†}{\overline{\sigma }}^{\mu }{\tau }^{I}L\right)\left(Q^{†}{\overline{\sigma }}^{\nu }{\tau }^{I}Q\right)$B_μν, which contribute to$$ \overline{q}{q}^{\prime}\to {\ell}^{\pm}\nu \gamma $$ $\overline{q}{q}^{\prime }\to {\ell }^{\pm }\mathrm{\nu \gamma }$directly and not to$$ \overline{q}{q}^{\prime}\to {W}^{\pm}\gamma $$ $\overline{q}{q}^{\prime }\to W^{\pm }\gamma$. We show several distributions to illustrate the shape differences of the different contributions. 

   more » « less
3. Low rank representations for quantum simulation of electronic structure

   https://doi.org/10.1038/s41534-021-00416-z  

   Motta, Mario; Ye, Erika; McClean, Jarrod R.; Li, Zhendong; Minnich, Austin J.; Babbush, Ryan; Chan, Garnet Kin-Lic (May 2021, npj Quantum Information)

   Abstract The quantum simulation of quantum chemistry is a promising application of quantum computers. However, forNmolecular orbitals, the$${\mathcal{O}}({N}^{4})$$ $O\left(N^4\right)$gate complexity of performing Hamiltonian and unitary Coupled Cluster Trotter steps makes simulation based on such primitives challenging. We substantially reduce the gate complexity of such primitives through a two-step low-rank factorization of the Hamiltonian and cluster operator, accompanied by truncation of small terms. Using truncations that incur errors below chemical accuracy allow one to perform Trotter steps of the arbitrary basis electronic structure Hamiltonian with$${\mathcal{O}}({N}^{3})$$ $O\left(N^3\right)$gate complexity in small simulations, which reduces to$${\mathcal{O}}({N}^{2})$$ $O\left(N^2\right)$gate complexity in the asymptotic regime; and unitary Coupled Cluster Trotter steps with$${\mathcal{O}}({N}^{3})$$ $O\left(N^3\right)$gate complexity as a function of increasing basis size for a given molecule. In the case of the Hamiltonian Trotter step, these circuits have$${\mathcal{O}}({N}^{2})$$ $O\left(N^2\right)$depth on a linearly connected array, an improvement over the$${\mathcal{O}}({N}^{3})$$ $O\left(N^3\right)$scaling assuming no truncation. As a practical example, we show that a chemically accurate Hamiltonian Trotter step for a 50 qubit molecular simulation can be carried out in the molecular orbital basis with as few as 4000 layers of parallel nearest-neighbor two-qubit gates, consisting of fewer than 10⁵non-Clifford rotations. We also apply our algorithm to iron–sulfur clusters relevant for elucidating the mode of action of metalloenzymes. 

   more » « less
4. An algorithm and computation to verify Legendre’s conjecture up to $$7\cdot 10^{13}$$

   https://doi.org/10.1007/s40993-024-00589-4  

   Sorenson, Jonathan; Webster, Jonathan (March 2025, Research in Number Theory)

   Abstract We state a general purpose algorithm for quickly finding primes in evenly divided sub-intervals. Legendre’s conjecture claims that for every positive integern, there exists a prime between$$n^2$$ $n^2$and$$(n+1)^2$$ ${(n+1)}^2$. Oppermann’s conjecture subsumes Legendre’s conjecture by claiming there are primes between$$n^2$$ $n^2$and$$n(n+1)$$ $n(n+1)$and also between$$n(n+1)$$ $n(n+1)$and$$(n+1)^2$$ ${(n+1)}^2$. Using Cramér’s conjecture as the basis for a heuristic run-time analysis, we show that our algorithm can verify Oppermann’s conjecture, and hence also Legendre’s conjecture, for all$$n\le N$$ $n\le N$in time$$O( N \log N \log \log N)$$ $O(NlogNloglogN)$and space$$N^{O(1/\log \log N)}$$ $N^{O(1/loglogN)}$. We implemented a parallel version of our algorithm and improved the empirical verification of Oppermann’s conjecture from the previous$$N = 2\cdot 10^{9}$$ $N=2·{10}^9$up to$$N = 7.05\cdot 10^{13} > 2^{46}$$ $N=7.05·{10}^{13}>2^{46}$, so we were finding 27 digit primes. The computation ran for about half a year on each of two platforms: four Intel Xeon Phi 7210 processors using a total of 256 cores, and a 192-core cluster of Intel Xeon E5-2630 2.3GHz processors. 

   more » « less
5. Spherical convex hull of random points on a wedge

   https://doi.org/10.1007/s00208-023-02704-9  

   Besau, Florian; Gusakova, Anna; Reitzner, Matthias; Schütt, Carsten; Thäle, Christoph; Werner, Elisabeth_M (August 2023, Mathematische Annalen)

   Abstract Consider two half-spaces$$H_1^+$$ $H_1^{+}$and$$H_2^+$$ $H_2^{+}$in$${\mathbb {R}}^{d+1}$$ $R^{d+1}$whose bounding hyperplanes$$H_1$$ $H_1$and$$H_2$$ $H_2$are orthogonal and pass through the origin. The intersection$${\mathbb {S}}_{2,+}^d:={\mathbb {S}}^d\cap H_1^+\cap H_2^+$$ $S_{2,+}^d:=S^d\cap H_1^{+}\cap H_2^{+}$is a spherical convex subset of thed-dimensional unit sphere$${\mathbb {S}}^d$$ $S^d$, which contains a great subsphere of dimension$$d-2$$ $d-2$and is called a spherical wedge. Choosenindependent random points uniformly at random on$${\mathbb {S}}_{2,+}^d$$ $S_{2,+}^d$and consider the expected facet number of the spherical convex hull of these points. It is shown that, up to terms of lower order, this expectation grows like a constant multiple of$$\log n$$ $logn$. A similar behaviour is obtained for the expected facet number of a homogeneous Poisson point process on$${\mathbb {S}}_{2,+}^d$$ $S_{2,+}^d$. The result is compared to the corresponding behaviour of classical Euclidean random polytopes and of spherical random polytopes on a half-sphere. 

   more » « less