Below is Section 2 of my article
The Tale of One-Way Functions in Probl.Inf.Transm. 39(1), 2003.
[[ Double brackets indicate additions absent in the article.
Note: Latex formulas below require Java Scripts enabled for this page,
for https://cdn.jsdelivr.net and for https://www.cs.bu.edu/fac/lnd/mjx.js ]]
Polynomial Time and Extravagant Models.
2.1. The Downfall of RSA
This development [RSA and other applications of one-way functions] was
all the more remarkable as the very existence of one-way (i.e., easy to
compute, infeasible to invert) functions remains unproven and subject
to repeated assaults. The first came from Shamir himself, one of the
inventors of the RSA system. He proved in [Inf.Process.Lett. 8(1) 1979]
that factoring (on infeasibility of which RSA depends) can be done in
polynomial number of arithmetic operations. This result uses a so-called
"unit-cost model," which charges one unit for each arithmetic operation,
however long the operands. Squaring a number doubles its length, repeated
squaring brings it quickly to cosmological sizes. Embedding a huge array
of ordinary numbers into such a long one allows one arithmetic step
to do much work, e.g., to check exponentially many factor candidates.
The closed-minded cryptographers, however, were not convinced and
this result brought a dismissal of the unit-cost model, not RSA.
Another, not dissimilar, attack is raging this very moment.
It started with the brilliant result of Peter Shor [SIComp, 26(5) 1997].
He factors integers in polynomial time using an imaginary analog device,
Quantum Computer (QC), inspired by the laws of quantum physics
taken to their formal extreme.
2.2. Quantum Computers
QC has $n$ interacting elements, called q-bits. A pure state of each is
a unit vector on the complex plane $C^2$. Its two components are quantum
amplitudes of its two Boolean values. A state of the entire machine is
a vector in the tensor product of $n$ planes. Its $2^n$ coordinate
vectors are tensor-products of q-bit basis states, one for each $n$-bit
combination. The machine is cooled, isolated from the environment nearly
perfectly, and initialized in one of its basis states representing
the input and empty memory bits. The computation is arranged as a
sequence of perfectly reversible interactions of the q-bits, putting
their combination in the superposition of a rapidly increasing number
of basis states, each having an exponentially small amplitude.
The environment may intervene with errors; the computation is done in
an error-correcting way, immune to such errors as long as they are few
and of special restricted forms. Otherwise, the equations of Quantum
Mechanics are obeyed with unlimited precision. This is crucial since the
amplitudes are exponentially small and deviations in remote (hundredth or
even much further) decimal places would overwhelm the content completely.
Peter Shor shows such computers capable of factoring in polynomial time.
The exponentially many coordinates of their states can,
using a rough analogy, explore one potential solution each
and concentrate the amplitudes in the one that works.
2.3. Small Difficulties
There are many problems with such QCs. For instance, thermal isolation
cannot be perfect. Tiny backgrounds of neutrinos, gravitational waves,
and other exotics, cannot be shielded. Their effects on quantum
amplitudes need not satisfy the restrictions on which error-correcting
tools depend. Moreover, nondissipative computing gates, even classical,
remain a speculation. Decades past, their existence was cheerfully
proclaimed and even proved for worlds where the laws of physical
interaction can be custom-designed. In our world, where
the electromagnetic interaction between electrons, nuclei, and photons
is about the only one readily available, circuits producing less entropy
than computing remain hypothetical. So, low temperatures have limits
and even a tiny amount of heat can cause severe decoherence problems.
Furthermore, the uncontrollable degrees of freedom need not behave simply
as heat. Interaction with the intricately correlated q-bits may put
them in devilish states capable of conspiracies which defy imagination.
2.4. Remote Decimals
All such problems, however, are peanuts. The major problem is
the requirement that basic quantum equations hold to multi-hundredth
if not millionth decimal positions where the significant digits of
the relevant quantum amplitudes reside. We have never seen a physical law
valid to over a dozen decimals. Typically, every few new decimal places
require major rethinking of most basic concepts. Are quantum amplitudes
still complex numbers to such accuracies or do they become
quaternions, colored graphs, or sick-humored gremlins? I suspect
physicists would doubt even the laws of arithmetic pushed that far.
In fact, we know that the most basic laws cannot all be correct to hundreds
of decimals: this is where they stop being consistent with each other!
And what is the physical meaning of 500 digit long numbers?
What could one possibly mean by saying "This box has a remarkable property:
its q-bits contain the Ten Commandments with the amplitude whose
first 500 decimal places end with 666"? What physical interpretation
could this statement have even for just this one amplitude?
[[Remark: Subtleties and paradoxes of probability lead to widespread
confusions. I heard questions about why similar issues do not plague tiny
probabilities. Exponentially small probabilities themselves do not have
physical meaning. Their logarithms, i.e. entropies, do. Entropies are
falsifiable e.g., by finding, for an experimental result, a code with
significantly fewer bits than its entropy under the predicted distribution.
But this (analyzed by Kolmogorov) link with the (observable) complexity,
only works because probabilities are always positive (or 0). Quantum
amplitudes have no such property, so cannot carry this meaning.]]
Close to the tensor product basis, one might have opportunities to
restate the assertions using several short measurable numbers instead
of one long. Such opportunities may also exist for large systems,
such as lasers or condensates, where individual states matter little.
But QC factoring uses amplitudes of an exponential number of highly
individualized basis states. I doubt anything short of the most generic
and direct use of these huge precisions would be easy to substitute.
One can make the amplitudes more "physical" by choosing
a less physical basis. Let us look into this.
2.5. Too Small Universe
QC proponents often say they win either way, by making
a working QC or by finding a correction to Quantum Mechanics;
e.g., in 2000/03/22 sci.physics.research usenet article
"Re: When will quantum computers become practical?"
https://groups.google.com/group/sci.physics.research/msg/dc191983dfa1477b,
Peter Shor said:
"If there are nonlinearities in quantum mechanics which are detectable
by watching quantum computers fail, physicists will be VERY interested
(I would expect a Nobel prize for conclusive evidence of this)."
Consider, however, this scenario. With few q-bits, QC is eventually
made to work. The progress stops, though, long before QC factoring starts
competing with pencils. The QC people then demand some noble prize for
the correction to the Quantum Mechanics. But the committee wants more
specifics than simply a nonworking machine, so something like observing
the state of the QC is needed. Then they find the Universe too small
for observing individual states of the needed dimensions and accuracy.
(Raising sufficient funds to compete with pencil factoring
may justify a Nobel Prize in Economics.)
Let us make some calculations. In cryptography, the length $n$ of the
integers to factor may be a thousand bits (and could easily be millions.)
A $2^n$-dimensional space has [[ sets with double-exponential in $n$ ]]
nearly orthogonal vectors. The minimal size of a machine which can recognize
[[ (with some distance error) a given typical vector is exponential ]]
--- far larger than our Universe. This comes from a cardinality argument:
$2^{O(K)}$ machines of $K$ atoms. [[ Of course, some states are nicer,
with ways to distinguish them from all distant states.
But are there arguments for all Quantum Factoring states to be so nice? ]]
There is a big difference between untested and untestable regimes. Claims
about individual [[typical]] states are untestable. I can imagine a feasible
way to separate any two QC states from each other. Yet, as this
calculation shows, no machine can separate a [typical]] state from the set of
all states more distant from it than QC tolerates. So, what thought experiments
can probe the QC to be in the state described with the accuracy needed?
I would allow to use the resources of the entire Universe, but not more!
Archimedes made a great discovery that digital representation of
numbers is exponentially more efficient than analog ones (sand pile
sizes). Many subsequent analog devices yielded unimpressive results.
It is not clear why QCs should be an exception.
2.6. Metric versus Topology
A gap in quantum formalism may be contributing to the confusion.
Approximation has two subtly different aspects: metric and topology.
Metric tells how close our ideal point is to a specific wrong one.
Topology tells how close it is to the combination of all unacceptable
(non-neighboring) points. This may differ from the distance to
the closest unacceptable point, especially for quantum systems.
In infinite dimensions, the distinction between 0 and positive
separation between a point and a set varies with topologies. In finite
dimensions, 0-vs.-positive distinction is too coarse: all topologies
agree. Since $2^{500}$ is finite only in a very philosophical sense,
one needs a quantitative refinement, some sort of a weak-topological
(not metric) depth of a neighborhood polynomially related to
resources required for precision to a given depth. Then, precision to
reasonable depths would be physical, e.g., allow one to generate points
inside the neighborhood, distinguish its center from the outside, etc.
Metric defines $e$-neighborhoods and is richer in that than topology
where the specific value of $e$ is lost (only $e\gt0$ is assured).
However, metric is restricted by the axiom that the intersection
of any set of $e$-neighborhoods is always another $e$-neighborhood.
Quantum proximity may require both benefits: defined depth $e$ and
freedom to express it by formulas violating the "intersection axiom."
Here is an example of such a violation, without pretense of relevance
to our needs. Suppose a neighborhood of 0 is given by a set of linear
inequalities $(f_i\cdot x)\lt 1$; then its depth may be taken as
$1/\sum_i\|f_i\|$. Restricting $x$ to the unit sphere would render
this depth quadratically close to metric depth. A more relevant
formula may need preferred treatment of tensor product basis.
2.7. The Cheaper Boon
QC of the sort that factors long numbers seems firmly rooted in science
fiction. It is a pity that popular accounts do not distinguish it
from much more believable ideas, like Quantum Cryptography, Quantum
Communications, or the sort of Quantum Computing that deals primarily
with locality restrictions, such as fast search of long arrays.
It is worth noting that the reasons why QC must fail are by no means
clear; they merit thorough investigation. The answer may bring much
greater benefits in the understanding of basic physical concepts than
any benefits factoring devices could promise. The present attitude is
analogous to, say, Maxwell selling the Daemon of his famous thought
experiment as a path to cheaper electricity from heat. If he did,
much of insights of today's thermodynamics might be lost or delayed.
The rest of the article ignores any extravagant models and stands
fully committed to the Polynomial Overhead Church--Turing Thesis: Any
computation that takes $t$ steps on an $s$-bit device can be simulated by
a Turing Machine in $s^{O(1)}t$ steps within $s^{O(1)}$ cells.