On exactly solved cases

Jozef Gruska, Daowen Qiu, Shenggen Zheng

The potential of the exact quantum information processing is an interesting, important and intriguing issue. For examples, it has been believed that quantum tools can provide significant, that is larger than polynomial, advantages in the case of exact quantum computation only, or mainly, for problems with very special structures. We will show that this is not the case. In this paper the potential of quantum finite automata producing outcomes not only with a (high) probability, but with certainty (so called exactly) is explored in the context of their uses for solving promise problems and with respect to the size of automata. It is shown that for solving particular classes [Formula: see text] of promise problems, even those without some very special structure, that succinctness of the exact quantum finite automata under consideration, with respect to the number of (basis) states, can be very small (and constant) though it grows proportional to [Formula: see text] in the case deterministic finite automata (DFAs) of the same power are used. This is here demonstrated also for the case that the component languages of the promise problems solvable by DFAs are non-regular. The method used can be applied in finding more exact quantum finite automata or quantum algorithms for other promise problems.

Stephen J. Gustafson, Israel Michael Sigal

Daiichiro Sugimoto

Physics is full of many-body problems. But many-problems cannot be solved exactly in terms of known mathematical functions. Even the three-body problem can only be solved exactly in a few special cases, and most many-body systems consist of many more than three bodies. Enter supercomputers.

Stephen J. Gustafson, Israel Michael Sigal

MASSIMO RUDAN

P.W. Anderson, G. Yuval, Donald R. Hamann

The simplest Kondo problem is treated exactly in the ferromagnetic case, and given exact bounds for the relevant physical properties in the antiferromagnetic case, by use of a Bcaling technique on an asymptotically exact expression for the ground-state properties given earlier. The theory also solves the n = 2 case of the one-dimensional Ising problem. The ferromagnetic case has a finite spin, while the antiferromagnetic case has no truly singular T → 0 properties (e.g., it has finite χ).