LIVIVO - Search results -

Search results

Result 1 - 10 of total 51

Search options

Thesis ; Online: Quantum Algorithms for Machine Learning and Optimization

Li, Tongyang

2020

Abstract: The theories of optimization and machine learning answer foundational questions in computer science and lead to new algorithms for practical applications. While these topics have been extensively studied in the context of classical computing, their ... ...

Abstract	The theories of optimization and machine learning answer foundational questions in computer science and lead to new algorithms for practical applications. While these topics have been extensively studied in the context of classical computing, their quantum counterparts are far from well-understood. In this thesis, we explore algorithms that bridge the gap between the fields of quantum computing and machine learning. First, we consider general optimization problems with only function evaluations. For two core problems, namely general convex optimization and volume estimation of convex bodies, we give quantum algorithms as well as quantum lower bounds that constitute the quantum speedups of both problems to be polynomial compared to their classical counterparts. We then consider machine learning and optimization problems with input data stored explicitly as matrices. We first look at semidefinite programs and provide quantum algorithms with polynomial speedup compared to the classical state-of-the-art. We then move to machine learning and give the optimal quantum algorithms for linear and kernel-based classifications. To complement with our quantum algorithms, we also introduce a framework for quantum-inspired classical algorithms, showing that for low-rank matrix arithmetics there can only be polynomial quantum speedup. Finally, we study statistical problems on quantum computers, with the focus on testing properties of probability distributions. We show that for testing various properties including ℓ1-distance, ℓ2-distance, Shannon and Renyi entropies, etc., there are polynomial quantum speedups compared to their classical counterparts. We also extend these results to testing properties of quantum states.
Keywords	Computer science\|Quantum physics
Subject code	510
Language	ENG
Publishing date	2020-01-01 00:00:01.0
Publisher	University of Maryland, College Park
Publishing country	us
Document type	Thesis ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Article ; Online: ATP and nucleic acids competitively modulate LLPS of the SARS-CoV2 nucleocapsid protein.

Dang, Mei / Li, Tongyang / Song, Jianxing

Communications biology

2023 Volume 6, Issue 1, Page(s) 80

Abstract: SARS-CoV-2 nucleocapsid (N) protein with very low mutation rates is the only structural protein which not only functions to package viral genomic RNA, but also manipulates host-cell machineries, thus representing a key target for drug development. Recent ...

Abstract	SARS-CoV-2 nucleocapsid (N) protein with very low mutation rates is the only structural protein which not only functions to package viral genomic RNA, but also manipulates host-cell machineries, thus representing a key target for drug development. Recent discovery of its liquid-liquid phase separation (LLPS) opens up a new direction for developing anti-SARS-CoV-2 strategies/drugs. However, so far the high-resolution mechanism of its LLPS still remains unknown. Here by DIC and NMR characterization, we have demonstrated: 1) nucleic acids modulate LLPS by dynamic and multivalent interactions over both folded NTD/CTD and Arg/Lys residues within IDRs; 2) ATP with concentrations > mM in all living cells but absent in viruses not only binds NTD/CTD, but also Arg residues within IDRs with a Kd of 2.8 mM; and 3) ATP dissolves nucleic-acid-induced LLPS by competitively displacing nucleic acid from binding the protein. Our study deciphers that the essential binding of N protein with nucleic acid and its LLPS are targetable by small molecules including ATP, which is emerging as a cellular factor controlling the host-SARS-CoV-2 interaction. Fundamentally, our results imply that the mechanisms of LLPS of IDR-containing proteins mediated by ATP and nucleic acids appear to be highly conserved from human to virus.
MeSH term(s)	Humans ; Nucleocapsid Proteins/chemistry ; RNA, Viral/genetics ; RNA, Viral/metabolism ; Nucleic Acids ; SARS-CoV-2/genetics ; SARS-CoV-2/metabolism ; COVID-19 ; Adenosine Triphosphate
Chemical Substances	Nucleocapsid Proteins ; RNA, Viral ; Nucleic Acids ; Adenosine Triphosphate (8L70Q75FXE)
Language	English
Publishing date	2023-01-21
Publishing country	England
Document type	Journal Article ; Research Support, Non-U.S. Gov't
ISSN	2399-3642
ISSN (online)	2399-3642
DOI	10.1038/s42003-023-04480-3
Database	MEDical Literature Analysis and Retrieval System OnLINE

Order via subito

This service is chargeable due to the Delivery terms set by subito. Orders including an article and supplementary material will be classified as separate orders. In these cases, fees will be demanded for each order.

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems

Zuo, Qian / Li, Tongyang

2023

Abstract: We propose fast and practical quantum-inspired classical algorithms for solving linear systems. Specifically, given sampling and query access to a matrix $A\in\mathbb{R}^{m\times n}$ and a vector $b\in\mathbb{R}^m$, we propose classical algorithms that ... ...

Abstract	We propose fast and practical quantum-inspired classical algorithms for solving linear systems. Specifically, given sampling and query access to a matrix $A\in\mathbb{R}^{m\times n}$ and a vector $b\in\mathbb{R}^m$, we propose classical algorithms that produce a data structure for the solution $x\in\mathbb{R}^{n}$ of the linear system $Ax=b$ with the ability to sample and query its entries. The resulting $x$ satisfies $\\|x-A^{+}b\\|\leq\epsilon\\|A^{+}b\\|$, where $\\|\cdot\\|$ is the spectral norm and $A^+$ is the Moore-Penrose inverse of $A$. Our algorithm has time complexity $\widetilde{O}(\kappa_F^4/\kappa\epsilon^2)$ in the general case, where $\kappa_{F} =\\|A\\|_F\\|A^+\\|$ and $\kappa=\\|A\\|\\|A^+\\|$ are condition numbers. Compared to the prior state-of-the-art result [Shao and Montanaro, arXiv:2103.10309v2], our algorithm achieves a polynomial speedup in condition numbers. When $A$ is $s$-sparse, our algorithm has complexity $\widetilde{O}(s \kappa\log(1/\epsilon))$, matching the quantum lower bound for solving linear systems in $\kappa$ and $1/\epsilon$ up to poly-logarithmic factors [Harrow and Kothari]. When $A$ is $s$-sparse and symmetric positive-definite, our algorithm has complexity $\widetilde{O}(s\sqrt{\kappa}\log(1/\epsilon))$. Technically, our main contribution is the application of the heavy ball momentum method to quantum-inspired classical algorithms for solving linear systems, where we propose two new methods with speedups: quantum-inspired Kaczmarz method with momentum and quantum-inspired coordinate descent method with momentum. Their analysis exploits careful decomposition of the momentum transition matrix and the application of novel spectral norm concentration bounds for independent random matrices. Finally, we also conduct numerical experiments for our algorithms on both synthetic and real-world datasets, and the experimental results support our theoretical claims. Comment: Theorem 3 and Theorem 5 are incorrect, and more efforts are needed to fix existing issues
Keywords	Computer Science - Data Structures and Algorithms ; Computer Science - Computational Complexity ; Mathematics - Numerical Analysis ; Quantum Physics
Subject code	518
Publishing date	2023-07-13
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Article ; Online: Arg/Lys-containing IDRs are cryptic binding domains for ATP and nucleic acids that interplay to modulate LLPS.

Dang, Mei / Li, Tongyang / Zhou, Shibo / Song, Jianxing

Communications biology

2022 Volume 5, Issue 1, Page(s) 1315

Abstract: Most membrane-less organelles (MLOs) formed by LLPS contain both nucleic acids and IDR-rich proteins. Currently while IDRs are well-recognized to drive LLPS, nucleic acids are thought to exert non-specific electrostatic/salt effects. TDP-43 functions by ... ...

Abstract	Most membrane-less organelles (MLOs) formed by LLPS contain both nucleic acids and IDR-rich proteins. Currently while IDRs are well-recognized to drive LLPS, nucleic acids are thought to exert non-specific electrostatic/salt effects. TDP-43 functions by binding RNA/ssDNA and its LLPS was characterized without nucleic acids to be driven mainly by PLD-oligomerization, which may further transit into aggregation characteristic of various neurodegenerative diseases. Here by NMR, we discovered unexpectedly for TDP-43 PLD: 1) ssDNAs drive and then dissolve LLPS by multivalently and specifically binding Arg/Lys. 2) LLPS is driven by nucleic-acid-binding coupled with PLD-oligomerization. 3) ATP and nucleic acids universally interplay in modulating LLPS by competing for binding Arg/Lys. However, the unique hydrophobic region within PLD renders LLPS to exaggerate into aggregation. The study not only unveils the first residue-resolution mechanism of the nucleic-acid-driven LLPS of TDP-43 PLD, but also decodes a general principle that not just TDP-43 PLD, all Arg/Lys-containing IDRs are cryptic nucleic-acid-binding domains that may phase separate upon binding nucleic acids. Strikingly, ATP shares a common mechanism with nucleic acids in binding IDRs, thus emerging as a universal mediator for interactions between IDRs and nucleic acids, which may underlie previously-unrecognized roles of ATP at mM in physiology and pathology.
MeSH term(s)	Nucleic Acids ; RNA ; DNA, Single-Stranded ; DNA-Binding Proteins ; Adenosine Triphosphate
Chemical Substances	Nucleic Acids ; RNA (63231-63-0) ; DNA, Single-Stranded ; DNA-Binding Proteins ; Adenosine Triphosphate (8L70Q75FXE)
Language	English
Publishing date	2022-12-01
Publishing country	England
Document type	Journal Article ; Research Support, Non-U.S. Gov't
ISSN	2399-3642
ISSN (online)	2399-3642
DOI	10.1038/s42003-022-04293-w
Database	MEDical Literature Analysis and Retrieval System OnLINE

Order via subito

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions

Zhang, Chenyi / Li, Tongyang

2022

Abstract: Quantum algorithms for optimization problems are of general interest. Despite recent progress in classical lower bounds for nonconvex optimization under different settings and quantum lower bounds for convex optimization, quantum lower bounds for ... ...

Abstract	Quantum algorithms for optimization problems are of general interest. Despite recent progress in classical lower bounds for nonconvex optimization under different settings and quantum lower bounds for convex optimization, quantum lower bounds for nonconvex optimization are still widely open. In this paper, we conduct a systematic study of quantum query lower bounds on finding $\epsilon$-approximate stationary points of nonconvex functions, and we consider the following two important settings: 1) having access to $p$-th order derivatives; or 2) having access to stochastic gradients. The classical query lower bounds is $\Omega\big(\epsilon^{-\frac{1+p}{p}}\big)$ regarding the first setting, and $\Omega(\epsilon^{-4})$ regarding the second setting (or $\Omega(\epsilon^{-3})$ if the stochastic gradient function is mean-squared smooth). In this paper, we extend all these classical lower bounds to the quantum setting. They match the classical algorithmic results respectively, demonstrating that there is no quantum speedup for finding $\epsilon$-stationary points of nonconvex functions with $p$-th order derivative inputs or stochastic gradient inputs, whether with or without the mean-squared smoothness assumption. Technically, our quantum lower bounds are obtained by showing that the sequential nature of classical hard instances in all these settings also applies to quantum queries, preventing any quantum speedup other than revealing information of the stationary points sequentially. Comment: 32 pages, 0 figures. To appear in the Fortieth International Conference on Machine Learning (ICML 2023)
Keywords	Quantum Physics ; Computer Science - Data Structures and Algorithms
Subject code	005
Publishing date	2022-12-07
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games

Gao, Minbo / Ji, Zhengfeng / Li, Tongyang / Wang, Qisheng

2023

Abstract: We propose the first online quantum algorithm for zero-sum games with $\tilde O(1)$ regret under the game setting. Moreover, our quantum algorithm computes an $\varepsilon$-approximate Nash equilibrium of an $m \times n$ matrix zero-sum game in quantum ... ...

Abstract	We propose the first online quantum algorithm for zero-sum games with $\tilde O(1)$ regret under the game setting. Moreover, our quantum algorithm computes an $\varepsilon$-approximate Nash equilibrium of an $m \times n$ matrix zero-sum game in quantum time $\tilde O(\sqrt{m+n}/\varepsilon^{2.5})$, yielding a quadratic improvement over classical algorithms in terms of $m, n$. Our algorithm uses standard quantum inputs and generates classical outputs with succinct descriptions, facilitating end-to-end applications. As an application, we obtain a fast quantum linear programming solver. Technically, our online quantum algorithm "quantizes" classical algorithms based on the optimistic multiplicative weight update method. At the heart of our algorithm is a fast quantum multi-sampling procedure for the Gibbs sampling problem, which may be of independent interest.
Keywords	Quantum Physics ; Computer Science - Machine Learning ; Mathematics - Optimization and Control
Subject code	000
Publishing date	2023-04-27
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: A Theory of Digital Quantum Simulations in the Low-Energy Subspace

Gong, Weiyuan / Zhou, Shuo / Li, Tongyang

2023

Abstract: Digital quantum simulation has broad applications in approximating unitary evolutions of Hamiltonians. In practice, many simulation tasks for quantum systems focus on quantum states in the low-energy subspace instead of the entire Hilbert space. In this ... ...

Abstract	Digital quantum simulation has broad applications in approximating unitary evolutions of Hamiltonians. In practice, many simulation tasks for quantum systems focus on quantum states in the low-energy subspace instead of the entire Hilbert space. In this paper, we systematically investigate the complexity of digital quantum simulation based on product formulas in the low-energy subspace. We show that the simulation error depends on the effective low-energy norm of the Hamiltonian for a variety of digital quantum simulation algorithms and quantum systems, allowing improvements over the previous complexities for full unitary simulations even for imperfect state preparations. In particular, for simulating spin models in the low-energy subspace, we prove that randomized product formulas such as qDRIFT and random permutation require smaller step complexities. This improvement also persists in symmetry-protected digital quantum simulations. We prove a similar improvement in simulating the dynamics of power-law quantum interactions. We also provide a query lower bound for general digital quantum simulations in the low-energy subspace. Comment: 32 pages, 4 figures, github repo: https://github.com/Qubit-Fernand/Digital-Quantum-Simulation
Keywords	Quantum Physics ; Computer Science - Data Structures and Algorithms
Subject code	541
Publishing date	2023-12-14
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret

Zhong, Han / Hu, Jiachen / Xue, Yecheng / Li, Tongyang / Wang, Liwei

2023

Abstract: While quantum reinforcement learning (RL) has attracted a surge of attention recently, its theoretical understanding is limited. In particular, it remains elusive how to design provably efficient quantum RL algorithms that can address the exploration- ... ...

Abstract	While quantum reinforcement learning (RL) has attracted a surge of attention recently, its theoretical understanding is limited. In particular, it remains elusive how to design provably efficient quantum RL algorithms that can address the exploration-exploitation trade-off. To this end, we propose a novel UCRL-style algorithm that takes advantage of quantum computing for tabular Markov decision processes (MDPs) with $S$ states, $A$ actions, and horizon $H$, and establish an $\mathcal{O}(\mathrm{poly}(S, A, H, \log T))$ worst-case regret for it, where $T$ is the number of episodes. Furthermore, we extend our results to quantum RL with linear function approximation, which is capable of handling problems with large state spaces. Specifically, we develop a quantum algorithm based on value target regression (VTR) for linear mixture MDPs with $d$-dimensional linear representation and prove that it enjoys $\mathcal{O}(\mathrm{poly}(d, H, \log T))$ regret. Our algorithms are variants of UCRL/UCRL-VTR algorithms in classical RL, which also leverage a novel combination of lazy updating mechanisms and quantum estimation subroutines. This is the key to breaking the $\Omega(\sqrt{T})$-regret barrier in classical RL. To the best of our knowledge, this is the first work studying the online exploration in quantum RL with provable logarithmic worst-case regret.
Keywords	Quantum Physics ; Computer Science - Artificial Intelligence ; Computer Science - Machine Learning ; Statistics - Machine Learning
Subject code	005
Publishing date	2023-02-21
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Near-Optimal Quantum Coreset Construction Algorithms for Clustering

Xue, Yecheng / Chen, Xiaoyu / Li, Tongyang / Jiang, Shaofeng H. -C.

2023

Abstract: k$-Clustering in $\mathbb{R}^d$ (e.g., $k$-median and $k$-means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the classical setting for a dataset with cardinality $n$, it remains open to find ... ...

Abstract	$k$-Clustering in $\mathbb{R}^d$ (e.g., $k$-median and $k$-means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the classical setting for a dataset with cardinality $n$, it remains open to find sublinear-time quantum algorithms. We give quantum algorithms that find coresets for $k$-clustering in $\mathbb{R}^d$ with $\tilde{O}(\sqrt{nk}d^{3/2})$ query complexity. Our coreset reduces the input size from $n$ to $\mathrm{poly}(k\epsilon^{-1}d)$, so that existing $\alpha$-approximation algorithms for clustering can run on top of it and yield $(1 + \epsilon)\alpha$-approximation. This eventually yields a quadratic speedup for various $k$-clustering approximation algorithms. We complement our algorithm with a nearly matching lower bound, that any quantum algorithm must make $\Omega(\sqrt{nk})$ queries in order to achieve even $O(1)$-approximation for $k$-clustering. Comment: Comments: 32 pages, 0 figures, 1 table. To appear in the Fortieth International Conference on Machine Learning (ICML 2023)
Keywords	Quantum Physics ; Computer Science - Artificial Intelligence ; Computer Science - Data Structures and Algorithms ; Computer Science - Machine Learning ; Statistics - Machine Learning
Subject code	006
Publishing date	2023-06-05
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Quantum Langevin Dynamics for Optimization

Chen, Zherui / Lu, Yuchen / Wang, Hao / Liu, Yizhou / Li, Tongyang

2023

Abstract: We initiate the study of utilizing Quantum Langevin Dynamics (QLD) to solve optimization problems, particularly those non-convex objective functions that present substantial obstacles for traditional gradient descent algorithms. Specifically, we examine ... ...

Abstract	We initiate the study of utilizing Quantum Langevin Dynamics (QLD) to solve optimization problems, particularly those non-convex objective functions that present substantial obstacles for traditional gradient descent algorithms. Specifically, we examine the dynamics of a system coupled with an infinite heat bath. This interaction induces both random quantum noise and a deterministic damping effect to the system, which nudge the system towards a steady state that hovers near the global minimum of objective functions. We theoretically prove the convergence of QLD in convex landscapes, demonstrating that the average energy of the system can approach zero in the low temperature limit with an exponential decay rate correlated with the evolution time. Numerically, we first show the energy dissipation capability of QLD by retracing its origins to spontaneous emission. Furthermore, we conduct detailed discussion of the impact of each parameter. Finally, based on the observations when comparing QLD with classical Fokker-Plank-Smoluchowski equation, we propose a time-dependent QLD by making temperature and $\hbar$ time-dependent parameters, which can be theoretically proven to converge better than the time-independent case and also outperforms a series of state-of-the-art quantum and classical optimization algorithms in many non-convex landscapes. Comment: 33 pages, 1 table, 26 figures
Keywords	Quantum Physics ; Computer Science - Data Structures and Algorithms ; Computer Science - Machine Learning ; Mathematics - Optimization and Control
Subject code	541
Publishing date	2023-11-27
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

To top

Full text online

More links

Kategorien

Inter-library loan at ZB MED

More links

Kategorien

Order via subito

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

More links

Kategorien

Order via subito

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED