Information Technology Reference
In-Depth Information
Table 10.6
Applying g
sa
¼
a
2
to multivibrator states
Truth table
x
1
x
2
g
as
Prepared list
Tagged list
Assumed list structure
0
0
0
1
1
¼a
1
b
1
0
1
0
1
1
¼a
1
b
2
1
0
1
1
1
¼a
2
b
1
1
1
1
1
1
¼a
2
b
2
x
1
0
x
2
Table 10.7
Decoding function g
d
¼
Truth table
x
1
x
2
g
as
Prepared list
Tagged list
Assumed list a
i
b
j
structure
0
0
0
1
1
a
1
b
1
0
1
1
1
1
a
1
b
2
1
0
0
1
1
a
2
b
1
1
1
0
1
1
a
2
b
2
For n multivibrators, there are 2
n
symmetric and antisymmetric multivibrator
functions whose truth table begins with a 0, and 2
n
symmetric and antisymmetric
“complementary” multivibrator functions whose truth table begins with a 1. Such
multivibrator functions can be classified with certainty to within a complement,
using only one evaluation. Normally a function of n binary variables would require
up to 2
n
calls to the function to fill in its truth table. So if an unknown multivibrator
function within the class g
sa
is applied to simulated qubits, it can be classified to
within a complement with only one call to the function and only one observation.
The Satisfiability Problem for a Multivibrator Decoding Function
An interesting class of binary functions g
d
may be defined on integers k,0
k
2
n
k
o
, for which g
d
(k
o
) ¼ 1. This
defines what are known in electrical engineering as a decoding function. Assume
that g
d
is known and given but that what satisfies it, k
o
is unknown. If one searches
classically, evaluating g
d
(k) until one finds k
o
one might have to make as many as 2
n
evaluations of g
d
(k).
When a binary function is known, it is not always easy to discover what satisfies
it, or makes it true, especially for complicated or indirectly presented functions.
Finding what satisfies a given binary function such as f
d
(k) is known as a
satisfiability problem.
Satisfiability problems also occur for multivibrator functions. Here is a simple
simulated qubit example in which the normalization factors have been omitted in
order to focus on the logic. Consider a multivibrator function on a Prepared List that
provides the Tagged List in Table
10.7
. Note that the truth table is true only for an
input of 01, so this is a decoding function; it satisfies the condition that only one
1, so that g
d
(k) ¼ 0 for all k except for k
¼
Search WWH ::
Custom Search