In recent years, rapid developments of quantum computer are witnessed in both the hardware and the algorithm domains, making it necessary to have an updated review of some major techniques and applications in quantum algorithm design. In this survey as well as tutorial article, the authors first present an overview of the development of quantum algorithms, then investigate five important techniques: Quantum phase estimation, linear combination of unitaries, quantum linear solver, Grover search, and quantum walk, together with their applications in quantum state preparation, quantum machine learning, and quantum search. In the end, the authors collect some open problems influencing the development of future quantum algorithms.

The GVWalgorithm is an efficient signature-based algorithm for computing Gr¨obner bases. In this paper, the authors consider the implementation of the GVW algorithm by using linear algebra, and speed up GVW via a substituting method. As it is well known that, most of the computing time of a Gr¨obner basis is spent on reductions of polynomials. Thus, linear algebraic techniques, such as matrix operations, have been used extensively to speed up the implementations. Particularly, one-direction (also called signature-safe) reduction is used in signature-based algorithms, because polynomials (or rows in matrices) with larger signatures can only be reduced by polynomials (rows) with smaller signatures. The authors propose a new method to construct sparser matrices for signature-based algorithms via a substituting method. Specifically, instead of only storing the original polynomials in GVW, the authors also record many equivalent but sparser polynomials at the same time. In matrix construction, denser polynomials are substituted by sparser equivalent ones. As the matrices get sparser, they can be eliminated more efficiently. Two specifical algorithms, Block-GVW and LMGVW, are presented, and their combination is the Sub-GVW algorithm. The correctness of the new proposed method is proved, and the experimental results demonstrate the efficiency of this new method.

In this paper, a Ritt-Wu characteristic set method for Laurent partial differential polynomial systems is presented. The concept of Laurent regular differential chain is defined and its basic properties are proved. The authors give a partial method to decide whether a Laurent differential chain A is Laurent regular. The decision for whether A is Laurent regular is reduced to the decision of whether a univariate differential chain A1 is Laurent regular. For a univariate differential chain A1, the authors first give a criterion for whether A1 is Laurent regular in terms of its generic zeros and then give partial results on deciding whether A1 is Laurent regular.

This paper presents the algebro-geometric method for computing explicit formula solutions for algebraic differential equations (ADEs). An algebraic differential equation is a polynomial relation between a function, some of its partial derivatives, and the variables in which the function is defined. Regarding all these quantities as unrelated variables, the polynomial relation leads to an algebraic relation defining a hypersurface on which the solution is to be found. A solution in a certain class of functions, such as rational or algebraic functions, determines a parametrization of the hypersurface in this class. So in the algebro-geometric method the author first decides whether a given ADE can be parametrized with functions from a given class; and in the second step the author tries to transform a parametrization into one respecting also the differential conditions. This approach is relatively well understood for rational and algebraic solutions of single algebraic ordinary differential equations (AODEs). First steps are taken in a generalization to systems and to partial differential equations.

The algebraic methods represented by Wu’s method have made significant breakthroughs in the field of geometric theorem proving. Algebraic proofs usually involve large amounts of calculations, thus making it difficult to understand intuitively. However, if the authors look at Wu’s method from the perspective of identity,Wu’s method can be understood easily and can be used to generate new geometric propositions. To make geometric reasoning simpler, more expressive, and richer in geometric meaning, the authors establish a geometric algebraic system (point geometry built on nearly 20 basic properties/formulas about operations on points) while maintaining the advantages of the coordinate method, vector method, and particle geometry method and avoiding their disadvantages. Geometric relations in the propositions and conclusions of a geometric problem are expressed as identical equations of vector polynomials according to point geometry. Thereafter, a proof method that maintains the essence of Wu’s method is introduced to find the relationships between these equations. A test on more than 400 geometry statements shows that the proposed proof method, which is based on identical equations of vector polynomials, is simple and effective. Furthermore, when solving the original problem, this proof method can also help the authors recognize the relationship between the propositions of the problem and help the authors generate new geometric propositions.

The aim of this article is to present the contribution ofWuWen-Ts¨un to Algebraic Topology and more precisely to the theory of characteristic classes. Several papers provide complete and welldocumented biography and academic career of Wu Wen-Ts¨un, in particular, Hudecek, 2014; O’Connor and Robertson, 2006; Wen-Ts¨un Wu’s Academic Career, 2006; Selected works of Wen-Tsun Wu, 2008. The author does not repeat the details provided in these papers concerning the Wu Wen-Ts¨un’s bibliography, we will just mention people involved in the Wu Wen-Ts¨un’s period in France. In addition to Wu Wen-Ts¨un’s papers, the Dieudonn´e’s book (Dieudonn´e, 1960) provides an excellent presentation of main results of Wu Wen-Ts¨un in Algebraic and Differential Topology. The author will use and abuse of this book (and refer to) when suitable. In the introduction, the author recalls mainly historical facts concerning the contribution of Wu Wen-Ts¨un to Algebraic Topology. The second section shows specifically the contribution of Wu Wen- Ts¨un to the Stiefel-Whitney classes and introduces the third section, dealing with the (real) Wu classes. The author provides definition, properties as well as further developments and generalizations of the Wu classes. The fourth and fifth sections are devoted to recent applications: In Cobordism theory and in Mathematical Physics. The author notices that Wu classes have been used as well in other domains, in particular surgery theory (Madsen and Milgram, 1979). The last section concerns the complex Wu classes and shows that the more recent Mather classes coincide with the previously defined complex Wu classes, that is a result from Zhou (1994) (see also Liu, 1996). This article is devoted to the contribution of Wu Wen-Ts¨un to the theory of Characteristic Classes, which coincides with his “French period” (1947–1951). However, speaking of Algebraic Topology, it is worthwhile to mention the important contribution of Wu Wen-Ts¨un to the Theory of realization of complexes or manifolds in Euclidean spaces and of embedding classes. That coincides with his return to China (1956–1965).

The idea of envelope of a family of plane curves is an elementary notion in differential geometry. As such, its implementation in dynamic geometry environments is quite universal (Cabri, The Geometer’s Sketchpad, Cinderella, GeoGebra, ...). Nevertheless, most of these programs return, when computing certain envelopes, both some spurious solutions and the curves that truly fit in the intuitive definition of envelope. The precise distinction between spurious and genuine parts has not been made before: This paper proposes such distinction in an algorithmic way, ready for its implementation in interactive geometry systems, allowing a finer classification of the different parts resulting from the current, advanced approach to envelope computation and, thus, yielding a more precise output, free from extraneous components.

Weispfenning in 1992 introduced the concepts of comprehensive Gr¨obner system/basis of a parametric polynomial system, and he also presented an algorithm to compute them. Since then, this research field has attracted much attention over the past several decades, and many efficient algorithms have been proposed. Moreover, these algorithms have been applied to many different fields, such as parametric polynomial equations solving, geometric theorem proving and discovering, quantifier elimination, and so on. This survey brings together the works published between 1992 and 2018, and we hope that this survey is valuable for this research area.

The authors translate the main results in the paper entitled “Multiplicative Decomposition of Multivariate q-Hypergeometric Terms” from Chinese into English. The paper is written by Shaoshi Chen, Ruyong Feng, Guofeng Fu and Jing Kang, and published in Journal of Mathematics and Systems Science, 32(8), 1019–1032, 2012. Some minor simplification and modification are made during the translation. Based on the results in the above paper, a special form is derived for q-shift exponents appearing in the q-shift quotients of a q-hypergeometric term.

Hilbert problem 15 requires to understand Schubert’s book. In this book, there is a theorem in §23, about the relation of the tangent lines from a point and the singular points of cubed curves with cusp near a 3-multiple straight line, which was obtained by the so called main trunk numbers, while for these numbers, Schubert said that he obtained them by experiences. So essentially Schubert even did not give any hint for the proof of this theorem. In this paper, by using the concept of generic point in the framework of Van der Waerden and Weil on algebraic geometry, and realizing Ritt-Wu method on computer, the authors prove that this theorem of Schubert is completely right.

In this paper it is shown how to transform a regular triangular set into a normal triangular set by computing the W-characteristic set of their saturated ideal and an algorithm is proposed for decomposing any polynomial set into finitely many strong characteristic pairs, each of which is formed with the reduced lexicographic Gr¨obner basis and the normal W-characteristic set of a characterizable ideal.

This paper presents the practice of automated theorem proving in Euclidean geometry with null geometric algebra, a combination of Conformal Geometric Algebra and Grassmann-Cayley algebra. This algebra helps generating extremely short and readable proofs: The proofs generated are mostly one-termed or two-termed. Besides, the theorems are naturally extended from qualitative description to quantitative characterization by removing one or more geometric constraints from the hypotheses.

Elimination theory is central in differential and difference algebra. The Wu-Ritt characteristic set method, the resultant and the Chow form are three fundamental tools in the elimination theory for algebraic differential or difference equations. In this paper, the authors mainly present a survey of the existing work on the theory of characteristic set methods for differential and difference systems, the theory of differential Chow forms, and the theory of sparse differential and difference resultants.

Let f, g1, · · · , gs be polynomials in R[X1, · · · ,Xn]. Based on topological properties of generalized critical values, the authors propose a method to compute the global infimum f ∗ of f over an arbitrary given real algebraic set V = {x ∈ Rn | g1(x) = 0, · · · , gs(x) = 0}, where V is not required to be compact or smooth. The authors also generalize this method to solve the problem of optimizing f over a basic closed semi-algebraic set S = {x ∈ Rn | g1(x) ≥ 0, · · · , gs(x) ≥ 0}.

A framework for generating congruence closure and conditional congruence closure of ground terms over uninterpreted as well as interpreted symbols satisfying various properties is proposed. It is based on some of the key concepts from Kapur’s congruence closure algorithm (RTA97) for ground equations based on introducing new symbols for all nonconstant subterms appearing in the equation set and using ground completion on uninterpreted constants and purified equalities over interpreted symbols belonging to different theories. In the original signature, the resulting rewrite systems may be nonterminating but they still generate canonical forms. A byproduct of this framework is a constant Horn completion algorithm using which ground canonical Horn rewrite systems can be generated for conditional ground theories.

The geometric constructions obtained with only straightedge and compass are famous and play a special role in the development of geometry. On the one hand, the constructibility of figures is a key ingredient in Euclid geometry and, on the other hand, unconstructibility gave birth to famous open problems of the ancient Greece which were unlocked only in the nineteenth century using discoveries in algebra. This paper discusses the mechanization of straightedge and compass constructions. It focuses on the algebraic approaches and presents two methods which are implemented; one is due to Lebesgue and the other one was jointly designed by Gao and Chou. Some links between the algebraic approach of constructions and synthetic geometry are described.

Motivated by the idea of Shen, et al.’s work, which proposed a hybrid procedure for real root isolation of polynomial equations based on homotopy continuation methods and interval analysis, this paper presents a hybrid procedure to compute sample points on each connected component of a real algebraic set by combining a special homotopy method and interval analysis with a better estimate on initial intervals. For a real algebraic set given by a polynomial system, the new method first constructs a square polynomial system which represents the sample points, and then solve this system by a special homotopy continuation method introduced recently by Wang, et al. (2017). For each root returned by the homotopy continuation method, which is a complex approximation of some (complex/real) root of the polynomial system, interval analysis is used to verify whether it is an approximation of a real root and finally get real points on the given real algebraic set. A new estimate on initial intervals is presented which helps compute smaller initial intervals before performing interval iteration and thus saves computation. Experiments show that the new method works pretty well on tested examples.

Boolean functions with optimal algebraic immunity (OAI functions) are important cryptographic primitives in the design of stream ciphers. During the past decade, a lot of work has been done on constructing such functions, among which mathematics, especially finite fields, play an important role. Notably, the approach based on decompositions of additive or multiplicative groups of finite fields turns out to be a very successful one in constructing OAI functions, where some original ideas are contributed by Tu and Deng (2012), Tang, et al. (2017), and Lou, et al. (2015). Motivated by their pioneering work, the authors and their collaborators have done a series of work, obtaining some more general constructions of OAI functions based on decompositions of finite fields. In this survey article, the authors review our work in this field in the past few years, illustrating the ideas for the step-by-step generalizations of previous constructions and recalling several new observations on a combinatorial conjecture on binary strings known as the Tu-Deng conjecture. In fact, the authors have obtained some variants or more general forms of Tu-Deng conjecture, and the optimal algebraic immunity of certain classes of functions we constructed is based on these conjectures.