Can mortals understand quantum computing?

Of course.

Can mortals also understand quantum computing? You can test your intelligence by secretly looking at pictures

2017/06/18

References:

1. E.Rieffel, W.Polak, An Introduction to QuantumComputing for Non-Physicists.

2.E.Strubell, An Introduction to QuantumAlgorithms.

------------------ -----------

Transforming understanding of computing (a short popular science article about classical computing, DNA computing and quantum computing)

As computers become more and more widespread, With profound application, the originally specialized mathematical concept of calculation has been generalized to the entire field of human knowledge, and has become an extremely universal scientific and philosophical concept, becoming a new perspective and new way for people to understand things and study problems. ideas and new methods.

What are calculations and types of calculations

In the public mind, calculation first refers to the addition, subtraction, multiplication and division of numbers, followed by the solution of equations, differential integration of functions, etc. ; People who know more know that calculation essentially includes the proof and derivation of theorems. It can be said that "calculation" is a mathematical concept that everyone knows, but there are probably not many people who can really answer what the essence of calculation is. In fact, until the 1930s, due to the work of mathematicians such as K. Godel (1906-1978), A. Church (1903-1995), and A.M. TUI-ing (1912-1954), Only then did people figure out what the nature of computation is, as well as fundamental issues such as what is computable and what is not computable.

Abstractly speaking, the so-called calculation is to transform from a symbol string f into another symbol string g. For example, converting the symbol string 12+3 into 15 is an addition calculation. If the symbol string f is x^2, and the symbol string g is 2x, the calculation from f to g is a differential. The same is true for theorem proof. Let f represent a set of axioms and derivation rules, let g be a theorem, then a series of transformations from f to g is the proof of theorem g. From this perspective, text translation is also a calculation. If f represents an English sentence and g represents a Chinese sentence with the same meaning, then f to g means translating English into Chinese. What are the similarities between these transformations? Why are they all called calculations? Because they all start from known symbols (strings), change the symbols (strings) step by step, and after limited steps, finally obtain a transformation process that satisfies the predetermined symbols (strings).

In terms of type, there are two main categories of calculations: numerical calculations and symbolic derivation. Numerical calculations include addition, subtraction, multiplication and division of real numbers and functions, curtain operations, square root operations, equation solving, etc. Symbolic derivation includes proofs of identities and inequalities in algebra and various functions, proofs of geometric propositions, etc. But whether it is numerical calculation or symbolic derivation, they are essentially equivalent and consistent, that is, they are closely related, can be transformed into each other, and have the same computational essence. As mathematics continues to develop, new types of calculations may appear.

The Essence of Computing and the E-Strange-Turing Argument

In order to answer questions such as what is computation and what is computability, people adopt the method of establishing computational models. From the 1930s to the 1940s, mathematical logicians successively proposed four models, which are general recursive functions, lambda computable functions, Turing machines and Post (E.L. Post, 1897-1954) systems. These models explore the calculation process or proof process from completely different perspectives. On the surface, they are very different, but in fact they are equivalent, that is, they have exactly the same computing power. Based on this fact, they finally formed The now famous Church-Turing argument: all computable functions are general recursive functions (or Turing machine computable functions, etc.). This establishes the mathematical meaning of computation and computability. The following is a brief introduction to general recursive functions.

G?del first proposed the concept of primitive recursive functions in 1931. The so-called original recursive function is a function that starts from the initial function and uses a limited number of generations and the original recursive formula. The initial function mentioned here refers to the following three functions:

(1) Zero function 0(x)=0 (the function value is always zero);

(2) Projection Function (x1, x2,…,xn)=xi(1≤i≤n) (the value of the function is the same as the value of the i-th independent variable);

Successor function S(x)=x +1 (its value is the immediate successor of x).

Generations and original recursive expressions are operators for constructing new functions.

Generation (also known as superposition, superposition), it is the simplest and most important operator. Its general form is: an m-ary function f and m n-ary functions g1, g2 ,...,gm results in a new function f(g1(x1,x2,...,xn),g2(x1,x2,...,xn),...,gm(x1,x2,...,xn)).

The original recursive formula, its general form is

(formula omitted)

Specifically it is

(formula omitted)

The characteristic is that the general value of the new function f(u,x

cannot be directly calculated from the two known functions g and h.