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

parallel computationgroup theoryquantum error-correcting codesquantum circuitsquantum complexity classes

Mathematics Subject Classification ID

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

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

(25)

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

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)