{'fraction_non_alphanumeric': 0.02716525530309382, 'fraction_numerical': 0.008384338056510439, 'mean_word_length': 4.344086021505376, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Notes on nonlinear quantum algorithms

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.

Recenty Abrams and Lloyd [1] have proposed a fast algorithm that is based on a nolinear 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.

I. FIRST ALGORITHM
Step 1. We begin with the state where the first n qubits correspond to the input and the last qubit represents the output.
Consider the unitary transformation acting as follows Step 2.
The input constists now of a uniform superposition of all the numbers 0 ≤ n ≤ 2 n − 1.
because the sum over j vanishes.
Step 5. We want to distinguish between the cases s = 0 and s > 0 for small s. To do so we are going to use a nonlinear dynamics that does not change the "North Pole" |0 but any superposition of |0 with |1 drags to the "South". The violation of orthogonality is called, after Mielnik [3], the mobility phenomenon.

II. MOBILITY FREQUENCY
Let us first concentrate on a single-qubit system. The first natural guess is something like where and η is small but nonzero. The solution of (19) for normalized ψ 0 is Assume Then The mobility frequency is therefore which for 2 n ≫ s gives approximately which makes the algorithm exponentially slow. Let us try therefore another nonlinearity: We find For η of the order of 2 −(n−1)/2 one can obtain a reasonable mobility frequency but this requires an exponentially precise control over 0|A|0 .

III. EVOLUTION OF THE ENTIRE SYSTEM
The discussion given above applies to a single-qubit (flag) subsystem. The entire system that is involved consists of n + 1 systems and therefore we arrive at the delicate problem of extending a one-particle nonlinear dynamics to more particles.
The description chosen by Abrams and Lloyd uses the Weinberg prescription. Several comments are in place here. First, it is known that the Weinberg formulation implies a "faster-than-light telegraph". The version of the telegraph especially relevant in this context is the one that is based on the mobility effect [2]. It is therefore not clear a priori to what extent the fact that the algorithm is fast depends on the presence of faster than light effects. Second, the Weinberg prescription is meant to describe systems that do not interact. We have two options now. Either we indeed want to keep the flag qubit noninteracting with the input (during the nonlinear evolution) or we allow a nonlinear evolution which involves the entire quantum computer. If we decide on the first option we should use the Polchinskitype description which eliminates the unphysical nonlocal influences, but the nonlinear evolution of the flag qubit is determined by its reduced density matrix (the Polchinski-type description was recently formulated for a class of equations more general than those considered by Weinberg in [5]; its aplication to interacting systems can be found for example in [6]). This is the reduced density matrix obtained by the reduction over all 2 n states of the input subsystem. Physically this kind of evolution occurs if the nonlinearity is active independently of the state of the n input qubits.
But the very idea of the algorithm is to take advantage of the fact that probability of finding the entire input in the ground state esceeds 1/4. It is also assumed that one can turn the nonlinearity on and off. It is legitimate therefore to contemplate the situation where the nonlinearity is turned on only provided all the input detectors signal 0.
At this point one might be tempted to act as follows: Take as an initial condition for our nonlinear evolution the product state obtained by projecting the entire entangled state on |0 1 , . . . , 0 n . The problem with this kind of approach is that the "projection postulate" of linear quantum mechanics does not have an immediate extension to a nonlinear dynamics. There are many reasons for this but I do not want to discuss it here. At this moment it is sufficient to know that it is safer to avoid reasonings based on the projection postulate if nonlinearity is involved.
I propose an alternative formulation. Assume that indeed the nonlinearity is activated only if the input is in the ground state. In principle there is no problem with this because all the different combinations of 0's and 1's correspond to orthogonal vectors in the 2 n -dimensionl Hilbert space of the input and there exists, in principle, an analyzer that splits a beam of input particles into 2 n different sub-beams. We can place our hypothetical nonlinear medium in front of this output of the analyzer that corresponds to the qubinary zero.
Let us introduce two projectors: P (n) = |0 1 , . . . , 0 n 0 1 , . . . , 0 n | ⊗ 1 (33) Denote by |Ψ the state of the entire quantum computer, B = 1 (n) ⊗ A, and consider the following nonlinear equation Both expressions occuring under tanh are time-independent. In particular, for |Ψ = i1...ini Ψ i1...ini |i 1 , . . . i n |i The other term is constant since the operators under the averages commute with P (n) B. The term reads explicitly We know that and therefore the mobility frequency is identical to the one obtained for a single qubit description. The explicit evolution of the entire entangled state of the quantum computer is finally For those of the readers who have played a little bit with faster-than-light telegraphs in nonlinear quantum mechanics the basis dependence of the evolution may look somewhat suspicious. There is no problem with this, however, since the dependence on P (n) reflects our experimental configuration: By changing the projector we change the dynamics since we simply put the nonlinear device in a different position with respect to the first analyzer. In the faster-thanlight problem one gets into trouble if such basis-dependent terms are produced at a distance, and this is typical of the Weinberg formulation. It may be instructive to discuss what would have happened if we did not assume that the nonlinearity is somehow activated in a state dependent way. We therefore assume that the flag system does not interact with the input one. For this reason we cannot have any dependence on the basis corresponding to the input particles during the nonlinear evolution and we use the Polchinski-type extension of the dynamics which looks as follows The first term under tanh is obviously time-independent. The same with the second one which equals as before. The solution for the entangled state of our quantum computer is now whereω ǫ has to be determined.
To do so we first compute the reduced density matrix of the flag subsystem because the sums over j vanish. The flag susbsystem is therefore in a fully mixed state. Finallỹ so it may pay to act with the nonlinearity on a selected subbeam.
Returning to the question of exponential precision we should note that the nonlinearity I have chosen leads to periodic dynamics and for this reason has a vanishing Lyapunov exponent. One could invent a nonlinear equation for a two-dimensional dynamics with a positive exponent (cf. [4]) but calculations might be less trivial.

IV. SECOND ALGORITHM
The first three steps are identical to the previous ones.
Step 4. We begin with the result of the third step |i 1 , . . . , i n |f (i 1 , . . . , i n ) (49) We assume that f (n) = 1 for at most one n (s equals 0 or 1). The state (49) can be written as Let us note that with very high probability the state is With much smaller probability it is either or |0 1 , i 2 , . . . , i n |0 and is never in the form since this would mean there are two different numbers satisfying f (n) = 1 which contradicts our assumption. The idea of the algorithm is to use a nonlinearity that leaves (51) unchanged but (52) and (53) transforms, respectively, into |0 1 , i 2 , . . . , i n |1 and |0 1 , i 2 , . . . , i n |1 One should be aware of the fact such transformations are in fact impossible within the nonlinear Schrdinger equation framework since one cannot merge two different vectors into a single one if the dynamics is reversible and first order in time. However one can do this with arbitrary acuracy as can be clearly seen from the preceding examples. The more serious problem is that using exactly the same trick it was shown in [2] that this kind of evolution leads to influences between separated systems (here the flag system would influence the first qubit). In the Weinberg description this leads to a contradiction when one obtains this kind of behavior assuming simultaneously that the subsystems do not interact.
We have again two possibilities. We can either assume some form of interaction between the subsystems, or take a correct (n + 1)-particle extension of a nonlinear dynamics of the flag subsystem assuming no interactions between different subsystems.
Before launching into a more detailed analysis let us first illustrate the Abrams-Lloyd idea on a simple example. Take n = 3 and f (110) = 1. The oracle produces The nonlinearity now looks at the second and the third input slots and sees the above kets as the following pairs Now it scans each of the rows and does not do anything when two flag 0's occur, but when it notices one 0 and one 1 it changes 0 to 1. So after this step we get Now the nonlinearity looks at the first and the third slots and sees the kets as the following pairs It again behaves as before and what we get after this step looks as follows Finally our nonlinearity looks at the first and the second slots and the state regroups in the following way Now each row contains one 1 and in the final move all flag 0's are switched to 1's and the state partly disentangles: Of course, in case s = 0 the entire state does not change during the operation and a measurement on the flag qubit gives 0 with certainty. One can try to implement such an evolution in terms of a Schrödinger-type dynamics. Let us note that the above procedure is somewhat artificial. Once we agree that the nonlinearity can somehow globaly and simultaneously recognize the states of all the qubits the optimal strategy would be to choose a nonlinear evolution which changes all flag 0's into 1's if at least one 1 has been "seen".