Parallel quantum computation and quantum codes

DOI10.1137/S0097539799355053MaRDI QIDQ2784481zbMATH OpenFDO

Authors Cristopher Moore, Martin Nilsson

Publication date 23 April 2002

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/9808027

zbMATH Keywords

group theoryparallel computationquantum circuitsquantum complexity classesquantum error-correcting codes

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum computation (81P68)

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.

Recommendations

• EFFICIENT QUANTUM CIRCUITS FOR NON-QUBIT QUANTUM ERROR-CORRECTING CODES
• Parallelizing quantum circuits
• scientific article; zbMATH DE number 1583875
• scientific article; zbMATH DE number 1962817
• scientific article; zbMATH DE number 1504668

Cited in

(27)

• Parallelizing quantum circuits
• Quantum neural networks
• Towards implementation of a generalized architecture for high-level quantum programming language
• A proof system for disjoint parallel quantum programs
• Quantum random access stored-program machines
• Power of uninitialized qubits in shallow quantum circuits
• A quantum multiply-accumulator
• scientific article; zbMATH DE number 1583875 (Why is no real title available?)
• Fast quantum modular exponentiation
• scientific article; zbMATH DE number 7228448 (Why is no real title available?)
• Collapse of the hierarchy of constant-depth exact quantum circuits
• Depth-optimized reversible circuit synthesis
• Abelian networks IV. Dynamics of nonhalting networks
• A class of efficient quantum incrementer gates for quantum circuit synthesis
• Coping with decoherence: parallelizing the quantum Fourier transform
• On the need for large quantum depth
• Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems
• Quantum circuit completeness: extensions and simplifications
• Quantum algorithms for longest common and palindromic substrings in the circuit model
• Noisy decoding by shallow circuits with parities: classical and quantum (extended abstract)
• Adding concurrency to quantum dynamic logic
• Minimum synthesis cost of CNOT circuits
• A new quantum oracle model for a hybrid quantum-classical attack on post-quantum lattice-based cryptosystems
• The improved quantum switching mechanism based on contention
• A general quantum circuit for string matching: unleashing quantum path parallelism
• Quantum programming in polylogarithmic time
• Nearly optimal circuit size for sparse quantum state preparation

This page was built for publication: Parallel quantum computation and quantum codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784481)