Computable and noncomputable in the quantum domain: statements and conjectures

• URL: http://arxiv.org/abs/2403.16881v2
• Date: Thu, 31 Oct 2024 15:45:04 GMT
• Title: Computable and noncomputable in the quantum domain: statements and conjectures
• Authors: Aleksey K. Fedorov, Evgeniy O. Kiktenko, Nikolay N. Kolachevsky,
• Abstract summary: We consider an approach to the question of describing a class of problems whose solution can be accelerated by a quantum computer. The unitary operation that transforms the initial quantum state into the desired one must be decomposable into a sequence of one- and two-qubit gates.
• Score: 0.70224924046445
• License:
• Abstract: Significant advances in the development of computing devices based on quantum effects and the demonstration of their use to solve various problems have rekindled interest in the nature of the "quantum computational advantage." Although various attempts to quantify and characterize the nature of the quantum computational advantage have previously been made, this question largely remains open. Indeed, there is no universal approach that allows determining the scope of problems whose solution can be accelerated by quantum computers, in theory of in practice. In this paper, we consider 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 are of interest for quantum computing must be complex, i.e., not amenable to simulation by classical computers with less than exponential resources. On the other hand, such quantum states must be reachable on a practically feasible quantum computer. This means that the unitary operation that transforms the initial quantum state into the desired one must be decomposable into a sequence of one- and two-qubit gates of a length that is at most polynomial in the number of qubits. By formulating several statements and conjectures, we discuss the question of describing a class of problems whose solution can be accelerated by a quantum computer.

Related papers

• 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.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.