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 |
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 |