Developing and expanding on the idea by Moore and Nilsson [1], we provide a detailed description of families of logspace uniform quantum circuits that implement cyclic shifts and permutations of qubits. This allows us to formally prove that such operations belong to QNC0, the quantum analogue of the complexity class NC0, which captures highly efficiently parallelizable classical computations.

Faro S., Pavone A., Viola C. (2024). Families of Constant-Depth Quantum Circuits for Rotations and Permutations. In U. de'Liguoro, M. Palazzo, L. Roversi (a cura di), Proceedings of the 25th Italian Conference on Theoretical Computer Science (pp. 29-41). CEUR-WS.

Families of Constant-Depth Quantum Circuits for Rotations and Permutations

Pavone A.;
2024-01-01

Abstract

Developing and expanding on the idea by Moore and Nilsson [1], we provide a detailed description of families of logspace uniform quantum circuits that implement cyclic shifts and permutations of qubits. This allows us to formally prove that such operations belong to QNC0, the quantum analogue of the complexity class NC0, which captures highly efficiently parallelizable classical computations.
2024
Settore INFO-01/A - Informatica
Faro S., Pavone A., Viola C. (2024). Families of Constant-Depth Quantum Circuits for Rotations and Permutations. In U. de'Liguoro, M. Palazzo, L. Roversi (a cura di), Proceedings of the 25th Italian Conference on Theoretical Computer Science (pp. 29-41). CEUR-WS.
File in questo prodotto:
File Dimensione Formato  
ICTCS_2024_paper_24-2.pdf

accesso aperto

Tipologia: Versione Editoriale
Dimensione 879.47 kB
Formato Adobe PDF
879.47 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/667093
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact