Information Technology Reference
In-Depth Information
3.3.3. Quantum Parallel Complexity Classes
Let NC (QNC, respectively) be the class of (quantum, respectively) circuits with
polynomial size and polylogorithmic depth. Thus QNC is the quantum analog of
the processor efficient parallel class NC. Moore, Nilsson [91] define QNC and
show various problems are in QNC; for example, they show that the quantum
Fourier transform can be parallelized to linear depth and polynomial size.
3.4. BOUNDS ON MEASUREMENT, SENSING,
AND COMMUNICATION
3.4.1. Lower Bounds on Quantum Communication
Cleve et al. [92] prove linear lower bounds for the quantum communication
complexity of the inner product function and give a reduction from the quantum
information theory problem to the problem of quantum computation of the inner
product. Knill, Laflamme [93] characterize the communication complexity of one
qubit.
3.4.2. Interaction-Free Quantum Measurement
A method for (nearly) interaction-free measurement (IFM) specifies the design of a
quantum optical sensing system that is able to determine with arbitrarily high
likelihood if an obstructing body has been inserted into the system, without
moving or modifying its optical components; moreover, in the case that the
obstructing body is present, IFM uses at most an arbitrarily small multiplicative
factor of the input intensity to do the sensing. Kwiat et al. [94] (also see [95]) have
given a method for IFM which does repeated rounds of measurement to affect
small phase changes that eventually determine (via the quantum Zeno effect)
whether an obstructing body has been inserted. Kwiat et al. [95] assert their
method can be applied to sensing tasks such as photography, but the use of their
method for IMF has major practical limitations (i.e., if the obstructing body has
not been inserted, then the amount of sensing can be quite large).
3.4.3. Interaction-Free Quantum Sensing
Reif [96] defines (nearly) interaction-free sensing (IFS) similarly to IFM, except
an upper bound is imposed on both the intensity to do the sensing (which again is
an arbitrarily small multiplicative factor of the input intensity) whether or not the
obstructing body is present. A quantum optical method for IFS (but not IFM)
may be used to do I/O with bandwidth reduced by an arbitrarily small multi-
plicative factor of the bandwidth required for classical (e.g., conventional optical
or electronic) I/O methods. Reif [96] proves there is no method for IFS with
 
Search WWH ::




Custom Search