How can BQSS proceed when there are N simultaneous events without enumerating 3^N possibilities?

[-]

Hi,

I had a conceptual question regarding BQSS and I thought this might be a good place to ask. (If not, please just let me know!)

Consider a simple unstable system, x'[k] = x[k] with initial condition x[k] = k with k = 1 : N. Assume the same uniform quantization for all variables.
Conceptually, one would expect the first quantization event to be x[N], but... how can BQSS figure this out? It would seem that doing so requires enumerating 3^N different possibilities (+Q/0/-Q for each state), which is obviously prohibitive for any nontrivial value of N.

It would seem that this problem exists at the starting time for all systems (not just the example above), in addition to possible other times depending on the particular system.

Edit: I guess if you don't trigger a quantization event at the beginning, then you can avoid this problem at the initial condition. But it would still come up whenever there are simultaneous events, right?

Thank you!

[-]

Here is an example to illustrate what I mean. If we have

x1'(t) = x2(t)
x2'(t) = x1(t)
x1(0) = +1
x2(0) = −1
Q = 4

then

q1(0) = +1 + 4 = +5, q2(0) = −1 + 4 = +3
q1(0) = +1 − 4 = −3, q2(0) = −1 − 4 = −5

are both BQSS solutions.
In general, there would seem to be ≥ 2^N candidates for the solution to consider (in this case, half of them satisfy the model).

So my questions are:
1. I assume 1 solution is nondeterministically chosen out of all; is this correct?
2. How is a solution selected from the ≥ 2^N candidates? Would finding a solution take potentially exponential time, or can a solution always be found in polynomial (hopefully linear) time?

Thank you!

[-]

I think I figured it out, so for anyone else who might come across this later:

• It is indeed nondeterministic, but
• The reason it doesn't take an exponential amount of time to find a consistent solution is that a greedy algorithm doesn't need backtracking: i.e., there is always a valid choice for every quantized variable (perhaps it is "keep it constant" rather than "go up" or "go down", but at least one of these works) no matter how many others have been already (and so far, consistently) quantized at the same time step.

Edit 1: I'm still not 100% sure so I'm still looking over it to see if I'm missing anything.

Edit 2: If someone could kindly explain why using q(t-) is sufficient for determining q(t), I would greatly appreciate it—I'm confused why there is no consistency concern for q(t) in step 1a of the algorithm in the BQSS paper.

[marcel hendrix]

From a practical perspective, why allow simultaneous events? This leads to an (IMHO) interesting problem: what should the minimum timestep be? Making it 10e-301s is clearly not a good idea.

Maybe it is possible to not check all possibilities but instead only check for a useful subset of them and ignore all others?

-marcel