{'fraction_non_alphanumeric': 0.023604346197077557, 'fraction_numerical': 0.003996503059822655, 'mean_word_length': 4.853801169590644, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Remarks on the nature of quantum computation

Two models of computer, a quantum and a classical"chemical machine"designed to compute the relevant part of Shor's factoring algorithm are discussed. The comparison shows that the basic quantum features believed to be responsible for the exponential speed-up of quantum computations possess their classical counterparts for the hybrid digital-analog computer. It is argued that the measurement errors which cannot be fully corrected make the computation not efficient for both models.


I. INTRODUCTION
The appearance of Shor's algorithm for factoring integers [1] beside its potential practical consequences for cryptography posed a fundamental, even philosophical question: What is the nature of quantum computation process which makes possible efficient solutions of problems for which the efficient classical algorithms seem not exist?
We remind that the algorithm is efficient if it uses a number of logical steps which is at most polynomial in logarithm of the input size N. In the course of development of quantum information and computation theory the above statements have been individually challenged by several authors. For example, in [2] the picture of "many simultaneous computations" is rebutted, and in [3] the key role of entanglement is questioned. The parallellism between classical chaos and quantum decoherence, on the essential for quantum computations time scale ∼ log dimH (H-Hilbert space of the computer), has been studied in [4] while the examples of quantum noise which do not satisfy the assumptions of the existing error correction schemes were discussed in [5].
A quantum computer is a physical system governed by the probabilistic laws of quantum mechanics and involving both digital entities related to discrete spectra of observables and continuous ones associated with arbitrary superpositions and unitary rotations. Therefore a fair comparison demands to consider as a classical counterpart a probabilistic hybrid digitalanalog classical computer. In both cases the analysis of efficiency involves careful estimation of the used resources (time, space, energy) and the presence of continuous component implies the analysis of errors and their possible corrections.
In the present paper we would like to compare the realizations of the crucial part of the factoring algorithm on a quantum computer with the analogical scheme performed on a certain hybrid digital-analog "chemical machine". We argue that the typical quantum features A) B) possess their classical macroscopical counterparts. We discuss also the output measurement errors in both cases, their scaling with the size of the input and the feasibility of corrections.

II. FACTORING ALGORITHM -QUANTUM VS. CLASSICAL
The details of the factoring algorithm for a given integer N can be found in [1,6]. Here, we discuss the only essential (in the context of quantum computations) part of this algorithm, namely the computation of the period of the function where 1 < y < N is a randomly choosen fixed integer. From the obvious recurrence formula it follows that, indeed, F N (a) is periodic with a period 1 < r < N and takes r different values.
The important fact is that there exists a classical efficient algorithm for the computation of F N (a) while an efficient classical algorithm for the computation of r is not known and probably does not exist.

A. Quantum algorithm
The part of Shor's algorithm used to find the period r consists of four steps performed on a quantum computer consisting of two registers, the first is a system of L qubits with q = 2 L choosen to satisfy N 2 < q < 2N 2 , the second -l qubits , N ≤ 2 l and with an additional computer performing classical efficient "precomputations".
1) Initial state preparation produces the quantum state where the state |a > is a product of the qubit states corresponding to the binary representation of a.
2)The results of efficient classical precomputation of F N (a) are encoded into the entangled state 3) Quantum Fourier transform applied to the first register yields what allows to find the period r by performing accurate measurements of the work and computing log r = L log 2 − W Mk B T .
The intuitional picture behind this model may be provided by the theory of rubber [7]. The elasticity of rubber, consisting of polymers, is entirely due to the entropy, its internal energy is not changed in isothermal processes and its equilibrium state corresponds to a "random coil". There is also a certain striking similarity to the mechanism of muscle contraction where chemical energy is transformed into mechanical work [8]. One should also mention in this context the theoretical ideas and experiments on DNA-based computers or more general molecular computations involving for example protein folding [9]. In particular, the examples of computations with the macroscopic output measurement are conceptually close to the proposed model.

C. Measurement errors
Both, presented physical realizations of the computation of the period r are threated by errors of various origin. For the quantum computer irreversible processes of decoherence and dissipation decrease the probability of obtaining the right result while for the chemical machine due to irreversible processes of the entropy production the equality (6) must be replaced by the innequality W < T (S in − S out ). Ingenious ideas of error correction based on a certain amount of redundancy can improve the situation. The schemes of quantum error correction should work for certain types of environmental noises [10]. For the chemical computer the assumption of infinitely slow process can be relaxed by averaging over an ensemble of finite-time measurements and using the result of [11] which in our case gives the relation log r = L log 2 + log exp(−W/Mk B T ) .
Nevertheless, we cannot eliminate all errors. Let us concentrate on the errors in the final measurement of the output. In the quantum case we have to perform L independent measurements of the qubit states each of them yields the right result with the probability 2 −ǫ < 1.The sources of errors in the case of Stern-Gerlach experiment, which is the prototype of an ideal spin measurement, are discussed extensively in [12]. They are related to the uncertainty of continuous macroscopic parameters like magnetic field direction and position of the spot on the screen and therefore cannot be completely eliminated. It follows that the probability of correct identification of the output state |c > for the whole register falls down exponentially in log N For the classical model we measure the macroscopic work W with an accuracy δW . Introducing γ = δW/Mk B T we obtain the average error of the period r as δr = γr. Assuming the Gaussian distribution of errors we can estimate the probability of obtaining the right result as which is also exponentially small in log N.
Finaly, we could try to apply error correction schemes to the measurement outcome.
Assume for the moment, that in the quantum case for a given input we always obtain a single outcome c in an ideal measurement. Then, by repeating real, unsharp measurements a sufficient number of times (∼ log L) and using, for instance, majority rule for single-qubit outcomes we could effectively recover the right state. However, as mentioned in Section IIA the number of right outcomes c is equal to r and therefore exponentially large what makes this method not applicable. For the classical model repeating measurement K times can reduce an error by a factor 1/ √ K what is also an inefficient procedure. It seems that a quantum computer can be treated as a kind of hybrid digital-analog computer with all its advantages and drawbacks. Digital-analog machines were quite successful in the past and probably dominate information processing in living organisms despite their bad scaling of errors. Therefore, one cannot exclude that the future technology will allow quantum computers to be useful for certain specific tasks.