More Like this

1. 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
2. Isotope engineering for spin defects in van der Waals materials

   https://doi.org/10.1038/s41467-023-44494-3  

   Gong, Ruotian; Du, Xinyi; Janzen, Eli; Liu, Vincent; Liu, Zhongyuan; He, Guanghui; Ye, Bingtian; Li, Tongcang; Yao, Norman Y; Edgar, James H; et al (December 2024, Nature Communications)

   Abstract Spin defects in van der Waals materials offer a promising platform for advancing quantum technologies. Here, we propose and demonstrate a powerful technique based on isotope engineering of host materials to significantly enhance the coherence properties of embedded spin defects. Focusing on the recently-discovered negatively charged boron vacancy center ($${{{{{{{{\rm{V}}}}}}}}}_{{{{{{{{\rm{B}}}}}}}}}^{-}$$ $V_B^{-}$) in hexagonal boron nitride (hBN), we grow isotopically purified h¹⁰B¹⁵N crystals. Compared to$${{{{{{{{\rm{V}}}}}}}}}_{{{{{{{{\rm{B}}}}}}}}}^{-}$$ $V_B^{-}$in hBN with the natural distribution of isotopes, we observe substantially narrower and less crowded$${{{{{{{{\rm{V}}}}}}}}}_{{{{{{{{\rm{B}}}}}}}}}^{-}$$ $V_B^{-}$spin transitions as well as extended coherence timeT₂and relaxation timeT₁. For quantum sensing,$${{{{{{{{\rm{V}}}}}}}}}_{{{{{{{{\rm{B}}}}}}}}}^{-}$$ $V_B^{-}$centers in our h¹⁰B¹⁵N samples exhibit a factor of 4 (2) enhancement in DC (AC) magnetic field sensitivity. For additional quantum resources, the individual addressability of the$${{{{{{{{\rm{V}}}}}}}}}_{{{{{{{{\rm{B}}}}}}}}}^{-}$$ $V_B^{-}$hyperfine levels enables the dynamical polarization and coherent control of the three nearest-neighbor¹⁵N nuclear spins. Our results demonstrate the power of isotope engineering for enhancing the properties of quantum spin defects in hBN, and can be readily extended to improving spin qubits in a broad family of van der Waals materials. 

   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. Approximate Unitary t-Designs by Short Random Quantum Circuits Using Nearest-Neighbor and Long-Range Gates

   https://doi.org/10.1007/s00220-023-04675-z  

   Harrow, Aram W.; Mehraban, Saeed (May 2023, Communications in Mathematical Physics)

   Abstract We prove that$${{\,\textrm{poly}\,}}(t) \cdot n^{1/D}$$ $\text{poly}\left(t\right)·n^{1/D}$-depth local random quantum circuits with two qudit nearest-neighbor gates on aD-dimensional lattice withnqudits are approximatet-designs in various measures. These include the “monomial” measure, meaning that the monomials of a random circuit from this family have expectation close to the value that would result from the Haar measure. Previously, the best bound was$${{\,\textrm{poly}\,}}(t)\cdot n$$ $\text{poly}\left(t\right)·n$due to Brandão–Harrow–Horodecki (Commun Math Phys 346(2):397–434, 2016) for$$D=1$$ $D=1$. We also improve the “scrambling” and “decoupling” bounds for spatially local random circuits due to Brown and Fawzi (Scrambling speed of random quantum circuits, 2012). One consequence of our result is that assuming the polynomial hierarchy ($${{\,\mathrm{\textsf{PH}}\,}}$$ $\mathrm{PH}$) is infinite and that certain counting problems are$$\#{\textsf{P}}$$ $\#P$-hard “on average”, sampling within total variation distance from these circuits is hard for classical computers. Previously, exact sampling from the outputs of even constant-depth quantum circuits was known to be hard for classical computers under these assumptions. However the standard strategy for extending this hardness result to approximate sampling requires the quantum circuits to have a property called “anti-concentration”, meaning roughly that the output has near-maximal entropy. Unitary 2-designs have the desired anti-concentration property. Our result improves the required depth for this level of anti-concentration from linear depth to a sub-linear value, depending on the geometry of the interactions. This is relevant to a recent experiment by the Google Quantum AI group to perform such a sampling task with 53 qubits on a two-dimensional lattice (Arute in Nature 574(7779):505–510, 2019; Boixo et al. in Nate Phys 14(6):595–600, 2018) (and related experiments by USTC), and confirms their conjecture that$$O(\sqrt{n})$$ $O\left(\sqrt{n}\right)$depth suffices for anti-concentration. The proof is based on a previous construction oft-designs by Brandão et al. (2016), an analysis of how approximate designs behave under composition, and an extension of the quasi-orthogonality of permutation operators developed by Brandão et al. (2016). Different versions of the approximate design condition correspond to different norms, and part of our contribution is to introduce the norm corresponding to anti-concentration and to establish equivalence between these various norms for low-depth circuits. For random circuits with long-range gates, we use different methods to show that anti-concentration happens at circuit size$$O(n\ln ^2 n)$$ $O\left(n{ln}^{2}n\right)$corresponding to depth$$O(\ln ^3 n)$$ $O\left({ln}^{3}n\right)$. We also show a lower bound of$$\Omega (n \ln n)$$ $\Omega (nlnn)$for the size of such circuit in this case. We also prove that anti-concentration is possible in depth$$O(\ln n \ln \ln n)$$ $O(lnnlnlnn)$(size$$O(n \ln n \ln \ln n)$$ $O(nlnnlnlnn)$) using a different model. 

   more » « less
5. A Refutation of the Pach-Tardos Conjecture for 0–1 Matrices

   https://doi.org/10.1007/s00493-025-00187-7  

   Pettie, Seth; Tardos, Gábor (December 2025, Combinatorica)

   Abstract The theory of forbidden 0–1 matrices generalizes Turán-style (bipartite) subgraph avoidance, Davenport-Schinzel theory, and Zarankiewicz-type problems, and has been influential in many areas, such as discrete and computational geometry, the analysis of self-adjusting data structures, and the development of the graph parametertwin width. The foremost open problem in this area is to resolve thePach-Tardos conjecturefrom 2005, which states that if a forbidden pattern$$P\in \{0,1\}^{k\times l}$$ $P\in {\{0,1\}}^{k\times l}$isacyclic, meaning it is the bipartite incidence matrix of a forest, then$$\operatorname {Ex}(P,n) = O(n\log ^{C_P} n)$$ $Ex(P,n)=O\left(n{log}^{C_P}n\right)$, where$$\operatorname {Ex}(P,n)$$ $Ex(P,n)$is the maximum number of 1s in aP-free$$n\times n$$ $n\times n$0–1 matrix and$$C_P$$ $C_P$is a constant depending only onP. This conjecture has been confirmed on many small patterns, specifically allPwith weight at most 5, and all but two with weight 6. The main result of this paper is a clean refutation of the Pach-Tardos conjecture. Specifically, we prove that$$\operatorname {Ex}(S_0,n),\operatorname {Ex}(S_1,n) \ge n2^{\Omega (\sqrt{\log n})}$$ $Ex(S_0,n),Ex(S_1,n)\ge n{2}^{\Omega \left(\sqrt{logn}\right)}$, where$$S_0,S_1$$ $S_0,S_1$are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class ofalternatingpatterns$$(P_t)$$ $\left(P_t\right)$, specifically that for every$$t\ge 2$$ $t\ge 2$,$$\operatorname {Ex}(P_t,n)=\Theta (n(\log n/\log \log n)^t)$$ $Ex(P_t,n)=\Theta \left(n{(logn/loglogn)}^t\right)$. This is the first proof of an asymptotically sharp bound that is$$\omega (n\log n)$$ $\omega (nlogn)$. 

   more » « less