Skip navigation
Skip navigation

Computational Power of Quantum Machines, Quantum Grammars and Feasible Computation

Krishnamurthy, E.Vikram

Description

This paper studies the computational power of quantum computers to explore as to whether they can recognize properties which are in nondeterministic polynomial-time class (NP) and beyond. To study the computational power, we use the Feynman's path integral (FPI) formulation of quantum mechanics. From a computational point of view the Feynman's path integral computes a quantum dynamical analogue of the k-ary relation computed by an Alternating Turing machine (ATM) using AND-OR Parallelism....[Show more]

dc.contributor.authorKrishnamurthy, E.Vikram
dc.date.accessioned2015-12-13T23:35:22Z
dc.date.available2015-12-13T23:35:22Z
dc.identifier.issn0129-1831
dc.identifier.urihttp://hdl.handle.net/1885/93881
dc.description.abstractThis paper studies the computational power of quantum computers to explore as to whether they can recognize properties which are in nondeterministic polynomial-time class (NP) and beyond. To study the computational power, we use the Feynman's path integral (FPI) formulation of quantum mechanics. From a computational point of view the Feynman's path integral computes a quantum dynamical analogue of the k-ary relation computed by an Alternating Turing machine (ATM) using AND-OR Parallelism. Hence, if we can find a suitable mapping function between an instance of a mathematical problem and the corresponding interference problem, using suitable potential functions for which FPI can be integrated exactly, the computational power of a quantum computer can be bounded to that of an alternating Turing machine that can solve problems in NP (e.g, factorization problem) and in polynomial space. Unfortunately, FPI is exactly integrable only for a few problems (e.g., the harmonic oscillator) involving quadratic potentials; otherwise, they may be only approximately computable or noncomputable. This means we cannot in general solve all quantum dynamical problems exactly except for those special cases of quadratic potentials, e.g., harmonic oscillator. Since there is a one to one correspondence between the quantum mechanical problems that can be analytically solved and the path integrals that can be exactly evaluated, we can say that the noncomputability of FPI implies quantum unsolvability. This is the analogue of classical unsolvability. The Feynman's path graph can be considered as a semantic parse graph for the quantum mechanical sentence. It provides a semantic valuation function of the terminal sentence based on probability amplitudes to disambiguate a given quantum description and obtain an interpretation in a linear time. In Feynman's path integral, the kernels are partially ordered over time (different alternate paths acting concurrently at the same time) and multiplied. The semantic valuation is computable only if the FPI is computable. Thus both the expressive power and complexity aspects quantum computing are mirrored by the exact and efficient integrability of FPI.
dc.publisherWorld Scientific Publishing Company
dc.sourceInternational Journal of Modern Physics C: Physics and Computers
dc.subjectKeywords: Alternating Turing Machine (ATM); Complexity; Feynman Path Integral (FPI); Integrability; Partition Function (PF); Pfaffian; Quantum Computation; Transitive Closure
dc.titleComputational Power of Quantum Machines, Quantum Grammars and Feasible Computation
dc.typeJournal article
local.description.notesImported from ARIES
local.description.refereedYes
local.identifier.citationvolume9(2)
dc.date.issued1999
local.identifier.absfor020604 - Quantum Optics
local.identifier.ariespublicationMigratedxPub25310
local.type.statusPublished Version
local.contributor.affiliationKrishnamurthy, E.Vikram, College of Engineering and Computer Science, ANU
local.bibliographicCitation.startpage213
local.bibliographicCitation.lastpage241
dc.date.updated2015-12-12T09:39:41Z
local.identifier.scopusID2-s2.0-0032386807
CollectionsANU Research Publications

Download

There are no files associated with this item.


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  22 January 2019/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator