An official website of the United States government
A<sc>bstract</sc> We use a combination of analytical and numerical methods to study out-of-time order correlators (OTOCs) in the sparse Sachdev-Ye-Kitaev (SYK) model. We find that at a given order ofN, the standard result for theq-local, all-to-all SYK, obtained through the sum over ladder diagrams, is corrected by a series in the sparsity parameter,k. We present an algorithm to sum the diagrams at any given order of 1/(kq)n. We also study OTOCs numerically as a function of the sparsity parameter and determine the Lyapunov exponent. We find that numerical stability when extracting the Lyapunov exponent requires averaging over a massive number of realizations. This trade-off between the efficiency of the sparse model and consistent behavior at finiteNbecomes more significant for larger values ofN.
more »
« less
Local decoding and testing of polynomials over grids
We study the local decodability and (tolerant) local testability of low‐degreen‐variate polynomials over arbitrary fields, evaluated over the domain {0,1}n. We show that for every field there is a tolerant local test whose query complexity depends only on the degree. In contrast we show that decodability is possible over fields of positive characteristic, but not over the reals.
more »
« less
- Award ID(s):
- 1715187
- PAR ID:
- 10165610
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 57
- Issue:
- 3
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 658-694
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Undirected C(sp3)−H functionalization reactions often follow site‐selectivity patterns that mirror the corresponding C−H bond dissociation energies (BDEs). This often results in the functionalization of weaker tertiary C−H bonds in the presence of stronger secondary and primary bonds. An important, contemporary challenge is the development of catalyst systems capable of selectively functionalizing stronger primary and secondary C−H bonds over tertiary and benzylic C−H sites. Herein, we report a Cu catalyst that exhibits a high degree of primary and secondary over tertiary C−H bond selectivity in the amidation of linear and cyclic hydrocarbons with aroyl azides ArC(O)N3. Mechanistic and DFT studies indicate that C−H amidation involves H‐atom abstraction from R‐H substrates by nitrene intermediates [Cu](κ2‐N,O‐NC(O)Ar) to provide carbon‐based radicals R.and copper(II)amide intermediates [CuII]‐NHC(O)Ar that subsequently capture radicals R.to form products R‐NHC(O)Ar. These studies reveal important catalyst features required to achieve primary and secondary C−H amidation selectivity in the absence of directing groups.more » « less
-
null (Ed.)We study the problems of identity and closeness testing of n-dimensional product distributions. Prior works of Canonne et al. (2017) and Daskalakis and Pan (2017) have established tight sample complexity bounds for non-tolerant testing over a binary alphabet: given two product distributions P and Q over a binary alphabet, distinguish between the cases P = Q and dTV(P;Q) > epsilon . We build on this prior work to give a more comprehensive map of the complexity of testing of product distributions by investigating tolerant testing with respect to several natural distance measures and over an arbitrary alphabet. Our study gives a fine-grained understanding of how the sample complexity of tolerant testing varies with the distance measures for product distributions. In addition, we also extend one of our upper bounds on product distributions to bounded-degree Bayes nets.more » « less
-
A collection of sets displays aproximity gapwith respect to some property if for every set in the collection, either (i) all members areδ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members areδ-close to the property. In particular, no set in the collection has roughly half of its membersδ-close to the property and the othersδ-far from it. We show that the collection of affine spaces displays a proximity gap with respect to Reed–Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to anyδsmaller than the Johnson/Guruswami–Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least)linearsize in the RS code dimension, forδsmaller than the unique decoding radius. Concretely, ifδis smaller than half the minimal distance of an RS code\(V\subset {\mathbb {F}}_q^n \), every affine space is either entirelyδ-close to the code, or alternatively at most an (n/q)-fraction of it isδ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed–Solomon codes (due to Berlekamp–Welch and Guruswami–Sudan) on aformal elementof an affine space. This involves working with Reed–Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.more » « less
-
Abstract We propose a new scalable platform for quantum computing (QC)—an array of optically trapped symmetric-top molecules (STMs) of the alkaline earth monomethoxide (MOCH3) family. Individual STMs form qubits, and the system is readily scalable to 100–1000 qubits. STM qubits have desirable features for QC compared to atoms and diatomic molecules. The additional rotational degree of freedom about the symmetric-top axis gives rise to closely spaced opposite parityK-doublets that allow full alignment at low electric fields, and the hyperfine structure naturally provides magnetically insensitive states with switchable electric dipole moments. These features lead to much reduced requirements for electric field control, provide minimal sensitivity to environmental perturbations, and allow for 2-qubit interactions that can be switched on at will. We examine in detail the internal structure of STMs relevant to our proposed platform, taking into account the full effective molecular Hamiltonian including hyperfine interactions, and identify useable STM qubit states. We then examine the effects of the electric dipolar interaction in STMs, which not only guide the design of high-fidelity gates, but also elucidate the nature of dipolar exchange in STMs. Under realistic experimental parameters, we estimate that the proposed QC platform could yield gate errors at the 10−3level, approaching that required for fault-tolerant QC.more » « less
