Constant-Depth Exact Quantum Circuits for the OR and Threshold Functions

Details Constant-Depth Exact Quantum Circuits for the OR and Threshold Functions Constant-Depth Exact Quantum Circuits for the OR and Threshold Functions

2011-12-28

arxiv.org/abs/1112.6063v1

Physics

Quantum Physics

17 pages, 4 figures

Scientific paper

We investigate the computational power of constant-depth polynomial-size quantum circuits with unbounded fan-out gates in the exact setting, where quantum circuits output the correct answer with certainty. We show that there exists an O(1)-depth O(n log n)-size quantum circuit for the OR function on n bits. This is an affirmative answer to the question of Hoyer and Spalek and implies that QNC^0_f=QAC^0_f in contrast to the fact that NC^0 \subsetneq AC^0, where QNC^0_f and QAC^0_f are the quantum circuit complexity classes corresponding to the classical ones NC^0 and AC^0, respectively. We also show that there exists an O(1)-depth small-size quantum circuit for the threshold function on n bits with a threshold 1 \leq t \leq n, where the size is O(n log n) when t is close to 1 or n, and it is O(n sqrt{n log n}) when t is around n/2.

Affiliated with

Also associated with

No associations

Rating

Constant-Depth Exact Quantum Circuits for the OR and Threshold Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Constant-Depth Exact Quantum Circuits for the OR and Threshold Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constant-Depth Exact Quantum Circuits for the OR and Threshold Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-32169