9.2 Variants of the Merchant’s Problem

In what follows we present an attempt by Calude and Pavlov [40] to trespass the Turing barrier (see also the discussion in Calude, _Dinneen _and Svozil _[36]).

Let us consider the following problem: A merchant learns than one of his five stacks of coins contains only false coins, grams heavier than normal ones. Can he find the odd stack by a single “weighting"? A simple solution is the following:
Take one coin from the first stack, two coins from the second stack, …, five coins from the last stack.
Measure the weight of the combination of coins and obtain the number .
The -th stack contains false coins.
The above solution is, in spirit, “quantum". It consists of the following steps:
_a) preparation,
b) measurement,
c) classical calculation.

Consider now the case when we have five stacks of coins, but a few (maybe none) may contain false coins. Can we, again with only one single “weighting", find all stacks containing false coins? A possible solution is to choose 1, 2, 4, 8, 16 coins from each stack, and use the uniqueness of base two representation.

Note that the difference between the above solutions is only in the specific way we chose the sample, i.e. in coding. The solutions work only if we have enough coins in each stack.

Two related problems appear in a natural way:
We have stacks of coins and we know that at most one stack may contain false coins. We are allowed to take just one coin from each stack. Can we determine whether there is a stack containing false coins, and in the affirmative, which?
We have now a countable many stacks, all of them, except at most one, containing true coins only. Can we determine whether there is a stack containing false coins?
Classically, these problems cannot be solved with one “weighting". In the first problem we can check whether there is a false coin, but we cannot find its position. The second problem is equivalent to the Halting Problem, so classically undecidable.
Is there any hope of positive solution?
For the first problem we consider as quantum space. Denote by the weight of a coin in the -th stack; if the -th stack contains true coins, then , otherwise, .

We consider the operator , where :

construct the quadratic form induced by the -th iteration of the operator , , and consider its dynamics:
if all coins are true , for all ;
if there are false coins in some stack, for some , , and the value increases with every new iteration.


We will work with a “weighted Lebesgue measure" with proper non-negative continuous density , for example, the Gaussian distribution

Hence the probability of the event is the integral

To solve our problem we assume that time is discrete, . The procedure will be probabilistic: it will indicate a method to decide, with a probability as close to one as we want, whether there exist any false coins; in the affirmative we will find the stack of false coins.

Fix a computable real as probability threshold. Assume that both and are computable reals. Choose a “test" vector . Assume that we have a quantum “device" which measures the quadratic form and clicks at time on when


(14)
In this case we say that the quantum “device" has sensitivity . In what follows we will assume that is a positive computable real.

Two cases may appear:
1. If then the “device" has clicked at time and we know for sure that there exist false coins in the system.
2. If at time the “device" hasn’t (yet?) clicked, then either all coins are true, i.e., , for all , or at time the growth of hasn’t yet reached the threshold .
In the first case the “device" will never click, so at each stage the test-vector produces “true" information; we can call a “true" vector.

In the second case, the test-vector is “lying" at time as we do have false coins in the system, but they were not detected at time ; we say that produces “false" information at time .

Of course, the second case may be dangerous, and indeed, classically we cannot say anything in this case.

If the system has false coins and they are located in the -th stack, then each test-vector whose -th coordinate is 0 produces “false" information at any time.

If the system has false coins and they are located in the -th stack, , but

then produces “false" information at time . If , then produces “false" information only a finite period of time, that is, only for

after this time the quantum “device" starts clicking.

The major problem is to distinguish between the absence/presence of false coins in the system, and in the last case to decide which stack contains false coins.

We will show how to compute the time such that when presented a randomly chosen test-vector to a quantum “device" with sensitivity that fails to click in time , then the system doesn’t contain false coins with probability larger than .

Consider now the indistinguishable set at time

If the system contains only true coins, then , for all . If there is one stack (say, the -th one) containing false coins, then is a cone centered at the “false" plane :

A direct calculation shows that


(15)
Selecting

in (15) we get


(16)
hence,


(17)
In fact, the above limit is constructive, that is, from (16), for every computable we can construct the computable bound


(18)
such that assuming that the system contains false coins, if then we get

Let us now denote by the event “the system contains no false coins" and by the event “the system contains false coins". By () we denote the a priori probability that the system contains no false coins (the system contains false coins).

In the simplest case . We can use Bayes’ formula to obtain the a posteriori probability that the system contains only true coins when at time the quantum “device" didn’t click:

When , goes to , so goes to . More precisely, if as in (18), then

In conclusion,
for every computable we can construct a computable time such that picking up at random a test-vector and using a quantum “device" with sensitivity up to time either
we get a click at some time , so the system contains false coins; the th stack, where is the unique coordinate such that , contains false coins;
we don’t get a click in time , so with probability greater than all coins are true.
For the second problem we follow the same strategy but use more sophisticated mathematical tools: the “device" (with sensitivity ) will distinguish the values of the iterated quadratic form

by observing the difference between the non-perturbed and perturbed sequences corresponding to two discrete stochastic processes. We will work with the intersections of with the discrete Sobolev class of summable sequences with the square norm square norm

and the discrete Sobolev class of weighted-summable sequences with the square norm

We consider two discrete stochastic processes corresponding to the equidistant sequence of moments of time and to the perturbed sequence of moments of time .

By natural extension from cylindrical sets we can define the Wiener measures and on these spaces and use the following relation between and : for every –measurable set ,

The indistinguishable set becomes

If we assume that there exist false coins in the system, say at stack , then _

then _

In fact,

provided _

Hence

It is not difficult to recognize that the infinite variant of the Merchant’s Problem is equivalent to the Halting Problem.

Let’s have a program which we want to check whether it stops or not. Given the program and a clock, we make a stack of coins at each tick of the clock. The stack consists of false coins only if the machine was running at the previous tick and stopped at the present tick. Otherwise, the stack of coins is from true coins. This process is, of course, infinite and cannot be completed classically. Further on, our quantum algorithm needs the whole, infinite sequence.

Do we get a problem? Yes. Can we solve it? Yes, and here is an oversimplified way to explain the solution (for details see the paper). Instead of trying to construct the infinite sequence we pick an infinite random test-vector in the Hilbert space and work with this vector. We fix also the accuracy we want to achieve. We will then compute “classically" the finite time which will be used by our quantum device to run the experiment on the random test-vector. This is possible because the set of “lying test-vectors" has constructive measure zero. If the device clicks in time then the answer is “the programs stops"; otherwise, the answer is “the program doesn’t stop with the pre-given accuracy".

We close with some comments.
 Not surprisingly, our approach goes beyond the “classical" model of quantum Turing machine.
The main result is mathematical: the Wiener measure of the indistinguishable set constructively tends to zero when tends to infinity.
The main ingredients of our approach are: a special type of continuity, the choice of test-vectors from a special class of trajectories of two Markov processes working in two different scales of time and realized as elements of an infinitely-dimensional Hilbert space (infinite superposition), the ability to work with “truly random" test-vectors in an evolution described by an exponentially growing semigroup and the possibility to obtain the result from a single measurement.
At this stage the “device" is more mathematical than physical. The discrete-time Brownian motion–used in the estimation of the probability of the indistinguishable set in the last section–can be represented as a “sum" of independent random variables with Gaussian distributions. It can be implemented as a “sum" of spins of a cascade of electrons formed by the shock-induced emission on a special geometrical structure of semiconductor elements with special random properties
Many problems are still open and much more remains to be done. Is the method used in this paper “natural"? Is it feasible? Is it better or can we get more “insight" about the nature of the Halting Problem if we use unitary operators?

For other approaches see the relativistic computing by Etesi and Németi [57] based on Hogart [73] and Kieu [79]