Subject(s): CX.07, CX.09

Category: Reject

Abstract:

The lambda-q calculus as defined in your paper does not succeed in capturing the concept of a quantum generalization of the lambda calculus. Nor is your lambda-p calculus a probabilistic lambda calculus. In both cases the missing ingredient is the requirement that operations must preserve the appropriate norm. For lambda-p this would mean conservation of probability, and for lambda-q this would be the requirement that all operators (other than measurement) must be unitary. The most obvious manifestation of this is that a lambda-q expression can take a term with nonzero amplitude and produce one with zero amplitude (i.e. a term can evaluate to an empty set). The simplest example x.(-x,+x) is the reason all NP problems (and co-NP as well) are so easily solvable. In fact, SAT is also solvable in the same way in your lambda-p calculus, illustrating that it is not a good model of probabilistic computation. Proof: Consider the behavior of AMPLIFY-T == .x.IF x (POWER n x) x where POWER(n x) reduces to (x,x,..., 2^n copies ,...x) (a recursive definition has a depth of only n) Example: AMPLIFY-T 2 (F,T,F) -> (F,T,T,T,T,F) As long as the number of candidate solutions is much less than 2^N, applying AMPLIFY-T n to the results of CHECK_f will produce T with high probability iff f is satisfiable, just as REMOVE-F did for lambda-q.

Retrieve Manuscript Abstract

Submit referee report/comment