Related papers: What is computable and non-computable in the quantum domain: 7 statements and 3 conjectures

What is computable and non-computable in the quantum domain: 7 statements and 3 conjectures

URL: http://arxiv.org/abs/2403.16881v1
Date: Mon, 25 Mar 2024 15:47:35 GMT
Title: What is computable and non-computable in the quantum domain: 7 statements and 3 conjectures
Authors: Aleksey K. Fedorov, Evgeniy O. Kiktenko,
Abstract summary: There is no universal approach that helps to define a scope of problems that quantum computers are able to speed up. On the one hand, the class of quantum states that is of interest for quantum computing should be complex. On the other hand, such quantum states should be reachable on a practical quantum computer.
Score: 0.7892577704654171
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Recent progress in developing computational devices based on quantum effects and demonstrations of solving various tasks using them has actualized the question of the origin of the quantum advantage. Although various attempts to quantify and characterize the nature of quantum computational advantage have been made, this question in the general context remains open: There is no universal approach that helps to define a scope of problems that quantum computers are able to speed up, theoretically and in practice. Here we review an approach to this question based on the concept of complexity and reachability of quantum states. On the one hand, the class of quantum states that is of interest for quantum computing should be complex, i.e. non-simulatable with classical computers with less than exponential resources. On the other hand, such quantum states should be reachable on a practical quantum computer. This means that a unitary corresponding to the transformation of quantum states from initial to desired can be decomposed in a sequence of single- and two-qubit gates with of no more than polynomial in the number of qubits. Our consideration paves the way towards understanding the scope of problems that can be solved by a quantum computer by formulating a sequence of statements and conjectures on various sets of quantum states.

Related papers

Fourier space readout method for efficiently recovering functions encoded in quantum states [0.0]
We propose a quantum-classical hybrid Fourier space readout (FSR) method to efficiently recover the underlying function from its corresponding quantum state.<n>In particular, the complexity on quantum computers has only a logarithmic dependence on the grid number, while the complexity on classical computers has a linear dependence on the number of target points instead of the grid number.
arXiv Detail & Related papers (2025-07-28T08:10:48Z)
Quantum Computing in Transport Science: A Review [0.8437187555622164]
Quantum computing, leveraging the principles of quantum mechanics, has been found to significantly enhance computational capabilities in principle. This paper explores quantum computing's potential to address complex, large-scale problems in transportation systems.
arXiv Detail & Related papers (2025-03-27T09:28:33Z)
Quantum Computer Does Not Need Coherent Quantum Access for Advantage [0.0]
A majority of quantum speedups rely on a subroutine in which classical information can be accessed in a coherent quantum manner. We develop a quantum gradient descent algorithm for optimization, which is a fundamental technique that enjoys a wide range of applications.
arXiv Detail & Related papers (2025-03-04T11:24:28Z)
Resource analysis of quantum algorithms for coarse-grained protein folding models [0.0]
We analyze the resource requirements for simulating protein folding on a quantum computer. We calculate the minimum number of qubits, interactions, and two-qubit gates necessary to build a quantum algorithm.
arXiv Detail & Related papers (2023-11-07T18:27:44Z)
Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
arXiv Detail & Related papers (2023-10-04T17:53:55Z)
A Practitioner's Guide to Quantum Algorithms for Optimisation Problems [0.0]
NP-hard optimisation problems are common in industrial areas such as logistics and finance. This paper aims to provide a comprehensive overview of the theory of quantum optimisation techniques. It focuses on their near-term potential for noisy intermediate scale quantum devices.
arXiv Detail & Related papers (2023-05-12T08:57:36Z)
Quantum Machine Learning: from physics to software engineering [58.720142291102135]
We show how classical machine learning approach can help improve the facilities of quantum computers. We discuss how quantum algorithms and quantum computers may be useful for solving classical machine learning tasks.
arXiv Detail & Related papers (2023-01-04T23:37:45Z)
Optimal Stochastic Resource Allocation for Distributed Quantum Computing [50.809738453571015]
We propose a resource allocation scheme for distributed quantum computing (DQC) based on programming to minimize the total deployment cost for quantum resources. The evaluation demonstrates the effectiveness and ability of the proposed scheme to balance the utilization of quantum computers and on-demand quantum computers.
arXiv Detail & Related papers (2022-09-16T02:37:32Z)
The Basics of Quantum Computing for Chemists [0.0]
We review and illustrate the basic aspects of quantum information and their relation to quantum computing. We discuss the current landscape when of relevance to quantum chemical simulations in quantum computers.
arXiv Detail & Related papers (2022-03-28T20:10:00Z)
Efficient criteria of quantumness for a large system of qubits [58.720142291102135]
We discuss the dimensionless combinations of basic parameters of large, partially quantum coherent systems. Based on analytical and numerical calculations, we suggest one such number for a system of qubits undergoing adiabatic evolution.
arXiv Detail & Related papers (2021-08-30T23:50:05Z)
Numerical hardware-efficient variational quantum simulation of a soliton solution [0.0]
We discuss the capabilities of quantum algorithms with special attention paid to a hardware-efficient variational eigensolver. A delicate interplay between magnetic interactions allows one to stabilize a chiral state that destroys the homogeneity of magnetic ordering. We argue that, while being capable of correctly reproducing a uniform magnetic configuration, the hardware-efficient ansatz meets difficulties in providing a detailed description to a noncollinear magnetic structure.
arXiv Detail & Related papers (2021-05-13T11:58:18Z)
Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems. We propose an algorithm to implement imaginary time propagation on a quantum computer.
arXiv Detail & Related papers (2021-02-24T12:48:00Z)
An Application of Quantum Annealing Computing to Seismic Inversion [55.41644538483948]
We apply a quantum algorithm to a D-Wave quantum annealer to solve a small scale seismic inversions problem. The accuracy achieved by the quantum computer is at least as good as that of the classical computer.
arXiv Detail & Related papers (2020-05-06T14:18:44Z)
Simulating quantum chemistry in the seniority-zero space on qubit-based quantum computers [0.0]
We combine the so-called seniority-zero, or paired-electron, approximation of computational quantum chemistry with techniques for simulating molecular chemistry on gate-based quantum computers. We show that using the freed-up quantum resources for increasing the basis set can lead to more accurate results and reductions in the necessary number of quantum computing runs.
arXiv Detail & Related papers (2020-01-31T19:44:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.