Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems

Abstract

If quantum states exhibit small nonlinearities during time evolution, then quantum computers can be used to solve NP-complete problems in polynomial time. We provide algorithms that solve NP-complete and #P oracle problems by exploiting nonlinear quantum logic gates. It is argued that virtually any deterministic nonlinear quantum theory will include such gates, and the method is explicitly demonstrated using the Weinberg model of nonlinear quantum mechanics.

10 pages, no figures, submitted to Phys. Rev. Lett

References in corpus (1)

• Simulation of Many-Body Fermi Systems on a Universal Quantum Computer

Cited by in corpus (129)

• Ultimate physical limits to computation
• On the role of entanglement in quantum computational speed-up
• Computational capacity of the universe
• Efficient quantum algorithm for dissipative nonlinear differential equations
• Almost quantum correlations
• Local PT symmetry violates the no-signaling principle
• NP-complete Problems and Physical Reality
• The quantum mechanics of time travel through post-selected teleportation
• Quantum perceptron over a field and neural network architecture selection in a quantum computer
• Testing foundations of quantum mechanics with photons
• Biology and medicine in the landscape of quantum advantages
• Can closed timelike curves or nonlinear quantum mechanics improve quantum state discrimination or help solve hard problems?
• Quantum feedback with weak measurements
• Information Invariance and Quantum Probabilities
• Quantum Computational Complexity in the Presence of Closed Timelike Curves
• Subquantum Information and Computation
• Bose-Einstein condensation in inhomogeneous Josephson arrays
• Nonunitary quantum circuit
• Linear Assignment Maps for Correlated System-Environment States
• Localized closed timelike curves can perfectly distinguish quantum states
• The Hidden Subgroup Problem - Review and Open Problems
• Almost Certain Escape from Black Holes
• Fast quantum state discrimination with nonlinear PTP channels
• Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices
• Quantum convolution and quantum correlation algorithms are physically impossible
• Is Quantum Mechanics An Island In Theoryspace?
• Quantitative approaches to information recovery from black holes
• Why initial system-environment correlations do not imply the failure of complete positivity: a causal perspective
• Computation in generalised probabilistic theories
• The computational landscape of general physical theories
• Optimal state discrimination and unstructured search in nonlinear quantum mechanics
• PT-symmetric quantum state discrimination
• Signal-based classical emulation of a universal quantum computer
• Nonlinear Quantum Search Using the Gross-Pitaevskii Equation
• Fast optimization algorithms and the cosmological constant
• Quantum associative memory with linear and non-linear algorithms for the diagnosis of some tropical diseases
• Quantum computation is the unique reversible circuit model for which bits are balls
• The Quantum Path Kernel: a Generalized Quantum Neural Tangent Kernel for Deep Quantum Machine Learning
• Limits on Efficient Computation in the Physical World
• Darboux-integration of idρ/dt=[H,f(ρ)]
• Quantum state matching of qubits via measurement-induced nonlinear transformations
• Weightless neural network parameters and architecture selection in a quantum computer
• Entanglement-based quantum deep learning
• Entanglement Between Bose-Einstein Condensates
• Grover search and the no-signaling principle
• Autonomous Quantum State Transfer by Dissipation Engineering
• De Broglie-Bohm Quantum Mechanics
• Informal Resource Letter - Nonlinear quantum mechanics on arXiv up to August 2004
• Computational tameness of classical non-causal models
• A healthier semi-classical dynamics
• Quantum Computing, NP-complete Problems and Chaotic Dynamics
• Quantum differential equation solvers: limitations and fast-forwarding
• Notes on nonlinear quantum algorithms
• Space-bounded Church-Turing thesis and computational tractability of closed systems
• An Introduction to Quantum Computing for Non-Physicists
• Experimental orthogonalization of highly overlapping quantum states with single photons
• Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems
• Quantum search with interacting Bose-Einstein condensates
• The nonlinear directional coupler. An analytic solution
• Memory Effects in Quantum Processes
• Computational complexity of non-equilibrium steady states of quantum spin chains
• Experimental limit on non-linear state-dependent terms in quantum theory
• Experimental Realization of Brüschweiler's exponentially fast search algorithm in a homo-nuclear system
• Optimization by a quantum reinforcement algorithm
• Quantum computing approach to realistic ESG-friendly stock portfolios
• Nonlinear Quantum Mechanics at the Planck Scale
• Nonlinear Schrödinger equations and generalized Heisenberg uncertainty principle violating the principle of estimation independence
• Design nearly optimal quantum algorithm for linear differential equations via Lindbladians
• Quantum State Readout, Collapses, Probes and Signals
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories
• Quantum simulation from the bottom up: the case of rebits
• Subspace projection method for unstructured searches with noisy quantum oracles using a signal-based quantum emulation device
• Nonlinear transformation of complex amplitudes via quantum singular value transformation
• An invitation to the sample complexity of quantum hypothesis testing
• Nonlinear and non-CP gates for Bloch vector amplification
• Neural Networks Architecture Evaluation in a Quantum Computer
• Estimation independence as an axiom for quantum uncertainty
• Emergent Quantum Mechanics at the Boundary of a Local Classical Lattice Model
• Proposal for a Lorenz qubit
• Probing the limits of quantum theory with quantum information at subnuclear scales
• Entanglement, intractability and no-signaling
• Quantum Adiabatic Computation and the Travelling Salesman Problem
• Quantum information processing and quantum logic: toward mutual illumination
• Unitary Evolutions Sourced By Interacting Quantum Memories: Closed Quantum Systems Directing Themselves Using Their State Histories
• Concise Quantum Associative Memories with Nonlinear Search Algorithm
• Coordinating quantum agents' perspectives: convex operational theories, quantum information, and quantum foundations
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• The Quantum Frontier
• Causality Violation and Nonlinear Quantum Mechanics
• Protocol for nonlinear state discrimination in rotating condensate
• Beyond the Projection Postulate and Back: Quantum Theories with Generalised State-Update Rules
• Quantum estimation bound of Gaussian matrix permanent
• Digital Quantum Simulation of Scalar Yukawa Coupling
• No-Signaling in Steepest Entropy Ascent: A Nonlinear Non-local Non-equilibrium Quantum Dynamics of Composite Systems
• Simulation of exceptional-point systems on quantum computers for quantum sensing
• Characterizing the asymmetry in hardness between synthesis and destruction of heteropolymers
• Lorentz Quantum Computer
• $\mathcal{P}\mathcal{T}$-Symmetric Quantum Discrimination of Three States
• $\mathcal{P}\mathcal{T}$-symmetric mapping of three states and its implementation on a cloud quantum processor
• Comment on "All-optical machine learning using diffractive deep neural networks"
• Measurement and Quantum Dynamics in the Minimal Modal Interpretation of Quantum Theory
• Revisiting Integer Factorization using Closed Timelike Curves
• Constant-Time Quantum Search with a Many-Body Quantum System
• Reality, Causality, and Quantum Theory
• Entanglement of $\pi$-LME states and the SAT problem
• Nonlinear Quantum Search
• Quantum Neural Networks
• A bird's eye view of quantum computers
• Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
• No-signaling, intractability and entanglement
• NP in BQP with Nonlinearity
• Searching via nonlinear quantum walk on the 2D-grid
• On the complexity of probabilistic trials for hidden satisfiability problems
• The universe as a nonlinear quantum simulation: Large $n$ limit of the central spin model
• Quantum Computing, Postselection, and Probabilistic Polynomial-Time
• Does Quantum Mechanics Breed Larger, More Intricate Quantum Theories? The Case for Experience-Centric Quantum Theory and the Interactome of Quantum Theories
• On the Simulation of Adaptive Measurements via Postselection
• A quantum computing scheme for the Hamiltonian path problem
• Novel formulation of Hamilton-Jacobi equation for higher derivative theory and quantum mechanical correspondence
• A Lossless Fuzzy Binary AND/OR Compressor
• From no causal loop to absoluteness of cause: discarding the quantum NOT logic
• Modular quantum computing and quantum-like devices
• Liquid State Machines in Adbiatic Quantum Computers for General Computation
• Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
• Fundamental Physics, Existential Risks and Human Futures
• Quantum interpretations, causality and quantum computation
• Nonunitary gates using measurements only
• Graph comparison via nonlinear quantum search