Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Strutture Algebriche nella Computazione Quantistica

Maria L. Dalla Chiara, Giuseppe Sergioli

Published Jan 1, 2011• 0 citations
OpenAlex

Abstract

Shi and Aharonov have shown that the Toffoli gate and the Hadamard gate give rise to an approximately universal set of quantum computational gates. We study the basic algebraic properties of this system by introducing the notion of Shi-Abaronov quantum computational structure. Finally, we investigate the possibility of an algebraic abstraction from Hilbert-space structures, by proposing the notion of Toffoli-Hadamard algebra. From an intuitive point of view, such abstract algebras represent a natural quantum generalization of both classical and fuzzy-like structures.

Related papers

A Simple Proof that Toffoli and Hadamard are Quantum Universal

Dorit Aharonov

Recently Shi proved that Toffoli and Hadamard are universal for quantum computation. This is perhaps the simplest universal set of gates that one can hope for, conceptually; It shows that one only needs to add the Hadamard gate to make a 'classical' set of gates quantum universal. In this note we give a few lines proof of this fact relying on Kitaev's universal set of gates, and discuss the meaning of the result.

arXiv:quant-ph/0301040•Jan 9, 2003•122 citations

Probability in quantum computation and quantum computational logics: a survey

María Luisa Dalla Chiara, Roberto Giuntini, Giuseppe Sergioli

Quantum computation and quantum computational logics give rise to some non-standard probability spaces that are interesting from a formal point of view. In this framework, events represent quantum pieces of information (qubits, quregisters, mixtures of quregisters), while operations on events are identified with quantum logic gates (which correspond to dynamic reversible quantum processes). We investigate the notion of Shi–Aharonov quantum computational algebra. This structure plays the role for quantum computation that is played by σ-complete Boolean algebras in classical probability theory.

Mathematical Structures in Computer Science•Mar 28, 2014•6 citations

The Qudit ZH-Calculus: Generalised Toffoli+Hadamard and Universality

Patrick Roy, John van de Wetering, Lia Yeh

We introduce the qudit ZH-calculus and show how to generalise the phase-free qubit rules to qudits.We prove that for prime dimensions d, the phase-free qudit ZH-calculus is universal for matrices over the ring Z[e 2πi/d ].For qubits, there is a strong connection between phase-free ZH-diagrams and Toffoli+Hadamard circuits, a computationally universal fragment of quantum circuits.We generalise this connection to qudits, by finding that the two-qudit |0 -controlled X gate can be used to construct all classical reversible qudit logic circuits in any odd qudit dimension, which for qubits requires the three-qubit Toffoli gate.We prove that our construction is asymptotically optimal up to a logarithmic term.Twenty years after the celebrated result by Shi proving universality of Toffoli+Hadamard for qubits, we prove that circuits of |0 -controlled X and Hadamard gates are approximately universal for qudit quantum computing for any odd prime d, and moreover that phase-free ZH-diagrams correspond precisely to such circuits allowing postselections.

arXiv:2307.10095•Electronic Proceedings in Theoretical Computer Science•Aug 23, 2023•8 citations

RESEARCH ARTICLE Some generalizations of fuzzy structures in quantum computational logic

Roberto Giuntini, Antonio Ledda, Giuseppe Sergioli +1 more

Quantum computational logics provide a fertile common ground for a unied treatment of vagueness and uncertainty. In this paper we describe an approach to the logic of quantum computation that has been recently taken up and developed by the present authors. Special attention will be devoted to a generalisation of Chang's MV algebras (called quasi-MV alge- bra) which abstracts over the algebra whose universe is the set of qumixes of the 2-dimensional complex Hilbert space, as well as to its expansions by additional quantum connectives. We fur- thermore explore some future research perspectives, also in the light of some recent limitative results whose general signicance will be duly assessed.

•Jan 1, 2009•0 citations

Elementary gates for cartoon computation

Marek Czachor

The basic one-bit gates (X, Y, Z, Hadamard, phase, π/8) as well as the controlled CNOT and Toffoli gates are reformulated in the language of geometric-algebra quantum-like computation. Thus, all the quantum algorithms can be reformulated in purely geometric terms without any need of tensor products.

•Jan 1, 2007•9 citations

Elementary gates for cartoon computation

Marek Czachor

The basic one-bit gates ( X , Y , Z , Hadamard, phase, π/8) as well as the controlled CNOT and Toffoli gates are reformulated in the language of geometric-algebra quantum-like computation. Thus, all the quantum algorithms can be reformulated in purely geometric terms without any need of tensor products.

arXiv:0706.0967•Journal of Physics A Mathematical and Theoretical•Jul 19, 2007•7 citations
Shi and Aharonov have shown that the Toffoli gate and the Hadamard gate give rise to an approximately universal set of quantum computational gates. We study the basic algebraic properties of this system by introducing the notion of Shi-Abaronov quantum computational structure. Finally, we investigate the possibility of an algebraic abstraction from Hilbert-space structures, by proposing the notion of Toffoli-Hadamard algebra. From an intuitive point of view, such abstract algebras represent a natural quantum generalization of both classical and fuzzy-like structures.
Quantum computation and quantum computational logics give rise to some non-standard probability spaces that are interesting from a formal point of view. In this framework, events represent quantum pieces of information (qubits, quregisters, mixtures of quregisters), while operations on events are identified with quantum logic gates (which correspond to dynamic reversible quantum processes). We investigate the notion of Shi–Aharonov quantum computational algebra. This structure plays the role for quantum computation that is played by σ-complete Boolean algebras in classical probability theory.
We introduce the qudit ZH-calculus and show how to generalise the phase-free qubit rules to qudits.We prove that for prime dimensions d, the phase-free qudit ZH-calculus is universal for matrices over the ring Z[e 2πi/d ].For qubits, there is a strong connection between phase-free ZH-diagrams and Toffoli+Hadamard circuits, a computationally universal fragment of quantum circuits.We generalise this connection to qudits, by finding that the two-qudit |0 -controlled X gate can be used to construct all classical reversible qudit logic circuits in any odd qudit dimension, which for qubits requires the three-qubit Toffoli gate.We prove that our construction is asymptotically optimal up to a logarithmic term.Twenty years after the celebrated result by Shi proving universality of Toffoli+Hadamard for qubits, we prove that circuits of |0 -controlled X and Hadamard gates are approximately universal for qudit quantum computing for any odd prime d, and moreover that phase-free ZH-diagrams correspond precisely to such circuits allowing postselections.
Quantum computational logics provide a fertile common ground for a unied treatment of vagueness and uncertainty. In this paper we describe an approach to the logic of quantum computation that has been recently taken up and developed by the present authors. Special attention will be devoted to a generalisation of Chang's MV algebras (called quasi-MV alge- bra) which abstracts over the algebra whose universe is the set of qumixes of the 2-dimensional complex Hilbert space, as well as to its expansions by additional quantum connectives. We fur- thermore explore some future research perspectives, also in the light of some recent limitative results whose general signicance will be duly assessed.