More Like this

1. Bounds on eigenfunctions of quantum cat maps

   https://doi.org/10.1088/1402-4896/ad0331  

   Kim, Elena; Koirala, Robert (October 2023, Physica Scripta)

   Abstract We studyℓ^∞norms ofℓ²-normalized eigenfunctions of quantum cat maps. For maps with short quantum periods (constructed by Bonechi and de Biévre in F Bonechi and S De Bièvre (2000,Communications in Mathematical Physics,211, 659–686)) we show that there exists a sequence of eigenfunctionsuwith $\parallel u{\parallel }_{\infty }\gtrsim {\left(\log N\right)}^{-1/2}$. For general eigenfunctions we show the upper bound $\parallel u{\parallel }_{\infty }\lesssim {\left(\log N\right)}^{-1/2}$. Here the semiclassical parameter is $h={\left(2\pi N\right)}^{-1}$. Our upper bound is analogous to the one proved by Bérard in P Bérard (1977,Mathematische Zeitschrift,155, 249-276) for compact Riemannian manifolds without conjugate points. 

   more » « less
2. 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
3. On the Size of the Singular Set of Minimizing Harmonic Maps

   https://doi.org/10.1090/memo/1519  

   Mazowiecka, Katarzyna; Miśkiewicz, Michał; Schikorra, Armin (October 2024, Memoirs of the American Mathematical Society)

   We consider minimizing harmonic maps $u$from $\mathrm{\Omega <\#comment/>}\subset <\#comment/>{\mathbb{R}}^n$into a closed Riemannian manifold $\mathcal{N}$and prove: 1. an extension to $n\ge <\#comment/>4$of Almgren and Lieb’s linear law. That is, if the fundamental group of the target manifold $\mathcal{N}$is finite, we have\[ ${\mathcal{H}}^{n-<\#comment/>3}(\mathrm{sing}<\#comment/>u)\le <\#comment/>C{\int <\#comment/>}_{\mathrm{\partial <\#comment/>}\mathrm{\Omega <\#comment/>}}|{\mathrm{\nabla <\#comment/>}}_{T}u{|}^{n-<\#comment/>1}\mathrm{d}{\mathcal{H}}^{n-<\#comment/>1};$\]2. an extension of Hardt and Lin’s stability theorem. Namely, assuming that the target manifold is $\mathcal{N}={\mathbb{S}}^2$we obtain that the singular set of $u$is stable under small $W^{1,n-<\#comment/>1}$-perturbations of the boundary data. In dimension $n=3$both results are shown to hold with weaker hypotheses, i.e., only assuming that the trace of our map lies in the fractional space $W^{s,p}$with $s\in <\#comment/>(\frac{1}{2},1]$and $p\in <\#comment/>[2,\mathrm{\infty <\#comment/>})$satisfying $sp\ge <\#comment/>2$. We also discuss sharpness. 

   more » « less
4. Optical spectral weight, phase stiffness, and T _c bounds for trivial and topological flat band superconductors

   https://doi.org/10.1073/pnas.2106744118  

   Verma, Nishchhal; Hazra, Tamaghna; Randeria, Mohit (August 2021, Proceedings of the National Academy of Sciences)

   We present exact results that give insight into how interactions lead to transport and superconductivity in a flat band where the electrons have no kinetic energy. We obtain bounds for the optical spectral weight for flat-band superconductors that lead to upper bounds for the superfluid stiffness and the two-dimensional (2D) $T_c$. We focus on on-site attraction $\left|U\right|$on the Lieb lattice with trivial flat bands and on the π-flux model with topological flat bands. For trivial flat bands, the low-energy optical spectral weight ${\tilde{D}}_{\text{low}}\le \tilde{n}\left|U\right|\mathrm{\Omega }/2$with $\tilde{n}=min\left(n,2-n\right)$, where n is the flat-band density and Ω is the Marzari–Vanderbilt spread of the Wannier functions (WFs). We also obtain a lower bound involving the quantum metric. For topological flat bands, with an obstruction to localized WFs respecting all symmetries, we again obtain an upper bound for ${\tilde{D}}_{low}$linear in $\left|U\right|$. We discuss the insights obtained from our bounds by comparing them with mean-field and quantum Monte Carlo results. 

   more » « less
5. 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