InterJournal Complex Systems, 512
Status: Accepted
Manuscript Number: [512]
Submission Date: 20424
Comment on manuscript revision number 42683
The lambda-q calculus is not quantum
Author(s): Ralph Hartley

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

Category: Reject


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

Public Comments: