Computable and noncomputable in the quantum domain: statements and conjectures

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.

5 pages, 1 figure; comments are very welcome

References in corpus (18)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Computing
• Improved Simulation of Stabilizer Circuits
• Strong quantum computational advantage using a superconducting quantum processor
• Tensor networks for complex quantum systems
• Optimal Quantum Circuits for General Two-Qubit Gates
• Quantum Entanglement in Neural Network States
• Hudson's Theorem for finite-dimensional quantum systems
• Solving Gapped Hamiltonians Locally
• Hadamard-free circuits expose the structure of the Clifford group
• Neural tensor contractions and the expressive power of deep neural quantum states
• Demonstration of algorithmic quantum speedup
• Realizing quantum gates with optically-addressable ${}^{171}$Yb${}^{+}$ ion qudits
• Security of the decoy state method for quantum key distribution
• Demonstration of a parity-time symmetry breaking phase transition using superconducting and trapped-ion qutrits
• Continuous dynamical decoupling of optical ${}^{171}$Yb${}^{+}$ qudits with radiofrequency fields
• Reconstructing complex states of a 20-qubit quantum simulator
• Sharp complexity phase transitions generated by entanglement