Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

The complexity of NISQ.

ABSTRACT: The recent proliferation of NISQ devices has made it imperative to understand their power. In this work, we define and study the complexity class NISQ, which encapsulates problems that can be efficiently solved by a classical computer with access to noisy quantum circuits. We establish super-polynomial separations in the complexity among classical computation, NISQ, and fault-tolerant quantum computation to solve some problems based on modifications of Simon's problems. We then consider the power of NISQ for three well-studied problems. For unstructured search, we prove that NISQ cannot achieve a Grover-like quadratic speedup over classical computers. For the Bernstein-Vazirani problem, we show that NISQ only needs a number of queries logarithmic in what is required for classical computers. Finally, for a quantum state learning problem, we prove that NISQ is exponentially weaker than classical computers with access to noiseless constant-depth quantum circuits.

SUBMITTER: Chen S

PROVIDER: S-EPMC10522708 | biostudies-literature | 2023 Sep

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

The complexity of NISQ.

Chen Sitan S Cotler Jordan J Huang Hsin-Yuan HY Li Jerry J

Nature communications 20230926 1

The recent proliferation of NISQ devices has made it imperative to understand their power. In this work, we define and study the complexity class NISQ, which encapsulates problems that can be efficiently solved by a classical computer with access to noisy quantum circuits. We establish super-polynomial separations in the complexity among classical computation, NISQ, and fault-tolerant quantum computation to solve some problems based on modifications of Simon's problems. We then consider the powe ...[more]

PMID: 37752125

Similar Datasets

Quantum Annealing in the NISQ Era: Railway Conflict Management.

Project description:We are in the noisy intermediate-scale quantum (NISQ) devices' era, in which quantum hardware has become available for application in real-world problems. However, demonstrations of the usefulness of such NISQ devices are still rare. In this work, we consider a practical railway dispatching problem: delay and conflict management on single-track railway lines. We examine the train dispatching consequences of the arrival of an already delayed train to a given network segment. This problem is computationally hard and needs to be solved almost in real time. We introduce a quadratic unconstrained binary optimization (QUBO) model of this problem, which is compatible with the emerging quantum annealing technology. The model's instances can be executed on present-day quantum annealers. As a proof-of-concept, we solve selected real-life problems from the Polish railway network using D-Wave quantum annealers. As a reference, we also provide solutions calculated with classical methods, including the conventional solution of a linear integer version of the model as well as the solution of the QUBO model using a tensor network-based algorithm. Our preliminary results illustrate the degree of difficulty of real-life railway instances for the current quantum annealing technology. Moreover, our analysis shows that the new generation of quantum annealers (the advantage system) does not perform well on those instances, either.

| S-EPMC9955039 | biostudies-literature

Quantum CNOT Circuits Synthesis for NISQ Architectures Using the Syndrome Decoding Problem

Project description:Current proposals for quantum compilers involve the synthesis and optimization of linear reversible circuits and among them CNOT circuits. This class of circuits represents a significant part of the cost of running an entire quantum circuit and therefore we aim at reducing the size of CNOT circuits. In this paper we present a new algorithm for the synthesis of CNOT circuits based on the solution of the syndrome decoding problem. Our method addresses the case of ideal hardware with an all-to-all qubit connectivity and the case of near-term quantum devices with restricted connectivity. Benchmarks show that our algorithm outperforms existing algorithms in both cases of partial and full connectivity.

| S-EPMC7345310 | biostudies-literature

Exact Non-Markovian Quantum Dynamics on the NISQ Device Using Kraus Operators.

Project description:The theory of open quantum systems has many applications ranging from simulating quantum dynamics in condensed phases to better understanding quantum-enabled technologies. At the center of theoretical chemistry are the developments of methodologies and computational tools for simulating charge and excitation energy transfer in solutions, biomolecules, and molecular aggregates. As a variety of these processes display non-Markovian behavior, classical computer simulation can be challenging due to exponential scaling with existing methods. With quantum computers holding the promise of efficient quantum simulations, in this paper, we present a new quantum algorithm based on Kraus operators that capture the exact non-Markovian effect at a finite temperature. The implementation of the Kraus operators on the quantum machine uses a combination of singular value decomposition (SVD) and optimal Walsh operators that result in shallow circuits. We demonstrate the feasibility of the algorithm by simulating the spin-boson dynamics and the exciton transfer in the Fenna-Matthews-Olson (FMO) complex. The NISQ results show very good agreement with the exact ones.

| S-EPMC10906042 | biostudies-literature

Towards the simulation of large scale protein-ligand interactions on NISQ-era quantum computers.

Project description:We explore the use of symmetry-adapted perturbation theory (SAPT) as a simple and efficient means to compute interaction energies between large molecular systems with a hybrid method combining NISQ-era quantum and classical computers. From the one- and two-particle reduced density matrices of the monomer wavefunctions obtained by the variational quantum eigensolver (VQE), we compute SAPT contributions to the interaction energy [SAPT(VQE)]. At first order, this energy yields the electrostatic and exchange contributions for non-covalently bound systems. We empirically find from ideal statevector simulations that the SAPT(VQE) interaction energy components display orders of magnitude lower absolute errors than the corresponding VQE total energies. Therefore, even with coarsely optimized low-depth VQE wavefunctions, we still obtain sub kcal mol-1 accuracy in the SAPT interaction energies. In SAPT(VQE), the quantum requirements, such as qubit count and circuit depth, are lowered by performing computations on the separate molecular systems. Furthermore, active spaces allow for large systems containing thousands of orbitals to be reduced to a small enough orbital set to perform the quantum portions of the computations. We benchmark SAPT(VQE) (with the VQE component simulated by ideal statevector simulators) against a handful of small multi-reference dimer systems and the iron center containing human cancer-relevant protein lysine-specific demethylase 5 (KDM5A).

| S-EPMC8926290 | biostudies-literature

Complete Active Space Methods for NISQ Devices: The Importance of Canonical Orbital Optimization for Accuracy and Noise Resilience.

Project description:To avoid the scaling of the number of qubits with the size of the basis set, one can divide the molecular space into active and inactive regions, which is also known as complete active space methods. However, selecting the active space alone is not enough to accurately describe quantum mechanical effects such as correlation. This study emphasizes the importance of optimizing the active space orbitals to describe correlation and improve the basis-dependent Hartree-Fock energies. We will explore classical and quantum computation methods for orbital optimization and compare the chemically inspired ansatz, UCCSD, with the classical full CI approach for describing the active space in both weakly and strongly correlated molecules. Finally, we will investigate the practical implementation of a quantum CASSCF, where hardware-efficient circuits must be used and noise can interfere with accuracy and convergence. Additionally, we will examine the impact of using canonical and noncanonical active orbitals on the convergence of the quantum CASSCF routine in the presence of noise.

| S-EPMC10210242 | biostudies-literature

Reduced complexity

Project description:Identification of RCO targets using ChIP-seq

| PRJEB29759 | ENA

Genetic complexity traits

Project description:The hidden complexity of Mendelian traits across yeast natural populations

| PRJEB11500 | ENA

Disentangling the complexity of low complexity proteins.

Project description:There are multiple definitions for low complexity regions (LCRs) in protein sequences, with all of them broadly considering LCRs as regions with fewer amino acid types compared to an average composition. Following this view, LCRs can also be defined as regions showing composition bias. In this critical review, we focus on the definition of sequence complexity of LCRs and their connection with structure. We present statistics and methodological approaches that measure low complexity (LC) and related sequence properties. Composition bias is often associated with LC and disorder, but repeats, while compositionally biased, might also induce ordered structures. We illustrate this dichotomy, and more generally the overlaps between different properties related to LCRs, using examples. We argue that statistical measures alone cannot capture all structural aspects of LCRs and recommend the combined usage of a variety of predictive tools and measurements. While the methodologies available to study LCRs are already very advanced, we foresee that a more comprehensive annotation of sequences in the databases will enable the improvement of predictions and a better understanding of the evolution and the connection between structure and function of LCRs. This will require the use of standards for the generation and exchange of data describing all aspects of LCRs.Short abstractThere are multiple definitions for low complexity regions (LCRs) in protein sequences. In this critical review, we focus on the definition of sequence complexity of LCRs and their connection with structure. We present statistics and methodological approaches that measure low complexity (LC) and related sequence properties. Composition bias is often associated with LC and disorder, but repeats, while compositionally biased, might also induce ordered structures. We illustrate this dichotomy, plus overlaps between different properties related to LCRs, using examples.

| S-EPMC7299295 | biostudies-literature

The Impact of Patient Complexity on Healthcare Utilization

Project description:Healthcare providers are routinely being assessed for metrics designed to assess the quality of the care they deliver. There is growing consensus that these measurements, which typically assess the percentage of patients meeting a specific standard of care, should be adjusted for the clinical complexity of the providers. This study will assess whether adjusting for the social complexity of the patient panel adds significantly to adjustment for clinical complexity in explaining apparent differences in quality of care provided by Primary care providers and clinics.

| 2257794 | ecrin-mdr-crc

Patient complexity: more than comorbidity. the vector model of complexity.

Project description:The conceptualization of patient complexity is just beginning in clinical medicine.This study aims (1) to propose a conceptual approach to complex patients; (2) to demonstrate how this approach promotes achieving congruence between patient and provider, a critical step in the development of maximally effective treatment plans; and (3) to examine availability of evidence to guide trade-off decisions and assess healthcare quality for complex patients.The Vector Model of Complexity portrays interactions between biological, socioeconomic, cultural, environmental and behavioral forces as health determinants. These forces are not easily discerned but exert profound influences on processes and outcomes of care for chronic medical conditions. Achieving congruence between patient, physician, and healthcare system is essential for effective, patient-centered care; requires assessment of all axes of the Vector Model; and, frequently, requires trade-off decisions to develop a tailored treatment plan. Most evidence-based guidelines rarely provide guidance for trade-off decisions. Quality measures often exclude complex patients and are not designed explicitly to assess their overall healthcare.We urgently need to expand the evidence base to inform the care of complex patients of all kinds, especially for the clinical trade-off decisions that are central to tailoring care. We offer long- and short-term strategies to begin to incorporate complexity into quality measurement and performance profiling, guided by the Vector Model. Interdisciplinary research should lay the foundation for a deeper understanding of the multiple sources of patient complexity and their interactions, and how provision of healthcare should be harmonized with complexity to optimize health.

| S-EPMC2219701 | biostudies-other

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data