P != PSPACE ? and quantum computing

From: Dalibor Hrg (dalix_at_fly.srk.fer.hr)
Date: 04/19/04 

Date: Mon, 19 Apr 2004 22:52:13 +0200

Hi!

Well, I have a question about P/PSPACE problem and Deutsch-Jozsa algorithm.

Deutsch-Jozsa algorithm is a first and most simple algorithm among all
quantum algorithms. It is a problem of finding the global property of some
Boolean function of N variables. The problem requires on a classical
computer O(2^N) steps and on a quantum computer only O(N)steps. The problem
is not in P, it is in BQP which is subset of PSPACE. In this O(N) steps, the
oracle is applied only once on N qubits. Since, it is the Oracle kind of
algorithm, in literature it is written that because of this, the algorithm
can not be the proof for P!=PSPACE.

Meaning, we do not know the complexity of calculating the function in some
argument in the oracle?

What if we take that the function is really simple and requires poly number
of quantum circuits! With this assumption, we have P!=PSPACE? On classical
computer the problem with the same assumption is still not in P! On the
other side, for all other functions, we can't say if P!=PSPACE! I must say
that I'm little confused with oracles and their impact on some theoretical
questions. How important are oracles and which classical algorithms use them
for some proofs or something?

Best, D.Hrg.

Relevant Pages

  • Re: Questioning the existence of an oracle A whereby P^A =/= NP^A
    ... way of thinking is that I assume that an Oracle has to be a computable ... but there should be an algorithm that can recognize all ... in finite time doesn't mean that we can't prove that the machine exists. ... supposed to be an infinite sequence of steps that *A itself had to execute*. ...
    (comp.theory)
  • Re: chaining algorithms together
    ... As mentioned, we can quantify strength. ... An algorithm which requires an oracle is called an /oracle ... SE be a symmetric encryption algorithm. ...
    (sci.crypt)
  • http://www.phenoelit.net/lablog/oracle.sl wrote
    ... CEO of Red Database Security GmbH and Oracle ... Oracle Database 11g for Linux with a new password hashing algorithm. ... dynamically by other executables shipped with Oracle 11g, ...
    (comp.databases.oracle.server)
  • Re: Python from Wise Guys Viewpoint
    ... > The programming task is as follows: given a training set of incoming email that ... > the oracle has already correctly categorized, construct an algorithm that will ... > has an operational component (evaluation of correctness requires running a ...
    (comp.lang.lisp)
  • Re: Algorithm to create an encrypted Oracle password
    ... do you know an algorithm for me, which is able to encrypt passwords, ... limitation in Oracle and the algorithm should not produce ... an encrypted password longer than 30 characters, ... password is less than or equals 30 characters. ...
    (comp.databases.oracle.misc)