Two arithmetic formulas and

PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch What quantum computers can compute efficiently

Problem

Two arithmetic formulas

F

and

G

, each of size polynomial in the number of variables

n

, are given. A randomised algorithm decides whether

F

and

G

compute the same polynomial by evaluating both at a single point chosen uniformly at random from a set of size at least

3d

, where

d

bounds the total degree of

F-G

(at most the larger formula size, so polynomial in

n

), and answering "equal" if and only if the two values agree; when

F\ne G

, the point is a root of

F-G

with probability at most

1/3

, so a wrong "equal" answer occurs with probability at most

1/3

, while a wrong "not equal" answer never occurs. Each evaluation takes time polynomial in

n

. ((a)) Say which of

\mathrm{P}

\mathrm{NP}

\mathrm{BPP}

\mathrm{PSPACE}

and

\mathrm{BQP}

this algorithm places the identity-testing problem in, and why, quoting the definition it matches. ((b)) State one class the problem is therefore also inside, using a containment proved earlier, and one class it is not known to be inside.

Browse the problem library