|
related topics |
{qubit, qubits, gate} |
{let, theorem, proof} |
{algorithm, log, probability} |
{error, code, errors} |
{operator, operators, space} |
{group, space, representation} |
{entanglement, phys, rev} |
{states, state, optimal} |
|
Parallel Quantum Computation and Quantum Codes
Cristopher Moore, Martin Nilsson
abstract: We propose a definition of QNC, the quantum analog of the efficient parallel
class NC. We exhibit several useful gadgets and prove that various classes of
circuits can be parallelized to logarithmic depth, including circuits for
encoding and decoding standard quantum error-correcting codes, or more
generally any circuit consisting of controlled-not gates, controlled pi-shifts,
and Hadamard gates. Finally, while we note the Quantum Fourier Transform can be
parallelized to linear depth, we conjecture that an even simpler `staircase'
circuit cannot be parallelized to less than linear depth, and might be used to
prove that QNC < QP.
- oai_identifier:
- oai:arXiv.org:quant-ph/9808027
- categories:
- quant-ph math.QA
- arxiv_id:
- quant-ph/9808027
- created:
- 1998-08-17
Full article ▸
|
|
related documents |
0304061v5 |
0407095v1 |
0410001v3 |
0207157v1 |
0104085v1 |
0311069v1 |
0304054v2 |
9908074v5 |
0012067v1 |
0305038v2 |
9909082v1 |
9903101v2 |
0408081v5 |
0308167v1 |
0305134v1 |
0506062v2 |
0303175v1 |
0304078v1 |
0003137v2 |
0702212v1 |
0610105v1 |
0511041v1 |
0312083v1 |
0109016v2 |
0504197v1 |
|