Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/9802051

Notes on nonlinear quantum algorithms

Marek Czachor

Published Feb 19, 1998• 13 citations
arXivHTMLPDF

Abstract

Recenty Abrams and Lloyd have proposed a fast algorithm that is based on a nonlinear evolution of a state of a quantum computer. They have explicitly used the fact that nonlinear evolutions in Hilbert spaces do not conserve scalar products of states, and applied a description of separated systems taken from Weinberg's nonlinear quantum mechanics. On the other hand it is known that violation of orthogonality combined with the Weinberg-type description generates unphysical, arbitrarily fast influences between noninteracting systems. It was not therefore clear whether the algorithm is fast because arbitrarily fast unphysical effects are involved. In these notes I show that this is not the case. I analyze both algorithms proposed by Abrams and Lloyd on concrete, simple models of nonlinear evolution. The description I choose is known to be free of the unphysical influences (therefore it is not the Weinberg one). I show, in particular, that the correct local formalism allows even to simplify the algorithm.

DOI
10.48550/arxiv.quant-ph/9802051

Related papers

Local modification of the Abrams-Lloyd nonlinear algorithm

Marek Czachor

The nonlinear algorithms proposed recently by Abrams and Lloyd [Report No. quant-ph/9801041] are fast but make an explicit use of an arbitrarily fast unphysical transfer of information within a quantum computer. It is shown that there exists a simplification of the second Abrams-Lloyd algorithm which eliminates the unphysical effect but keeps the algorithm fast.

arXiv:quant-ph/9803019•Mar 9, 1998•9 citations

Nonlinear Schrödinger equation and two-level atoms

Marek Czachor

Starting with the same form of atomic nonlinearity, Weinberg [Ann. Phys. (NY) 194, 336 (1989)] and W\'odkiewicz and Scully [Phys. Rev. A 42, 5111 (1990)] obtained contradictory results concerning an evolution of the atomic inversion w in a two-level atom in Weinberg's nonlinear quantum mechanics: If the atom is initially in a ground state then either the evolution of w (1) can be linear if one uses a nonlinear generalization of the Jaynes-Cummings Hamiltonian, or (2) is always nonlinear if one uses the nonlinear Bloch equations derived from the nonlinear atomic Hamiltonian function. It is shown that the difference is rooted in inequivalent descriptions of the composite ``atom-plus-field'' system. The linear evolution of w results from a ``faster-than-light communication'' between the atom and the field. If one applies a description without the ``faster-than-light telegraph'' then the calculations based on a suitably modified Jaynes-Cummings Hamiltonian lead to the same dynamics of w as is found in semiclassical calculations based on Bloch equations. It is shown also that a nonlinear quantum mechanics based on a nonlinear Schr\"odinger equation does not possess a natural probability interpretation.

arXiv:quant-ph/9501007•Physical Review A•Mar 1, 1996•28 citations

On the General Class of Models of Adiabatic Evolution

Jie Sun, Songfeng Lu, Fang Liu

The general class of models of adiabatic evolution was proposed to speed up the usual adiabatic computation in the case of quantum search problem. It was shown [8] that, by temporarily increasing the ground state energy of a time-dependent Hamiltonian to a suitable quantity, the quantum computation can perform the calculation in time complexity O(1). But it is also known that if the overlap between the initial and final states of the system is zero, then the computation based on the generalized models of adiabatic evolution can break down completely. In this paper, we find another severe limitation for this class of adiabatic evolution-based algorithms, which should be taken into account in applications. That is, it is still possible that this kind of evolution designed to deal with the quantum search problem fails completely if the interpolating paths in the system Hamiltonian are chosen inappropriately, while the usual adiabatic evolutions can do the same job relatively effectively. This implies that it is not always recommendable to use nonlinear paths in adiabatic computation. On the contrary, the usual simple adiabatic evolution may be sufficient for effective use.

Open Systems & Information Dynamics•Sep 1, 2016•3 citations

NP in BQP with Nonlinearity

Phil Gossett

If one modifies the laws of Quantum Mechanics to allow nonlinear evolution of quantum states, this paper shows that NP-complete problems would be efficiently solvable in polynomial time with bounded probability (NP in BQP). With that (admittedly very unlikely) assumption, this is demonstrated by describing a polynomially large network of quantum gates that solves the 3SAT problem with bounded probability in polynomial time. As in a previous paper by Abrams and Lloyd (but by a somewhat simpler argument), allowing nonlinearity in the laws of Quantum Mechanics would prove the "weak Church-Turing thesis" to be false. General Relativity is suggested as a possible mechanism to supply the necessary nonlinearity.

arXiv:quant-ph/9804025•Apr 9, 1998•1 citation

Fast-forwarding quantum evolution

Shouzhen Gu, Rolando D. Somma, Burak Şahinoğlu

We investigate the problem of fast-forwarding quantum evolution, whereby the dynamics of certain quantum systems can be simulated with gate complexity that is sublinear in the evolution time. We provide a definition of fast-forwarding that considers the model of quantum computation, the Hamiltonians that induce the evolution, and the properties of the initial states. Our definition accounts for any asymptotic complexity improvement of the general case and we use it to demonstrate fast-forwarding in several quantum systems. In particular, we show that some local spin systems whose Hamiltonians can be taken into block diagonal form using an efficient quantum circuit, such as those that are permutation-invariant, can be exponentially fast-forwarded. We also show that certain classes of positive semidefinite local spin systems, also known as frustration-free, can be polynomially fast-forwarded, provided the initial state is supported on a subspace of sufficiently low energies. Last, we show that all quadratic fermionic systems and number-conserving quadratic bosonic systems can be exponentially fast-forwarded in a model where quantum gates are exponentials of specific fermionic or bosonic operators, respectively. Our results extend the classes of physical Hamiltonians that were previously known to be fast-forwarded, while not necessarily requiring methods that diagonalize the Hamiltonians efficiently. We further develop a connection between fast-forwarding and precise energy measurements that also accounts for polynomial improvements.

arXiv:2105.07304•Quantum•Nov 15, 2021•45 citations

Preparation of Approximate Eigenvector by Unitary Operations on Eigenstate in Abrams-Lloyd Quantum Algorithm

Latha S. Warrier

The Abrams-Lloyd quantum algorithm computes an eigenvalue and the corresponding eigenstate of a unitary matrix from an approximate eigenvector Va . The eigenstate is a basis vector in the orthonormal eigenspace. Finding another eigenvalue, using a random approximate eigenvector, may require many trials as the trial may repeatedly result in the eigenvalue measured earlier. We present a method involving orthogonalization of the eigenstate obtained in a trial. It is used as the Va for the next trial. Because of the orthogonal construction, Abrams-Lloyd algorithm will not repeat the eigenvalue measured earlier. Thus, all the eigenvalues are obtained in sequence without repetitions. An operator that anticommutes with a unitary operator orthogonalizes the eigenvectors of the unitary. We implemented the method on the programming language model of quantum computation and tested it on a unitary matrix representing the time evolution operator of a small spin chain. All the eigenvalues of the operator were obtained sequentially. Another use of the first eigenvector from Abrams-Lloyd algorithm is preparing a state that is the uniform superposition of all the eigenvectors. This is possible by nonorthogonalizing the first eigenvector in all dimensions and then applying the Abrams-Lloyd algorithm steps stopping short of the last measurement.

Journal of Computational Methods in Physics•Sep 11, 2013•0 citations
Recenty Abrams and Lloyd have proposed a fast algorithm that is based on a nonlinear evolution of a state of a quantum computer. They have explicitly used the fact that nonlinear evolutions in Hilbert spaces do not conserve scalar products of states, and applied a description of separated systems taken from Weinberg's nonlinear quantum mechanics. On the other hand it is known that violation of orthogonality combined with the Weinberg-type description generates unphysical, arbitrarily fast influences between noninteracting systems. It was not therefore clear whether the algorithm is fast because arbitrarily fast unphysical effects are involved. In these notes I show that this is not the case. I analyze both algorithms proposed by Abrams and Lloyd on concrete, simple models of nonlinear evolution. The description I choose is known to be free of the unphysical influences (therefore it is not the Weinberg one). I show, in particular, that the correct local formalism allows even to simplify the algorithm.
Starting with the same form of atomic nonlinearity, Weinberg [Ann. Phys. (NY) 194, 336 (1989)] and W\'odkiewicz and Scully [Phys. Rev. A 42, 5111 (1990)] obtained contradictory results concerning an evolution of the atomic inversion w in a two-level atom in Weinberg's nonlinear quantum mechanics: If the atom is initially in a ground state then either the evolution of w (1) can be linear if one uses a nonlinear generalization of the Jaynes-Cummings Hamiltonian, or (2) is always nonlinear if one uses the nonlinear Bloch equations derived from the nonlinear atomic Hamiltonian function. It is shown that the difference is rooted in inequivalent descriptions of the composite ``atom-plus-field'' system. The linear evolution of w results from a ``faster-than-light communication'' between the atom and the field. If one applies a description without the ``faster-than-light telegraph'' then the calculations based on a suitably modified Jaynes-Cummings Hamiltonian lead to the same dynamics of w as is found in semiclassical calculations based on Bloch equations. It is shown also that a nonlinear quantum mechanics based on a nonlinear Schr\"odinger equation does not possess a natural probability interpretation.
The general class of models of adiabatic evolution was proposed to speed up the usual adiabatic computation in the case of quantum search problem. It was shown [8] that, by temporarily increasing the ground state energy of a time-dependent Hamiltonian to a suitable quantity, the quantum computation can perform the calculation in time complexity O(1). But it is also known that if the overlap between the initial and final states of the system is zero, then the computation based on the generalized models of adiabatic evolution can break down completely. In this paper, we find another severe limitation for this class of adiabatic evolution-based algorithms, which should be taken into account in applications. That is, it is still possible that this kind of evolution designed to deal with the quantum search problem fails completely if the interpolating paths in the system Hamiltonian are chosen inappropriately, while the usual adiabatic evolutions can do the same job relatively effectively. This implies that it is not always recommendable to use nonlinear paths in adiabatic computation. On the contrary, the usual simple adiabatic evolution may be sufficient for effective use.
If one modifies the laws of Quantum Mechanics to allow nonlinear evolution of quantum states, this paper shows that NP-complete problems would be efficiently solvable in polynomial time with bounded probability (NP in BQP). With that (admittedly very unlikely) assumption, this is demonstrated by describing a polynomially large network of quantum gates that solves the 3SAT problem with bounded probability in polynomial time. As in a previous paper by Abrams and Lloyd (but by a somewhat simpler argument), allowing nonlinearity in the laws of Quantum Mechanics would prove the "weak Church-Turing thesis" to be false. General Relativity is suggested as a possible mechanism to supply the necessary nonlinearity.
We investigate the problem of fast-forwarding quantum evolution, whereby the dynamics of certain quantum systems can be simulated with gate complexity that is sublinear in the evolution time. We provide a definition of fast-forwarding that considers the model of quantum computation, the Hamiltonians that induce the evolution, and the properties of the initial states. Our definition accounts for any asymptotic complexity improvement of the general case and we use it to demonstrate fast-forwarding in several quantum systems. In particular, we show that some local spin systems whose Hamiltonians can be taken into block diagonal form using an efficient quantum circuit, such as those that are permutation-invariant, can be exponentially fast-forwarded. We also show that certain classes of positive semidefinite local spin systems, also known as frustration-free, can be polynomially fast-forwarded, provided the initial state is supported on a subspace of sufficiently low energies. Last, we show that all quadratic fermionic systems and number-conserving quadratic bosonic systems can be exponentially fast-forwarded in a model where quantum gates are exponentials of specific fermionic or bosonic operators, respectively. Our results extend the classes of physical Hamiltonians that were previously known to be fast-forwarded, while not necessarily requiring methods that diagonalize the Hamiltonians efficiently. We further develop a connection between fast-forwarding and precise energy measurements that also accounts for polynomial improvements.
The Abrams-Lloyd quantum algorithm computes an eigenvalue and the corresponding eigenstate of a unitary matrix from an approximate eigenvector Va . The eigenstate is a basis vector in the orthonormal eigenspace. Finding another eigenvalue, using a random approximate eigenvector, may require many trials as the trial may repeatedly result in the eigenvalue measured earlier. We present a method involving orthogonalization of the eigenstate obtained in a trial. It is used as the Va for the next trial. Because of the orthogonal construction, Abrams-Lloyd algorithm will not repeat the eigenvalue measured earlier. Thus, all the eigenvalues are obtained in sequence without repetitions. An operator that anticommutes with a unitary operator orthogonalizes the eigenvectors of the unitary. We implemented the method on the programming language model of quantum computation and tested it on a unitary matrix representing the time evolution operator of a small spin chain. All the eigenvalues of the operator were obtained sequentially. Another use of the first eigenvector from Abrams-Lloyd algorithm is preparing a state that is the uniform superposition of all the eigenvectors. This is possible by nonorthogonalizing the first eigenvector in all dimensions and then applying the Abrams-Lloyd algorithm steps stopping short of the last measurement.