A Boolean circuit has input wires

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

A Boolean circuit

C

has

n

input wires, built from AND, OR and NOT gates, and one output wire. The decision problem CIRCUIT-SAT asks: given

C

, is there an input assignment that makes the output wire equal

1

? ((a)) Show that CIRCUIT-SAT has a certificate that can be checked in time polynomial in the size of

C

, and say which class this places it in. ((b)) Given that satisfiability of Boolean formulas is

\mathrm{NP}

-complete, and that every Boolean formula is already a Boolean circuit of comparable size, state the strongest classification of CIRCUIT-SAT among

\mathrm{P}

\mathrm{NP}

\mathrm{BPP}

\mathrm{PSPACE}

and

\mathrm{BQP}

that the definitions justify, and say which of the remaining classes it is proved to sit inside regardless.

Browse the problem library