Computability and Complexity of Unconventional Computing Devices
arXiv:1702.02980
Abstract
We discuss some claims that certain UCOMP devices can perform hypercomputation (compute Turing-uncomputable functions) or perform super-Turing computation (solve NP-complete problems in polynomial time). We discover that all these claims rely on the provision of one or more unphysical resources.
arXiv commentto appear in "Computational Matter". Stepney, Rasmussen, Amos, eds. Springer 2017
References in corpus (21)
- Quantum Machine Learning
- A variational eigenvalue solver on a quantum processor
- A Quantum Approximate Optimization Algorithm
- Characterizing Quantum Supremacy in Near-Term Devices
- An Open-System Quantum Simulator with Trapped Ions
- Ultimate physical limits to computation
- Quantum algorithms: an overview
- Convolutional Networks for Fast, Energy-Efficient Neuromorphic Computing
- Towards Quantum Chemistry on a Quantum Computer
- Elucidating Reaction Mechanisms on Quantum Computers
- Digitized adiabatic quantum computing with a superconducting circuit
- Digital quantum simulation of fermionic models with a superconducting circuit
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- Hybrid quantum-classical approach to correlated materials
- Quantum Supremacy through the Quantum Approximate Optimization Algorithm
- A Software Methodology for Compiling Quantum Programs
- Quantum Simulation of Helium Hydride in a Solid-State Spin Register
- NP-complete Problems and Physical Reality
- Computational complexity of the landscape I
- Measuring Intelligence through Games
- A Survey and Discussion of Memcomputing Machines