More Like this

1. Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms

   https://doi.org/10.1007/s00224-022-10106-8  

   Vyas, Nikhil ; Williams, R. Ryan ( November 2022 , Theory of Computing Systems)

   We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$$\mathrm{Quasi}-\mathrm{NP}=\mathrm{NTIME}\left[n^{{\left(\log n\right)}^{O\left(1\right)}}\right]$and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathcal { C}$$C$, by showing that$\mathcal { C}$$C$admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class${\mathcal C}$$C$. Say that a symmetric Boolean functionf(x₁,…,x_n) issparseif it outputs 1 onO(1) values of${\sum }_{i} x_{i}$${\sum }_i{x}_i$. We show that for every sparsef, and for all “typical”$\mathcal { C}$$C$, faster#SAT algorithms for$\mathcal { C}$$C$circuits imply lower bounds against the circuit class$f \circ \mathcal { C}$$f\circ C$, which may bestrongerthan$\mathcal { C}$$C$itself. In particular:

   #SAT algorithms forn^k-size$\mathcal { C}$$C$-circuits running in 2ⁿ/n^ktime (for allk) implyNEXPdoes not have$(f \circ \mathcal { C})$$(f\circ C)$-circuits of polynomial size.

   #SAT algorithms for$2^{n^{{\varepsilon }}}$$2^{n^{\epsilon }}$-size$\mathcal { C}$$C$-circuits running in$2^{n-n^{{\varepsilon }}}$$2^{n-n^{\epsilon }}$time (for someε> 0) implyQuasi-NPdoes not have$(f \circ \mathcal { C})$$(f\circ C)$-circuits of polynomial size.

   Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJ∘ACC⁰∘THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC⁰[Williams JACM’14] andACC⁰∘THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.

    

   more » « less
2. The FRB 20190520B Sight Line Intersects Foreground Galaxy Clusters

   https://doi.org/10.3847/2041-8213/acefb5  

   Lee, Khee-Gan ; Khrykin, Ilya S. ; Simha, Sunil ; Ata, Metin ; Huang, Yuxin ; Prochaska, J. Xavier ; Tejos, Nicolas ; Cooke, Jeff ; Nagamine, Kentaro ; Zhang, Jielai ( August 2023 , The Astrophysical Journal Letters)

   The repeating fast radio burst FRB 20190520B is an anomaly of the FRB population thanks to its high dispersion measure (DM = 1205 pc cm⁻³) despite its low redshift ofz_frb= 0.241. This excess has been attributed to a large host contribution of DM_host≈ 900 pc cm⁻³, far larger than any other known FRB. In this paper, we describe spectroscopic observations of the FRB 20190520B field obtained as part of the FLIMFLAM survey, which yielded 701 galaxy redshifts in the field. We find multiple foreground galaxy groups and clusters, for which we then estimated halo masses by comparing their richness with numerical simulations. We discover two separateM_halo> 10¹⁴M_⊙galaxy clusters atz= 0.1867 and 0.2170 that are directly intersected by the FRB sight line within their characteristic halo radiusr₂₀₀. Subtracting off their estimated DM contributions, as well that of the diffuse intergalactic medium, we estimate a host contribution of${\mathrm{D}\mathrm{M}}_{\mathrm{h}\mathrm{o}\mathrm{s}\mathrm{t}}={430}_{-220}^{+140}$or${280}_{-170}^{+140}\mathrm{p}\mathrm{c}{\mathrm{c}\mathrm{m}}^{-3}$(observed frame), depending on whether we assume that the halo gas extends tor₂₀₀or 2 ×r₂₀₀. This significantly smaller DM_host—no longer the largest known value—is now consistent with Hαemission measures of the host galaxy without invoking unusually high gas temperatures. Combined with the observed FRB scattering timescale, we estimate the turbulent fluctuation and geometric amplification factor of the scattering layer to be$\tilde{F}G\approx 4.5–11{({\mathrm{pc}}^2\mathrm{km})}^{-1/3}$, suggesting that most of the gas is close to the FRB host. This result illustrates the importance of incorporating foreground data for FRB analyses both for understanding the nature of FRBs and to realize their potential as a cosmological probe.

    

   more » « less
3. Random Quantum Circuits Transform Local Noise into Global White Noise

   https://doi.org/10.1007/s00220-024-04958-z  

   Dalzell, Alexander M. ; Hunter-Jones, Nicholas ; Brandão, Fernando G. S. L. ( March 2024 , Communications in Mathematical Physics)

   We study the distribution over measurement outcomes of noisy random quantum circuits in the regime of low fidelity, which corresponds to the setting where the computation experiences at least one gate-level error with probability close to one. We model noise by adding a pair of weak, unital, single-qubit noise channels after each two-qubit gate, and we show that for typical random circuit instances, correlations between the noisy output distribution$$p_{\text {noisy}}$$$p_{\text{noisy}}$and the corresponding noiseless output distribution$$p_{\text {ideal}}$$$p_{\text{ideal}}$shrink exponentially with the expected number of gate-level errors. Specifically, the linear cross-entropy benchmarkFthat measures this correlation behaves as$$F=\text {exp}(-2s\epsilon \pm O(s\epsilon ^2))$$$F=\text{exp}(-2sϵ\pm O\left(s{ϵ}^2\right))$, where$$\epsilon $$$ϵ$is the probability of error per circuit location andsis the number of two-qubit gates. Furthermore, if the noise is incoherent—for example, depolarizing or dephasing noise—the total variation distance between the noisy output distribution$$p_{\text {noisy}}$$$p_{\text{noisy}}$and the uniform distribution$$p_{\text {unif}}$$$p_{\text{unif}}$decays at precisely the same rate. Consequently, the noisy output distribution can be approximated as$$p_{\text {noisy}}\approx Fp_{\text {ideal}}+ (1-F)p_{\text {unif}}$$$p_{\text{noisy}}\approx F{p}_{\text{ideal}}+(1-F)p_{\text{unif}}$. In other words, although at least one local error occurs with probability$$1-F$$$1-F$, the errors are scrambled by the random quantum circuit and can be treated as global white noise, contributing completely uniform output. Importantly, we upper bound the average total variation error in this approximation by$$O(F\epsilon \sqrt{s})$$$O\left(Fϵ\sqrt{s}\right)$. Thus, the “white-noise approximation” is meaningful when$$\epsilon \sqrt{s} \ll 1$$$ϵ\sqrt{s}\ll 1$, a quadratically weaker condition than the$$\epsilon s\ll 1$$$ϵs\ll 1$requirement to maintain high fidelity. The bound applies if the circuit size satisfies$$s \ge \Omega (n\log (n))$$$s\ge \Omega (nlog(n\left)\right)$, which corresponds to onlylogarithmic depthcircuits, and if, additionally, the inverse error rate satisfies$$\epsilon ^{-1} \ge {\tilde{\Omega }}(n)$$${ϵ}^{-1}\ge \tilde{\Omega }\left(n\right)$, which is needed to ensure errors are scrambled faster thanFdecays. The white-noise approximation is useful for salvaging the signal from a noisy quantum computation; for example, it was an underlying assumption in complexity-theoretic arguments that noisy random quantum circuits cannot be efficiently sampled classically, even when the fidelity is low. Our method is based on a map from second-moment quantities in random quantum circuits to expectation values of certain stochastic processes for which we compute upper and lower bounds.

    

   more » « less
4. Now You See It, Now You Don’t: Star Formation Truncation Precedes the Loss of Molecular Gas by ∼100 Myr in Massive Poststarburst Galaxies at z ∼ 0.6

   https://doi.org/10.3847/1538-4357/ac3dfa  

   Bezanson, Rachel ; Spilker, Justin S. ; Suess, Katherine A. ; Setton, David J. ; Feldmann, Robert ; Greene, Jenny E. ; Kriek, Mariska ; Narayanan, Desika ; Verrico, Margaret ( February 2022 , The Astrophysical Journal)

   We use ALMA observations of CO(2–1) in 13 massive (M_*≳ 10¹¹M_⊙) poststarburst galaxies atz∼ 0.6 to constrain the molecular gas content in galaxies shortly after they quench their major star-forming episode. The poststarburst galaxies in this study are selected from the Sloan Digital Sky Survey spectroscopic samples (Data Release 14) based on their spectral shapes, as part of the Studying QUenching at Intermediate-z Galaxies: Gas, angu$$\overrightarrow{L}\mathrm{ar}$$momentum, and Evolution ($\mathit{SQuIGG}\vec{L}E$) program. Early results showed that two poststarburst galaxies host large H₂reservoirs despite their low inferred star formation rates (SFRs). Here we expand this analysis to a larger statistical sample of 13 galaxies. Six of the primary targets (45%) are detected, with$M_{{\mathrm{H}}_2}\gtrsim {10}^9$M_⊙. Given their high stellar masses, this mass limit corresponds to an average gas fraction of$〈f_{{\mathrm{H}}_2}\equiv M_{{\mathrm{H}}_2}/M_{*}〉\sim 7\%$or ∼14% using lower stellar masses estimates derived from analytic, exponentially declining star formation histories. The gas fraction correlates with theD_n4000 spectral index, suggesting that the cold gas reservoirs decrease with time since burst, as found in local K+A galaxies. Star formation histories derived from flexible stellar population synthesis modeling support this empirical finding: galaxies that quenched ≲150 Myr prior to observation host detectable CO(2–1) emission, while older poststarburst galaxies are undetected. The large H₂reservoirs and low SFRs in the sample imply that the quenching of star formation precedes the disappearance of the cold gas reservoirs. However, within the following 100–200 Myr, the$\mathit{SQuIGG}\vec{L}E$galaxies require the additional and efficient heating or removal of cold gas to bring their low SFRs in line with standard H₂scaling relations.

    

   more » « less
5. The Large Dispersion and Scattering of FRB 20190520B Are Dominated by the Host Galaxy

   https://doi.org/10.3847/1538-4357/ac6504  

   Koch Ocker, Stella ; Cordes, James M. ; Chatterjee, Shami ; Niu, Chen-Hui ; Li, Di ; McKee, James W. ; Law, Casey J. ; Tsai, Chao-Wei ; Anna-Thomas, Reshma ; Yao, Ju-Mei ; et al ( May 2022 , The Astrophysical Journal)

   The repeating fast radio burst FRB 20190520B is localized to a galaxy atz= 0.241, much closer than expected given its dispersion measure DM = 1205 ± 4 pc cm⁻³. Here we assess implications of the large DM and scattering observed from FRB 20190520B for the host galaxy’s plasma properties. A sample of 75 bursts detected with the Five-hundred-meter Aperture Spherical radio Telescope shows scattering on two scales: a mean temporal delayτ(1.41 GHz) = 10.9 ± 1.5 ms, which is attributed to the host galaxy, and a mean scintillation bandwidth Δν_d(1.41 GHz) = 0.21 ± 0.01 MHz, which is attributed to the Milky Way. Balmer line measurements for the host imply an Hαemission measure (galaxy frame) EM_s= 620 pc cm⁻⁶× (T/10⁴K)^0.9, implying DM_Hαof order the value inferred from the FRB DM budget,${\mathrm{DM}}_{\mathrm{h}}={1121}_{-138}^{+89}$pc cm⁻³for plasma temperatures greater than the typical value 10⁴K. Combiningτand DM_hyields a nominal constraint on the scattering amplification from the host galaxy$\tilde{F}G={1.5}_{-0.3}^{+0.8}{({\mathrm{pc}}^2\mathrm{km})}^{-1/3}$, where$\tilde{F}$describes turbulent density fluctuations andGrepresents the geometric leverage to scattering that depends on the location of the scattering material. For a two-screen scattering geometry whereτarises from the host galaxy and Δν_dfrom the Milky Way, the implied distance between the FRB source and dominant scattering material is ≲100 pc. The host galaxy scattering and DM contributions support a novel technique for estimating FRB redshifts using theτ–DM relation, and are consistent with previous findings that scattering of localized FRBs is largely dominated by plasma within host galaxies and the Milky Way.

    

   more » « less