QUANTUM COMPUTING - Bio-Inspired and Nanoscale Integrated Computing - page 93

Let us also assume that the number of qubits n is small (at most a few
hundreds). For sake of contradiction, let us for the moment suppose that
(i) quantum computing scales to at least moderate size (say a few tens of thousands
of qubits), and (ii) an e -approximate observation operation can be done on one of
n qubits by a microscopic measuring device of size n 0 =n c , for a constant c, and
operating within time polynomial in n. Since n is small, the measuring device is
surely of sufficiently small size so that its physics is consistent with established
quantum physics. (Observe that if quantum computing is to scale to at least
moderate size n 0 , then surely quantum effects need to hold for molecules of size n 0 ).
This implies that we need to view the apparatus for the observation as executing
polynomial time unitary quantum computation, which is reversible, so the reverse
of the observation also executes in quantum polynomial time. Hence we have an
apparent contradiction, since we have assumed the e -approximate observation is
not reversible in polynomial time. (Note: This argument does not require that the
governing physical laws shift at some definite size from a quantum-mechanical
paradigm to a classical paradigm; instead, the argument requires that if the
quantum-mechanical paradigm is valid at size n then it also is valid at some what
larger size n 0 =n c .)
Due to informal nature of this argument, it only provides partial evidence that
(with the above assumption), QC with the observation operation does not scale to
a large number of qubits within small volumes, and in particular that a polynomial
time e -approximate observation operation requires very large volume and cannot
be done at the micromolecular scale for moderate large n. We feel our above
argument is far too informal to provide a resolution of the issue. It remains a
major open problem in QC to provide a formal proof that either (i) there is large
volume required for observation or (ii) there is not.
3.13. CONCLUSIONS
This chapter provided an overview of the field of QC, including abstract models
for QC. We have surveyed major potential applications of QC, for example,
cryptography, speeding up combinatorial search and integer factorization were
surveyed. Major technologies for experimental implementation of QC have been
enumerated. Even after two decades of major research efforts, all prior QC
demonstrations to date have been limited to very small number of qubits. Various
key technical challenges and fundamental resource bounds for scaling QC to
larger problem sizes have been reviewed. It remains to be demonstrated if these
challenges can be overcome to allow QC to scale to problem instances of practical
importance to combinatorial search and integer factorization.
REFERENCES
Note: QCQC 98 is an acronym for Proceedings of 1st NASA Workshop on Quantum
Computation and Quantum Communication (QCQC 98), Springer-Verlag, Feb 1998.