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
- Quantum computing topological invariants of two-dimensional quantum matter [0.0]
We present two quantum circuits for calculating Chern numbers of two-dimensional quantum matter on quantum computers.
First algorithm uses many qubits, and we analyze it using a tensor-network simulator of quantum circuits.
Second circuit uses fewer qubits, and we implement it experimentally on a quantum computer based on superconducting qubits.
arXiv Detail & Related papers (2024-04-09T06:22:50Z) - Review on Quantum Walk Computing: Theory, Implementation, and Application [0.30723404270319693]
The quantum walk is proposed as an important theoretical model for quantum computing.
Quantum walks and their variety have been extensively studied for achieving beyond classical computing power.
Recent progress has been achieved in implementing a wide variety of quantum walks and quantum walk applications.
arXiv Detail & Related papers (2024-04-05T15:45:35Z) - 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) - A prototype of quantum von Neumann architecture [0.0]
We propose a model of universal quantum computer system, the quantum version of the von Neumann architecture.
It uses ebits as elements of the quantum memory unit, and qubits as elements of the quantum control unit and processing unit.
Our primary study demonstrates the manifold power of quantum information and paves the way for the creation of quantum computer systems.
arXiv Detail & Related papers (2021-12-17T06:33:31Z) - Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor.
We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
arXiv Detail & Related papers (2021-01-21T22:18:49Z) - Quantum walk processes in quantum devices [55.41644538483948]
We study how to represent quantum walk on a graph as a quantum circuit.
Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
arXiv Detail & Related papers (2020-12-28T18:04:16Z) - 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) - Contraction-free quantum state encoding by quantum tunneling in single
molecules [0.0]
We propose a new system and theory for quantum computing that employs single molecule confinement between electrodes.
The striking features of this system are (i) an individual molecule that exhibits quantum tunneling can be regarded as a sequence of quantum gates, (ii) the quantum tunneling can be encoded onto an array of quantum bits, and (iii) quantum computing by quantum tunneling can be performed at room temperature.
arXiv Detail & Related papers (2020-01-15T14:54: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.