检索结果-内蒙古大学图书馆

On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Kapit, Eliot Barton, Brandon A. Feeney, Sean Grattan, George Patnaik, Pratik Sagal, Jacob Carr, Lincoln D. Oganesyan, Vadim Department of Physics Colorado School of Mines 1523 Illinois St GoldenCO80401 United States Department of Applied Mathematics and Statistics Colorado School of Mines 1500 Illinois St GoldenCO80401 United States Quantum Engineering Program Colorado School of Mines 1523 Illinois St GoldenCO80401 United States Department of Physics and Astronomy College of Staten Island CUNY Staten IslandNY10314 United States Physics Program and Initiative for the Theoretical Sciences The Graduate Center CUNY New YorkNY10016 United States Center for Computational Quantum Physics Flatiron Institute 162 5th Avenue New YorkNY10010 United States

A canonical feature of the constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard for all known methods. Fundamentally, the lack of any guided local minimum escape method ensures both exact and approximate classical approximation hardness, but the equivalent mechanism(s) for quantum algorithms are poorly understood. For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We review known results from the literature, and identify mechanisms that make conventional quantum methods (such as Adiabatic Quantum Computing) weak approximation algorithms in the worst case. We construct a family of "spectrally filtered" quantum algorithms that escape these issues, and develop analytical theories for their performance. We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be E = Nunsat - Nsat, spectrally filtered quantum optimization will return states with E ≤ qmEGS (where EGS is the ground state energy) in sub-quadratic time, where conservatively, qm 0.59. This is in contrast to qm → 0 for the hardest instances with classical searches. We test all of these claims with extensive numerical simulations. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm’s mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed. © 2023, CC BY.

关键词： Constraint satisfaction problems

Local number fluctuations in ordered and disordered phases of water across temperatures: Higher-order moments and degrees of tetrahedrality

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Klatt, Michael A. Kim, Jaeuk Gartner, Thomas E. Torquato, Salvatore Institute for AI Safety and Security Wilhelm-Runge-Str. 10 Ulm89081 Germany Institute for Material Physics in Space Köln51170 Germany Department of Physics Ludwig-Maximilians-Universität München Schellingstr. 4 Munich80799 Germany Department of Chemistry Princeton University PrincetonNJ08544 United States Department of Physics Princeton University PrincetonNJ08544 United States Princeton Materials Institute Princeton University PrincetonNJ08544 United States Department of Chemical & Biomolecular Engineering Lehigh University BethlehemPA18015 United States Program in Applied and Computational Mathematics Princeton University PrincetonNJ08544 United States

The isothermal compressibility (i.e., the asymptotic number variance) of equilibrium liquid water as a function of temperature is minimal near ambient conditions. This anomalous non-monotonic temperature dependence is due to a balance between thermal fluctuations and the formation of tetrahedral hydrogen-bond networks. Since tetrahedrality is a many-body property, it will also influence the higher-order moments of density fluctuations, including the skewness and kurtosis. To gain a more complete picture, we examine these higher-order moments that encapsulate many-body correlations using a recently developed, advanced platform for local density fluctuations. We study an extensive set of simulated phases of water across a range of temperatures (80 K to 1600 K) with various degrees of tetrahedrality, including ice phases, equilibrium liquid water, supercritical water, and disordered nonequilibrium quenches. We find clear signatures of tetrahedrality in the higher-order moments, including the skewness and excess kurtosis, that scale for all cases with the degree of tetrahedrality. More importantly, this scaling behavior leads to non-monotonic temperature dependencies in the higher-order moments for both equilibrium and non-equilibrium phases. Specifically, at near-ambient conditions, the higher-order moments vanish most rapidly for large length scales, and the distribution quickly converges to a Gaussian in our metric. However, at non-ambient conditions, higher-order moments vanish more slowly and hence become more relevant especially for improving information-theoretic approximations of hydrophobic solubility. The temperature non-monotonicity that we observe in the full distribution across length-scales could shed light on water's nested anomalies, i.e., reveal new links between structural, dynamic, and thermodynamic anomalies. © 2024, CC BY-NC-ND.

关键词： Higher order statistics

Breakdown of Boltzmann-type Models for the Alignment of Self-propelled Rods

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Murphy, Patrick Perepelitsa, Misha Timofeyev, Ilya Lieber-Kotz, Matan Islas, Brandon Igoshin, Oleg A. Department of Bioengineering Rice University HoustonTX77005 United States Center for Theoretical Biological Physics Rice University HoustonTX77005 United States Department of Mathematics University of Houston TX77204 United States Department of Computational and Applied Mathematics Rice University HoustonTX77005 United States Department of Chemistry Rice University HoustonTX77005 United States Department of Biosciences Rice University HoustonTX77005 United States

Studies in the collective motility of organisms use a range of analytical approaches to formulate continuous kinetic models of collective dynamics from rules or equations describing agent interactions. However, the derivation of these kinetic models often relies on Boltzmann’s hypothesis of"molecular chaos", that correlations between individuals are short-lived. While this assumption is often the simplest way to derive tractable models, it is often not valid in practice due to the high levels of cooperation and self-organization present in biological systems. In this work, we illustrated this point by considering a general Boltzmann-type kinetic model for the alignment of self-propelled rods where rod reorientation occurs upon binary collisions. We examine the accuracy of the kinetic model by comparing numerical solutions of the continuous equations to an agent-based model that implements the underlying rules governing microscopic alignment. Even for the simplest case considered, our comparison demonstrates that the kinetic model fails to replicate the discrete dynamics due to the formation of rod clusters that violate statistical independence. Additionally, we show that introducing noise to limit cluster formation helps improve the agreement between the analytical model and agent simulations but does not restore agreement completely. These results highlight the need to both develop and disseminate improved moment-closure methods for modeling biological and active matter systems. © 2023, CC BY.

关键词： Boltzmann equation

Impact of time-correlated noise on zero-noise extrapolation

学校读者我要写书评

暂无评论

Physical Review A 2022年第5期106卷 052406-052406页

作者： Kevin Schultz Ryan LaRose Andrea Mari Gregory Quiroz Nathan Shammah B. David Clader William J. Zeng Johns Hopkins University Applied Physics Laboratory Laurel Maryland 20723 USA Department of Computational Mathematics Science and Engineering Michigan State University East Lansing Michigan 48823 USA Unitary Fund Walnut California 91789 USA Goldman Sachs & Co New York New York 10282 USA

Zero-noise extrapolation is a quantum error mitigation technique that has typically been studied under the ideal approximation that the noise acting on a quantum device is not time correlated. In this paper, we investigate the feasibility and performance of zero-noise extrapolation in the presence of time-correlated noise. We show that, in contrast to white noise, time-correlated noise is harder to mitigate via zero-noise extrapolation because it is difficult to scale the noise level without also modifying its spectral distribution. This limitation is particularly strong if “local” gate-level methods are applied for noise scaling. However, we find that “global” noise-scaling methods, e.g., global unitary folding, can be sufficiently reliable even in the presence of time-correlated noise.

关键词： Quantum algorithms Quantum benchmarking Quantum control

Sequential Markov Chain Monte Carlo for Lagrangian Data Assimilation with Applications to Unknown Data Locations

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Ruzayqat, Hamza Beskos, Alexandros Crisan, Dan Jasra, Ajay Kantas, Nikolas Applied Mathematics and Computational Science Program Computer Electrical and Mathematical Sciences and Engineering Division King Abdullah University of Science and Technology Thuwal23955-6900 Saudi Arabia Department of Statistical Science University College London LondonWC1E 6BT United Kingdom Department of Mathematics Imperial College London LondonSW7 2AZ United Kingdom

We consider a class of high-dimensional spatial filtering problems, where the spatial locations of observations are unknown and driven by the partially observed hidden signal. This problem is exceptionally challenging as not only is high-dimensional, but the model for the signal yields longer-range time dependencies through the observation locations. Motivated by this model we revisit a lesser-known and provably convergent computational methodology from [4, 11, 28] that uses sequential Markov Chain Monte Carlo (MCMC) chains. We extend this methodology for data filtering problems with unknown observation locations. We benchmark our algorithms on Linear Gaussian state space models against competing ensemble methods and demonstrate a significant improvement in both execution speed and accuracy. Finally, we implement a realistic case study on a high-dimensional rotating shallow water model (of about 104 - 105 dimensions) with real and synthetic data. The data is provided by the National Oceanic and Atmospheric Administration (NOAA) and contains observations from ocean drifters in a domain of the Atlantic Ocean restricted to the longitude and latitude intervals [-51◦,-41◦], [17◦,27◦] *** Codes 62M20, 60G35, 60J20, 94A12, 93E11, 65C40 © 2023, CC BY.

关键词： Location

Equivariant geometric convolutions for emulation of dynamical systems

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Gregory, Wilson G. Hogg, David W. Blum-Smith, Ben Arias, Maria Teresa Wong, Kaze W.K. Villar, Soledad Department of Applied Mathematics and Statistics Johns Hopkins University BaltimoreMD United States Center for Cosmology and Particle Physics Department of Physics New York University New YorkNY United States Max-Planck-Institut für Astronomie Heidelberg Germany Center for Computational Astrophysics Flatiron Institute New YorkNY United States Department of Mathematics Universidad Autónoma de Madrid Madrid Spain Mathematical Institute for Data Science Johns Hopkins University BaltimoreMD United States

Machine learning methods are increasingly being employed as surrogate models in place of computationally expensive and slow numerical integrators for a bevy of applications in the natural sciences. However, while the laws of physics are relationships between scalars, vectors, and tensors that hold regardless of the frame of reference or chosen coordinate system, surrogate machine learning models are not coordinate-free by default. We enforce coordinate freedom by using geometric convolutions in three model architectures: a ResNet, a Dilated ResNet, and a UNet. In numerical experiments emulating 2D compressible Navier-Stokes, we see better accuracy and improved stability compared to baseline surrogate models in almost all cases. The ease of enforcing coordinate freedom without making major changes to the model architecture provides an exciting recipe for any CNN-based method applied to an appropriate class of problems. © 2023, CC BY.

关键词： Convolution

Finite-thickness effect of the fluids on bubbles and spikes in Richtmyer–Meshkov instability for arbitrary Atwood numbers

学校读者我要写书评

暂无评论

Plasma Science and Technology 2019年第2期21卷 9-15页

作者： Wanhai LIU Changping YU Pei WANG Zheng FU Lili WANG Yulian CHEN Research Center of Computational Physics Mianyang Normal University LHD Institute of MechanicsChinese Academy of Sciences Institute of Applied Physics and Computational Mathematics Mechanical and Electrical Engineering Department Lanzhou Resources and Environment Voc-Tech College

This paper investigates the finite-thickness effect of two superimposed fluids on bubbles and spikes in Richtmyer–Meshkov instability(RMI) for arbitrary Atwood numbers by using the method of the small parameter expansion up to the second order. When the thickness of the two fluids tends to be infinity, our results can reproduce the classical results where RMI happens at the interface separating two semi-infinity-thickness fluids of different densities. It is found that the thickness has a large influence on the amplitude evolution of bubbles and spikes compared with those in classical RMI. Based on the thickness relationship of the two fluids, the thickness effect on bubbles and spikes for four cases is discussed. The thickness encourages(or reduces)the growth of bubbles or spikes, depending on not only Atwood number, but also the relationship of the thickness ratio of the heavy and light fluids, which is explicitly determined in this paper.

关键词： Richtmyer–Meshkov instability bubbles and spikes finite-thickness

Complexity for an open quantum system

学校读者我要写书评

暂无评论

Physical Review D 2022年第4期105卷 046011-046011页

作者： Arpan Bhattacharyya Tanvir Hanif S. Shajidul Haque Md. Khaledur Rahman Indian Institute of Technology Gandhinagar Gujarat 382355 India Department of Theoretical Physics University of Dhaka Dhaka-1000 Bangladesh High Energy Physics Cosmology & Astrophysics Theory Group and The Laboratory for Quantum Gravity & Strings Department of Mathematics and Applied Mathematics University of Cape Town Rondebosch Cape Town 7700 South Africa National Institute for Theoretical and Computational Sciences (NITheCS) Rondebosch Cape Town 7700 South Africa

We study the complexity for an open quantum system. Our system is a harmonic oscillator coupled to a one-dimensional massless scalar field, which acts as the bath. Specifically, we consider the reduced density matrix by tracing out the bath degrees of freedom for both regular and inverted oscillators and compute the complexity of purification (COP) and complexity by using the operator-state mapping. We find that when the oscillator is regular, the COP saturates quickly for both underdamped and overdamped oscillators. Interestingly, when the oscillator is underdamped, we discover a kink-like behavior for the saturation value of the COP with a varying damping coefficient. For the inverted oscillator, we find a linear growth of the COP with time for all values of the bath-system interaction. However, when the interaction is increased the slope of the linear growth decreases, implying that the unstable nature of the system can be regulated by the bath.

关键词： computational complexity Gauge-gravity dualities Open quantum systems Quantum chaos

Diffusion spreadability as a probe of the microstructure of complex media across length scales

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Torquato, Salvatore Department of Chemistry Princeton Institute for the Science and Technology of Materials Program in Applied and Computational Mathematics Princeton University PrincetonNJ08544 United States

Understanding time-dependent diffusion processes in multiphase media is of great importance in physics, chemistry, materials science, petroleum engineering and biology. Consider the time-dependent problem of mass transfer of a solute between two phases and assume that the solute is initially distributed in one phase (phase 2) and absent from the other (phase 1). We desire the fraction of total solute present in phase 1 as a function of time, S(t), which we call the spreadability, since it is a measure of the spreadability of diffusion information as a function of time. We derive exact direct-space formulas for S(t) in any Euclidean space dimension d in terms of the autocovariance function as well as corresponding Fourier representations of S(t) in terms of the spectral density, which are especially useful when scattering information is available experimentally or theoretically. These are singular results because they are rare examples of mass transport problems where exact solutions are possible. We derive closed-form general formulas for the short- and long-time behaviors of the spreadability in terms of crucial small- and large-scale microstructural information, respectively. The long-time behavior of S(t) enables one to distinguish the entire spectrum of microstructures that span from hyperuniform to nonhyperuniform media. For hyperuniform media, disordered or not, we show that the "excess" spreadability, S(∞) − S(t), decays to its long-time behavior exponentially faster than that of any nonhyperuniform two-phase medium, the "slowest" being antihyperuniform media. The stealthy hyperuniform class is characterized by an excess spreadability with the fastest decay rate among all translationally invariant microstructures. We obtain exact results for S(t) for a variety of specific ordered and disordered model microstructures across dimensions that span from hyperuniform to antihyperuniform media. Moreover, we establish a remarkable connection between the spreadability

关键词： Microstructure