Search

Alon, Seymour, and Thomas [J. Amer. Math. Soc., 3 (1990), pp. 801-808] proved that every n-vertex graph excluding Kt as a minor has treewidth less than t3/2 \surdn. Illingworth, Scott, and Wood [Product Structure of Graphs with an Excluded Minor, preprint, arXiv:2104.06627, 2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth t - 2, where each vertex is blown up by a complete graph of order \scrO(\surdtn). Solving an open problem of Illingworth, Scott, and Wood [2022], we prove that the treewidth bound can be reduced to 4 while keeping blowups of order \scrOt(\surdn). As an extension of the Lipton-Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to 2, which is best possible. We generalize this result for K3,t-minor-free graphs, with blowups of order \scrO(t\surdn). This setting includes graphs embeddable on any fixed surface.

Isthmic spondylolysis is characterized by a stress injury to the pars interarticularis bones of the lumbar spines and is often missed by conventional magnetic resonance imaging (MRI), necessitating a computed tomography (CT) for accurate diagnosis. We compare MRI techniques suitable for producing CT-like images. Lumbar spines of asymptomatic and low back pain (LBP) subjects were imaged at 3-Tesla with multi-echo ultrashort echo time (UTE) and field echo (FE) sequences followed by simple post-processing of averaging and inverting to depict spinal bones with a CT-like appearance. The contrast-to-noise ratio (CNR) for bone was determined to compare UTE vs. FE and single-echo vs. multi-echo data. Visually, both sequences depicted cortical bone with good contrast; UTE-processed sequences provided a flatter contrast for soft tissues that made them easy to distinguish from bone, while FE-processed images had better resolution and bone–muscle contrast, which are important for fracture detection. Additionally, multi-echo images provided significantly (p = 0.03) greater CNR compared with single-echo images. Using these techniques, progressive spondylolysis was detected in an LBP subject. This study demonstrates the feasibility of using spine bone MRI to yield CT-like contrast. Through the employment of multi-echo UTE and FE sequences combined with simple processing, we observe sufficient enhancements in image quality and contrast to detect pars fractures.

We propose a rich foundational theory of typed data streams and stream transformers, motivated by two high-level goals. First, the type of a stream should be able to express complex sequential patterns of events over time. And second, it should describe the internal parallel structure of the stream, to support deterministic stream processing on parallel and distributed systems. To these ends, we introduce stream types, with operators capturing sequential composition, parallel composition, and iteration, plus a core calculus λST of transformers over typed streams that naturally supports a number of common streaming idioms, including punctuation, windowing, and parallel partitioning, as first-class constructions. λST exploits a Curry-Howard-like correspondence with an ordered variant of the Logic of Bunched Implication to program with streams compositionally and uses Brzozowski-style derivatives to enable an incremental, prefix-based operational semantics. To illustrate the programming style supported by the rich types of λST, we present a number of examples written in Delta, a prototype high-level language design based on λST.

This paper presents a single-chip bits-to-antenna transmitter (TX) for >100 Gbps in 45nm CMOS SOI. The construction of the 64QAM constellation is achieved directly in the RF domain by utilizing three QPSK sub-TXs with weighted amplitude. This method significantly reduces the need to address power amplifier nonlinear effects in high-order modulation, thereby creating room for TX enhancements in both bandwidth and output power. To further improve TX performance, multi-step phase alignment strategies, and a local oscillator leakage suppression technique have been incorporated. With 40-GHz RF bandwidth, the RF-64QAM TX prototype is able to achieve a measured data rate of 120 Gbps with 15dBm effective isotropic radiated power (EIRP).

Hardware execution attacks exploit subtle microarchitectural interactions to leak secret data. While checking programs for the existence of such attacks is essential, verification of software against the full hardware implementation does not scale. Verification using abstract formal models of the hardware can help provide strong security guarantees while leveraging abstraction to achieve scalability. However, handwriting accurate abstract models is tedious and error-prone. Hence, we need techniques to generate models that enable sound yet scalable security analysis automatically.In this work, we propose micro-update models as a modelling framework that enables sound and abstract modelling of microarchitectural features. We also develop algorithms to generate micro-update models from RTL semi-automatically. We implement our modelling and generation framework in a prototype tool called PAUL. We evaluate our approach by synthesizing micro-update models for the Sodor5Stage processor and components from the cva6 (Ariane) processor. We demonstrate how these models can be generated hierarchically, thus increasing scalability to larger designs. We observe up to 8× improvement in run time when performing analysis with the generated models as compared to the source RTL.

High throughput screening (HTS) is routinely used to identify bioactive small molecules. This requires physical compounds, which limits coverage of accessible chemical space. Computational approaches combined with vast on-demand chemical libraries can access far greater chemical space, provided that the predictive accuracy is sufficient to identify useful molecules. Through the largest and most diverse virtual HTS campaign reported to date, comprising 318 individual projects, we demonstrate that our AtomNet® convolutional neural network successfully finds novel hits across every major therapeutic area and protein class. We address historical limitations of computational screening by demonstrating success for target proteins without known binders, high-quality X-ray crystal structures, or manual cherry-picking of compounds. We show that the molecules selected by the AtomNet® model are novel drug-like scaffolds rather than minor modifications to known bioactive compounds. Our empirical results suggest that computational methods can substantially replace HTS as the first step of small-molecule drug discovery.

The use of uncrewed aerial vehicles (UAVs) in cell-free networks is poised to unleash a number of new opportunities to further improve wireless networks. However, cell-free UAV networks present major challenges related to the wireless nature of access and fronthaul links. This manuscript studies the uplink of cell-free systems where users connect to UAVs, the latter devices forwarding the information to a processing point through imperfect wireless fronthaul links. Three multiple access alternatives are considered for the fronthaul, namely frequency division multiples access, spatial division multiple access, and combinations thereof. Deterministic equivalent expressions for the spectral efficiency under these fronthaul schemes and minimum mean-square error reception are derived. Then, the optimization subproblems of (a) the 3D deployment of the UAVs, (b) the user transmit powers, and (c) the UAV transmit powers, are investigated. The joint optimization of these subproblems yields superior performance, with the 3D deployment being the main source of improvement.

We study a heterogeneous Rayleigh fading wireless sensor network (WSN) in which sensor nodes surveil a field of interest and communicate their sensory data with base stations with the aid of access points as relays. With the goal of improving the energy efficiency of the network, we consider both large-scale and small-scale signal propagation effects in our system model and aim to optimize the node deployment as an effective measure to reduce the wireless communication power consumption of the WSN. We propose a new framework, in which hard deterministic connectivity constraints on communication links are replaced with realistic limitations on outage due to severe stochastic fading. We also consider a radio energy model that reflects the exponential dependence of the transmission power on the rate. We derive the necessary conditions for the optimal deployment that not only minimize the power consumption, but also guarantee all wireless links to have an outage probability below the given threshold. Our theoretical findings are accompanied by simulations that indicate significant performance gains compared to existing node deployment algorithms in the literature.

Structure-based virtual screening is a key tool in early drug discovery, with growing interest in the screening of multi-billion chemical compound libraries. However, the success of virtual screening crucially depends on the accuracy of the binding pose and binding affinity predicted by computational docking. Here we develop a highly accurate structure-based virtual screen method, RosettaVS, for predicting docking poses and binding affinities. Our approach outperforms other state-of-the-art methods on a wide range of benchmarks, partially due to our ability to model receptor flexibility. We incorporate this into a new open-source artificial intelligence accelerated virtual screening platform for drug discovery. Using this platform, we screen multi-billion compound libraries against two unrelated targets, a ubiquitin ligase target KLHDC2 and the human voltage-gated sodium channel NaV1.7. For both targets, we discover hit compounds, including seven hits (14% hit rate) to KLHDC2 and four hits (44% hit rate) to NaV1.7, all with single digit micromolar binding affinities. Screening in both cases is completed in less than seven days. Finally, a high resolution X-ray crystallographic structure validates the predicted docking pose for the KLHDC2 ligand complex, demonstrating the effectiveness of our method in lead discovery.

Abstract: The entropic doubling of a random variable taking values in an abelian group is a variant of the notion of the doubling constant of a finite subset of , but it enjoys somewhat better properties; for instance, it contracts upon applying a homomorphism. In this paper we develop further the theory of entropic doubling and give various applications, including: (1) A new proof of a result of Pálvölgyi and Zhelezov on the “skew dimension” of subsets of with small doubling; (2) A new proof, and an improvement, of a result of the second author on the dimension of subsets of with small doubling; (3) A proof that the Polynomial Freiman–Ruzsa conjecture over implies the (weak) Polynomial Freiman–Ruzsa conjecture over .

We present a new framework based on quantization theory to design cellular networks optimized for both legacy ground users and uncrewed aerial vehicle (UAV) corridors, dedicated aerial highways for safe UAV flights. Our framework leverages antenna tilts and transmit power at each base station to enhance coverage and quality of service among users. We develop a comprehensive mathematical analysis and optimization algorithms for multiple system-level performance metrics, including received signal strength and signal-to-interference-plus-noise ratio. Realistic antenna radiation patterns and propagation channel models are considered, alongside a generic 3D user distribution that allows for performance prioritization on the ground, along UAV corridors, or a desired tradeoff between the two. We demonstrate the efficacy of the proposed framework through case studies, showcasing the non-trivial combinations of antenna tilts and power levels that improve coverage and signal quality along UAV corridors while incurring only a marginal impact on the ground user performance compared to scenarios without UAVs.

The quantum computation of molecular response properties on near-term quantum hardware is a topic of substantial interest. Computing these properties directly in the frequency domain is desirable, but the circuits require large depth if the typical hardware gate set consisting of single- and two-qubit gates is used. While high-fidelity multipartite gates have been reported recently, their integration into quantum simulation and the demonstration of improved accuracy of the observable properties remains to be shown. Here, we report the application of a high-fidelity multipartite gate, the iToffoli gate, to the computation of frequency-domain response properties of diatomic molecules. The iToffoli gate enables a ~50% reduction in circuit depth and ~40% reduction in circuit execution time compared to the traditional gate set. We show that the molecular properties obtained with the iToffoli gate exhibit comparable or better agreement with theory than those obtained with the native CZ gates. Our work is among the first demonstrations of the practical usage of a native multi-qubit gate in quantum simulation, with diverse potential applications to near-term quantum computation.

Polypharmacology drugs-compounds that inhibit multiple proteins-have many applications but are difficult to design. To address this challenge we have developed POLYGON, an approach to polypharmacology based on generative reinforcement learning. POLYGON embeds chemical space and iteratively samples it to generate new molecular structures; these are rewarded by the predicted ability to inhibit each of two protein targets and by drug-likeness and ease-of-synthesis. In binding data for >100,000 compounds, POLYGON correctly recognizes polypharmacology interactions with 82.5% accuracy. We subsequently generate de-novo compounds targeting ten pairs of proteins with documented co-dependency. Docking analysis indicates that top structures bind their two targets with low free energies and similar 3D orientations to canonical single-protein inhibitors. We synthesize 32 compounds targeting MEK1 and mTOR, with most yielding >50% reduction in each protein activity and in cell viability when dosed at 1-10 μM. These results support the potential of generative modeling for polypharmacology.

Verification of asynchronous distributed programs is challenging due to the need to reason about numerous control paths resulting from the myriad interleaving of messages and failures. In this paper, we propose an automated bookkeeping method based on message chains. Message chains reveal structure in asynchronous distributed system executions and can help programmers verify their systems at the message passing level of abstraction. To evaluate our contributions empirically we build a verification prototype for the P programming language that integrates message chains. We use it to verify 16 benchmarks from related work, one new benchmark that exemplifies the kinds of systems our method focuses on, and two industrial benchmarks. We find that message chains are able to simplify existing proofs and our prototype performs comparably to existing work in terms of runtime. We extend our work with support for specification mining and find that message chains provide enough structure to allow existing learning and program synthesis tools to automatically infer meaningful specifications using only execution examples.

This article presents a fast and approximate multifrontal solver for large sparse linear systems. In a recent work by Liu et al., we showed the efficiency of a multifrontal solver leveraging the butterfly algorithm and its hierarchical matrix extension, HODBF (hierarchical off-diagonal butterfly) compression to compress large frontal matrices. The resulting multifrontal solver can attain quasi-linear computation and memory complexity when applied to sparse linear systems arising from spatial discretization of high-frequency wave equations. To further reduce the overall number of operations and especially the factorization memory usage to scale to larger problem sizes, in this article we develop a composite multifrontal solver that employs the HODBF format for large-sized fronts, a reduced-memory version of the nonhierarchical block low-rank format for medium-sized fronts, and a lossy compression format for small-sized fronts. This allows us to solve sparse linear systems of dimension up to 2.7 × larger than before and leads to a memory consumption that is reduced by 70% while ensuring the same execution time. The code is made publicly available in GitHub.

Choreographic programming is an emerging paradigm for programming distributed systems. In choreographic programming, the programmer describes the behavior of the entire system as a single, unified program -- a choreography -- which is then compiled to individual programs that run on each node, via a compilation step called endpoint projection. We present a new model for functional choreographic programming where choreographies are expressed as computations in a monad. Our model supports cutting-edge choreographic programming features that enable modularity and code reuse: in particular, it supports higher-order choreographies, in which a choreography may be passed as an argument to another choreography, and location-polymorphic choreographies, in which a choreography can abstract over nodes. Our model is implemented in a Haskell library, HasChor , which lets programmers write choreographic programs while using the rich Haskell ecosystem at no cost, bringing choreographic programming within reach of everyday Haskellers. Moreover, thanks to Haskell's abstractions, the implementation of the HasChor library itself is concise and understandable, boiling down endpoint projection to its short and simple essence.

Formal verification can help ensure the correctness of today's processors. However, such formal verification requires formal specifications of the processors being verified. Today, these specifications are mostly written by hand, which is tedious and error-prone. Furthermore, architects and hardware engineers generally do not have formal methods experience, making it even harder for them to write formal specifications. Existing methods for the automated synthesis of formal microarchitectural specifications utilise RTL implementations of processors for their synthesis, preventing their usage until RTL implementation of the processor has completed. This hampers the effectiveness of formal verification for processors, as catching design bugs pre-RTL can reduce verification overhead and overall development time. In response, we present PipeSynth, an automated formal methodology and tool for the synthesis of μspec microarchitectural ordering axioms from small example programs (litmus tests) and microarchitectural execution traces. PipeSynth helps architects automatically generate formal specifications for their microarchitectures before RTL is even written, enabling greater use of formal verification on today's microarchitectures. We evaluate PipeSynth's capability to synthesise single axioms and multiple axioms at the same time across four microarchitectures. Our evaluated microarchitectures include an out-of-order processor and one with a non-traditional coherence protocol. In single-axiom synthesis, PipeSynth is capable of synthesising replacement axioms for 42 out of 46 axioms from our evaluated microarchitectures in under 2 hours per axiom. When doing multi-axiom synthesis, we are able to synthesise an entire microarchitectural specification for the in-order Multi-V-scale processor in under 1 hour, and can synthesise at least 4 nontrivial axioms at the same time for our other microarchitectures.

The nonstructural protein 3 (NSP3) of the severe acute respiratory syndrome-coronavirus-2 (SARS-CoV-2) contains a conserved macrodomain enzyme (Mac1) that is critical for pathogenesis and lethality. While small-molecule inhibitors of Mac1 have great therapeutic potential, at the outset of the COVID-19 pandemic, there were no well-validated inhibitors for this protein nor, indeed, the macrodomain enzyme family, making this target a pharmacological orphan. Here, we report the structure-based discovery and development of several different chemical scaffolds exhibiting low- to sub-micromolar affinity for Mac1 through iterations of computer-aided design, structural characterization by ultra-high-resolution protein crystallography, and binding evaluation. Potent scaffolds were designed with in silico fragment linkage and by ultra-large library docking of over 450 million molecules. Both techniques leverage the computational exploration of tangible chemical space and are applicable to other pharmacological orphans. Overall, 160 ligands in 119 different scaffolds were discovered, and 153 Mac1-ligand complex crystal structures were determined, typically to 1 Å resolution or better. Our analyses discovered selective and cell-permeable molecules, unexpected ligand-mediated conformational changes within the active site, and key inhibitor motifs that will template future drug development against Mac1.

Contemporary methods for benchmarking noisy quantum processors typically measure average error rates or process infidelities. However, thresholds for fault-tolerant quantum error correction are given in terms of worst-case error rates—defined via the diamond norm—which can differ from average error rates by orders of magnitude. One method for resolving this discrepancy is to randomize the physical implementation of quantum gates, using techniques like randomized compiling (RC). In this work, we use gate set tomography to perform precision characterization of a set of two-qubit logic gates to study RC on a superconducting quantum processor. We find that, under RC, gate errors are accurately described by a stochastic Pauli noise model without coherent errors, and that spatially correlated coherent errors and non-Markovian errors are strongly suppressed. We further show that the average and worst-case error rates are equal for randomly compiled gates, and measure a maximum worst-case error of 0.0197(3) for our gate set. Our results show that randomized benchmarks are a viable route to both verifying that a quantum processor’s error rates are below a fault-tolerance threshold, and to bounding the failure rates of near-term algorithms, if—and only if—gates are implemented via randomization methods which tailor noise.

Given a class of graphs H , the problem ⊕ Sub (H) is defined as follows. The input is a graph H ∈ H together with an arbitrary graph G. The problem is to compute, modulo 2, the number of subgraphs of G that are isomorphic to H. The goal of this research is to determine for which classes H the problem ⊕ Sub (H) is fixed-parameter tractable (FPT), i.e., solvable in time f (| H |) · | G | O (1) . Curticapean, Dell, and Husfeldt (ESA 2021) conjectured that ⊕ Sub (H) is FPT if and only if the class of allowed patterns H is matching splittable, which means that for some fixed B, every H ∈ H can be turned into a matching (a graph in which every vertex has degree at most 1) by removing at most B vertices. Assuming the randomised Exponential Time Hypothesis, we prove their conjecture for (I) all hereditary pattern classes H , and (II) all tree pattern classes, i.e., all classes H such that every H ∈ H is a tree. We also establish almost tight fine-grained upper and lower bounds for the case of hereditary patterns (I). [ABSTRACT FROM AUTHOR]

There is considerable interest in screening ultralarge chemical libraries for ligand discovery, both empirically and computationally1-4. Efforts have focused on readily synthesizable molecules, inevitably leaving many chemotypes unexplored. Here we investigate structure-based docking of a bespoke virtual library of tetrahydropyridines-a scaffold that is poorly sampled by a general billion-molecule virtual library but is well suited to many aminergic G-protein-coupled receptors. Using three inputs, each with diverse available derivatives, a one pot C-H alkenylation, electrocyclization and reduction provides the tetrahydropyridine core with up to six sites of derivatization5-7. Docking a virtual library of 75 million tetrahydropyridines against a model of the serotonin 5-HT2A receptor (5-HT2AR) led to the synthesis and testing of 17 initial molecules. Four of these molecules had low-micromolar activities against either the 5-HT2A or the 5-HT2B receptors. Structure-based optimization led to the 5-HT2AR agonists (R)-69 and (R)-70, with half-maximal effective concentration values of 41 nM and 110 nM, respectively, and unusual signalling kinetics that differ from psychedelic 5-HT2AR agonists. Cryo-electron microscopy structural analysis confirmed the predicted binding mode to 5-HT2AR. The favourable physical properties of these new agonists conferred high brain permeability, enabling mouse behavioural assays. Notably, neither had psychedelic activity, in contrast to classic 5-HT2AR agonists, whereas both had potent antidepressant activity in mouse models and had the same efficacy as antidepressants such as fluoxetine at as low as 1/40th of the dose. Prospects for using bespoke virtual libraries to sample pharmacologically relevant chemical space will be considered.

Exponential integrators are a well-known class of time integration methods that have been the subject of many studies and developments in the past two decades. Surprisingly, there have been limited efforts to analyze their stability and efficiency on non-diffusive equations to date. In this paper we apply linear stability analysis to showcase the poor stability properties of exponential integrators on non-diffusive problems. We then propose a simple repartitioning approach that stabilizes the integrators and enables the efficient solution of stiff, non-diffusive equations. To validate the effectiveness of our approach, we perform several numerical experiments that compare partitioned exponential integrators to unmodified ones. We also compare repartitioning to the well-known approach of adding hyperviscosity to the equation right-hand-side. Overall, we find that the repartitioning restores convergence at large timesteps and, unlike hyperviscosity, it does not require the use of high-order spatial derivatives.

In this paper, we consider a general notion of convolution. Let D be a finite domain and let D n be the set of n-length vectors (tuples) of D . Let f : D × D → D be a function and let ⊕ f be a coordinate-wise application of f. The f -Convolution of two functions g , h : D n → { - M , ... , M } is (g ⊛ f h) (v) : = ∑ v g , v h ∈ D n s.t. v = v g ⊕ f v h g (v g) · h (v h) for every v ∈ D n . This problem generalizes many fundamental convolutions such as Subset Convolution, XOR Product, Covering Product or Packing Product, etc. For arbitrary function f and domain D we can compute f -Convolution via brute-force enumeration in O ~ (| D | 2 n · polylog (M)) time. Our main result is an improvement over this naive algorithm. We show that f -Convolution can be computed exactly in O ~ ((c · | D | 2 ) n · polylog (M)) for constant c : = 3 / 4 when D has even cardinality. Our main observation is that a cyclic partition of a function f : D × D → D can be used to speed up the computation of f -Convolution, and we show that an appropriate cyclic partition exists for every f. Furthermore, we demonstrate that a single entry of the f -Convolution can be computed more efficiently. In this variant, we are given two functions g , h : D n → { - M , ... , M } alongside with a vector v ∈ D n and the task of the f -Query problem is to compute integer (g ⊛ f h) (v) . This is a generalization of the well-known Orthogonal Vectors problem. We show that f -Query can be computed in O ~ (| D | ω 2 n · polylog (M)) time, where ω ∈ [ 2 , 2.372) is the exponent of currently fastest matrix multiplication algorithm. [ABSTRACT FROM AUTHOR]

In a hierarchical clustering problem the task is to compute a series of mutually compatible clusterings of a finite metric space (P , dist) . Starting with the clustering where every point forms its own cluster, one iteratively merges two clusters until only one cluster remains. Complete linkage is a well-known and popular algorithm to compute such clusterings: in every step it merges the two clusters whose union has the smallest radius (or diameter) among all currently possible merges. We prove that the radius (or diameter) of every k-clustering computed by complete linkage is at most by factor O(k) (or O (k ln (3) / ln (2)) = O (k 1.59) ) worse than an optimal k-clustering minimizing the radius (or diameter). Furthermore we give a negative answer to the question proposed by Dasgupta and Long (J Comput Syst Sci 70(4):555–569, 2005. https://doi.org/10.1016/j.jcss.2004.10.006), who show a lower bound of Ω (log (k)) and ask if the approximation guarantee is in fact Θ (log (k)) . We present instances where complete linkage performs poorly in the sense that the k-clustering computed by complete linkage is off by a factor of Ω (k) from an optimal solution for radius and diameter. We conclude that in general metric spaces complete linkage does not perform asymptotically better than single linkage, merging the two clusters with smallest inter-cluster distance, for which we prove an approximation guarantee of O(k). [ABSTRACT FROM AUTHOR]

The Zeno effect occurs in quantum systems when a very strong measurement is applied, which can alter the dynamics in non-trivial ways. Despite being dissipative, the dynamics stay coherent within any degenerate subspaces of the measurement. Here we show that such a measurement can turn a single-qubit operation into a two- or multi-qubit entangling gate, even in a non-interacting system. We demonstrate this gate between two effectively non-interacting transmon qubits. Our Zeno gate works by imparting a geometric phase on the system, conditioned on it lying within a particular non-local subspace. These results show how universality can be generated not only by coherent interactions as is typically employed in quantum information platforms, but also by Zeno measurements.

Every generic linear functional (Formula presented.) on a convex polytope (Formula presented.) induces an orientation on the graph of (Formula presented.). From the resulting directed graph one can define a notion of (Formula presented.) -arborescence and (Formula presented.) -monotone path on (Formula presented.), as well as a natural graph structure on the vertex set of (Formula presented.) -monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of (Formula presented.) -arborescences, the number of (Formula presented.) -monotone paths, and the diameter of the graph of (Formula presented.) -monotone paths for polytopes (Formula presented.) in terms of their dimension and number of vertices or facets.

Hamiltonian simulation is one of the most important problems in quantum computation, and quantum singular value transformation (QSVT) is an efficient way to simulate a general class of Hamiltonians. However, the QSVT circuit typically involves multiple ancilla qubits and multi-qubit control gates. In order to simulate a certain class of n-qubit random Hamiltonians, we propose a drastically simplified quantum circuit that we refer to as the minimal QSVT circuit, which uses only one ancilla qubit and no multi-qubit controlled gates. We formulate a simple metric called the quantum unitary evolution score (QUES), which is a scalable quantum benchmark and can be verified without any need for classical computation. Under the globally depolarized noise model, we demonstrate that QUES is directly related to the circuit fidelity, and the potential classical hardness of an associated quantum circuit sampling problem. Under the same assumption, theoretical analysis suggests there exists an ‘optimal’ simulation time topt ≈ 4.81, at which even a noisy quantum device may be sufficient to demonstrate the potential classical hardness.

Understanding non-covalent biomolecular recognition, which includes drug-protein bound states and their binding/unbinding processes, is of fundamental importance in chemistry, biology, and medicine. Fully revealing the factors that govern the binding/unbinding processes can further assist in designing drugs with desired binding kinetics. HIV protease (HIVp) plays an integral role in the HIV life cycle, so it is a prime target for drug therapy. HIVp has flexible flaps, and the binding pocket can be accessible by a ligand via various pathways. Comparing ligand association and dissociation pathways can help elucidate the ligand-protein interactions such as key residues directly involved in the interaction or specific protein conformations that determine the binding of a ligand under certain pathway(s). Here, we investigated the ligand unbinding process for a slow binder, ritonavir, and a fast binder, xk263, by using unbiased all-atom accelerated molecular dynamics (aMD) simulation with a re-seeding approach and an explicit solvent model. Using ritonavir-HIVp and xk263-HIVp ligand-protein systems as cases, we sampled multiple unbinding pathways for each ligand and observed that the two ligands preferred the same unbinding route. However, ritonavir required a greater HIVp motion to dissociate as compared with xk263, which can leave the binding pocket with little conformational change of HIVp. We also observed that ritonavir unbinding pathways involved residues which are associated with drug resistance and are distal from catalytic site. Analyzing HIVp conformations sampled during both ligand-protein binding and unbinding processes revealed significantly more overlapping HIVp conformations for ritonavir-HIVp rather than xk263-HIVp. However, many HIVp conformations are unique in xk263-HIVp unbinding processes. The findings are consistent with previous findings that xk263 prefers an induced-fit model for binding and unbinding, whereas ritonavir favors a conformation selection model. This study deepens our understanding of the dynamic process of ligand unbinding and provides insights into ligand-protein recognition mechanisms and drug discovery.

We determined the effectiveness of absolute binding free energy (ABFE) calculations to refine the selection of active compounds in virtual compound screening, a setting where the more commonly used relative binding free energy approach is not readily applicable. To do this, we conducted baseline docking calculations of structurally diverse compounds in the DUD-E database for three targets, BACE1, CDK2 and thrombin, followed by ABFE calculations for compounds with high docking scores. The docking calculations alone achieved solid enrichment of active compounds over decoys. Encouragingly, the ABFE calculations then improved on this baseline. Analysis of the results emphasizes the importance of establishing high quality ligand poses as starting points for ABFE calculations, a nontrivial goal when processing a library of diverse compounds without informative co-crystal structures. Overall, our results suggest that ABFE calculations can play a valuable role in the drug discovery process.

Abstract: We show that for every integer$$m > 0$$m>0, there is an ordinary abelian variety over $${{\mathbb {F}}}_2$$F2that has exactlymrational points.

Influence Maximization (IM) is a classical combinatorial optimization problem, which can be widely used in mobile networks, social computing, and recommendation systems. It aims at selecting a small number of users such that maximizing the influence spread across the online social network. Because of its potential commercial and academic value, there are a lot of researchers focusing on studying the IM problem from different perspectives. The main challenge comes from the NP-hardness of the IM problem and #P-hardness of estimating the influence spread, thus traditional algorithms for overcoming them can be categorized into two classes: heuristic algorithms and approximation algorithms. However, there is no theoretical guarantee for heuristic algorithms, and the theoretical design is close to the limit. Therefore, it is almost impossible to further optimize and improve their performance. With the rapid development of artificial intelligence, technologies based on Machine Learning (ML) have achieved remarkable achievements in many fields. In view of this, in recent years, a number of new methods have emerged to solve combinatorial optimization problems by using ML-based techniques. These methods have the advantages of fast solving speed and strong generalization ability to unknown graphs, which provide a brand-new direction for solving combinatorial optimization problems. Therefore, we abandon the traditional algorithms based on iterative search and review the recent development of ML-based methods, especially Deep Reinforcement Learning, to solve the IM problem and other variants in social networks. We focus on summarizing the relevant background knowledge, basic principles, common methods, and applied research. Finally, the challenges that need to be solved urgently in future IM research are pointed out. [ABSTRACT FROM AUTHOR]

Many network applications can be formulated as NP-hard combinatorial optimization problems of community detection (CD) that partitions nodes of a graph into several groups with dense linkage. Most existing CD methods are transductive, which independently optimized their models for each single graph, and can only ensure either high quality or efficiency of CD by respectively using advanced machine learning techniques or fast heuristic approximation. In this study, we consider the CD task and aims to alleviate its NP-hard challenge. Motivated by the efficient inductive inference of graph neural networks (GNNs), we explore the possibility to achieve a better tradeoff between the quality and efficiency of CD via an inductive embedding scheme across multiple graphs of a system and propose a novel inductive community detection (ICD) method. Concretely, ICD first conducts the offline training of an adversarial dual GNN structure on historical graphs to capture key properties of a system. The trained model is then directly generalized to new graphs of the same system for online CD without additional optimization, where a better tradeoff between quality and efficiency can be achieved. Compared with existing inductive approaches, we develop a novel feature extraction module based on graph coarsening, which can efficiently extract informative feature inputs for GNNs. Moreover, our original designs of adversarial dual GNN and clustering regularization loss further enable ICD to capture permutation-invariant community labels in the offline training and help derive community-preserved embedding to support the high-quality online CD. Experiments on a set of benchmarks demonstrate that ICD can achieve a significant tradeoff between quality and efficiency over various baselines. [ABSTRACT FROM AUTHOR]

A constant locality function is one in which each output bit depends on just a constant number of input bits. Viola and Wigderson (2018) gave an explicit construction of bipartite degree-3 Ramanujan graphs such that each neighbor of a vertex can be computed using a constant locality function. In this work, we construct the first explicit local Ramanujan graph (bipartite) of degree q + 1, where q > 2 is any prime power. Alon and Capalbo (2002) used 4-regular, 8-regular and 44-regular Ramanujan graphs to construct unique-neighbor expanders that were 3-regular, 4-regular, 6-regular and `bipartite' (respectively). Viola and Wigderson (2018) had asked if a local construction of such unique-neighbor expanders exists. Our construction gives local 4-regular, 8-regular and 44-regular Ramanujan graphs, which also solves the corresponding open problem of the construction of local unique-neighbor expanders. The only known explicit construction of Ramanujan graphs exists for degree q + 1, where q is a prime-power. In this paper, we essentially localize the explicit Ramanujan graphs for all these degrees. Our results use the explicit Ramanujan graphs by Morgenstern (1994) and a significant generalization of the ideas used in Viola and Wigderson (2018). [ABSTRACT FROM AUTHOR]