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

Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

Quantum ground–state computation with kinematical gates

Giuseppe Castagnoli, David Finkelstein

Published Nov 25, 2003• 3 citations
Publisher

Abstract

We develop a computation model for solving Boolean networks that implements wires dynamically through quantum ground–state computation and implements gates kinematically through identities following from angular–momentum algebra and statistics. The gates are extra–dynamical in the sense that they contribute nothing to the Hamiltonian and hold as constants of the motion; only the wires are dynamical. Just as a spin ½ makes an ideal 1–bit memory element, a spin 1 makes an ideal 3–bit gate. Such gates cost no computation time; relaxing the wires alone solves the network. We compare computation time heuristically with that of an easier Boolean network where all the gate constraints are simply removed. This computation model is robust with respect to decoherence and yields a generalized quantum speed–up for all NP (non–deterministic–polynomial) problems. We give an Ising model for such a logical network composed of spins of 1 with bilinear couplings.

DOI
10.1098/rspa.2003.1178

Related papers

Quantum ground-state computation with static gates

Giuseppe Castagnoli, David Finkelstein

We develop a computation model for solving Boolean networks that implements wires through quantum ground-state computation and implements gates through identities following from angular momentum algebra and statistics. The gates are static in the sense that they contribute Hamiltonian 0 and hold as constants of the motion; only the wires are dynamic. Just as a spin 1/2 makes an ideal 1-bit memory element, a spin 1 makes an ideal 3-bit gate. Such gates cost no computation time: relaxing the wires alone solves the network. We compare computation time with that of an easier Boolean network where all the gate constraints are simply removed. This computation model is robust with respect to decoherence and yields a generalized quantum speed-up for all NP problems.

arXiv:quant-ph/0209084•Sep 13, 2002•2 citations

Quantum ground-mode computation with static gates

Giuseppe Castagnoli, David Finkelstein

We develop a computation model for solving Boolean networks by implementing wires through quantum ground-mode computation and gates through identities following from angular momentum algebra and statistics. Gates are represented by three-dimensional (triplet) symmetries due to particle indistinguishability and are identically satisfied throughout computation being constants of the motion. The relaxation of the wires yields the network solutions. Such gates cost no computation time, which is comparable with that of an easier Boolean network where all the gate constraints implemented as constants of the motion are removed. This model computation is robust with respect to decoherence and yields a generalized quantum speed-up for all NP problems.

arXiv:quant-ph/0209169•CRC Press eBooks•Nov 30, 2003•0 citations

Computing Spin Networks

Annalisa Marzuoli, Mario Rasetti

We expand a set of notions recently introduced providing the general setting for a universal representation of the quantum structure on which quantum information stands. The dynamical evolution process associated with generic quantum information manipulation is based on the (re)coupling theory of SU(2) angular momenta. Such scheme automatically incorporates all the essential features that make quantum information encoding much more efficient than classical: it is fully discrete; it deals with inherently entangled states, naturally endowed with a tensor product structure; it allows for generic encoding patterns. The model proposed can be thought of as the non-Boolean generalization of the quantum circuit model, with unitary gates expressed in terms of 3nj coefficients connecting inequivalent binary coupling schemes of n+1 angular momentum variables, as well as Wigner rotations in the eigenspace of the total angular momentum. A crucial role is played by elementary j-gates (6j symbols) which satisfy algebraic identities that make the structure of the model similar to "state sum models", employed in discretizing Topological Quantum Field Theories and quantum gravity. The spin network simulator can thus be viewed also as a Combinatorial QFT model for computation. The semiclassical limit (large j's) is discussed.

•Jan 1, 2004•46 citations

Static Quantum Computation

Haiqing Wei, Xin Xue

Tailoring many-body interactions among a proper quantum system endows it with computing ability by means of static quantum computation in the sense that some of the physical degrees of freedom can be used to store binary information and the corresponding binary variables satisfy some given logic relations if and only if the system is in the ground state. Two theorems are proved showing that the universal static quantum computer can encode the solutions for any P and NP problem into its ground state using only polynomial number (in the problem input size) of logic gates. The second step is to read out the solutions by relaxing the system. The time complexity is relevant when one tries to read out the solution by relaxing the system, therefore our model of static quantum computation provides a new connection between the computational complexity and the dynamics of a complex system.

arXiv:quant-ph/9702046•Feb 22, 1997•3 citations

Elementary gates for quantum computation

Adriano Barenco, Charles H. Bennett, Richard Cleve +6 more

We show that a set of gates that consists of all one-bit quantum gates [U(2)] and the two-bit exclusive-OR gate [that maps Boolean values (x,y) to (x,x\ensuremath{\bigoplus}y)] is universal in the sense that all unitary operations on arbitrarily many bits n [U(${2}^{\mathit{n}}$)] can be expressed as compositions of these gates. We investigate the number of the above gates required to implement other gates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2) transformation to one input bit if and only if the logical and of all remaining input bits is satisfied. These gates play a central role in many proposed constructions of quantum computational networks. We derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two- and three-bit quantum gates, the asymptotic number required for n-bit Deutsch-Toffoli gates, and make some observations about the number required for arbitrary n-bit unitary operations.

arXiv:quant-ph/9503016•Physical Review A•Nov 1, 1995•4,309 citations

Quantum Circuits That Can Be Simulated Classically in Polynomial Time

Leslie Gabriel Valiant

A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 × 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. Therefore, it is possible that, The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent with one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.

SIAM Journal on Computing•Jan 1, 2002•310 citations
We develop a computation model for solving Boolean networks that implements wires dynamically through quantum ground–state computation and implements gates kinematically through identities following from angular–momentum algebra and statistics. The gates are extra–dynamical in the sense that they contribute nothing to the Hamiltonian and hold as constants of the motion; only the wires are dynamical. Just as a spin ½ makes an ideal 1–bit memory element, a spin 1 makes an ideal 3–bit gate. Such gates cost no computation time; relaxing the wires alone solves the network. We compare computation time heuristically with that of an easier Boolean network where all the gate constraints are simply removed. This computation model is robust with respect to decoherence and yields a generalized quantum speed–up for all NP (non–deterministic–polynomial) problems. We give an Ising model for such a logical network composed of spins of 1 with bilinear couplings.
We develop a computation model for solving Boolean networks that implements wires through quantum ground-state computation and implements gates through identities following from angular momentum algebra and statistics. The gates are static in the sense that they contribute Hamiltonian 0 and hold as constants of the motion; only the wires are dynamic. Just as a spin 1/2 makes an ideal 1-bit memory element, a spin 1 makes an ideal 3-bit gate. Such gates cost no computation time: relaxing the wires alone solves the network. We compare computation time with that of an easier Boolean network where all the gate constraints are simply removed. This computation model is robust with respect to decoherence and yields a generalized quantum speed-up for all NP problems.
We develop a computation model for solving Boolean networks by implementing wires through quantum ground-mode computation and gates through identities following from angular momentum algebra and statistics. Gates are represented by three-dimensional (triplet) symmetries due to particle indistinguishability and are identically satisfied throughout computation being constants of the motion. The relaxation of the wires yields the network solutions. Such gates cost no computation time, which is comparable with that of an easier Boolean network where all the gate constraints implemented as constants of the motion are removed. This model computation is robust with respect to decoherence and yields a generalized quantum speed-up for all NP problems.
We expand a set of notions recently introduced providing the general setting for a universal representation of the quantum structure on which quantum information stands. The dynamical evolution process associated with generic quantum information manipulation is based on the (re)coupling theory of SU(2) angular momenta. Such scheme automatically incorporates all the essential features that make quantum information encoding much more efficient than classical: it is fully discrete; it deals with inherently entangled states, naturally endowed with a tensor product structure; it allows for generic encoding patterns. The model proposed can be thought of as the non-Boolean generalization of the quantum circuit model, with unitary gates expressed in terms of 3nj coefficients connecting inequivalent binary coupling schemes of n+1 angular momentum variables, as well as Wigner rotations in the eigenspace of the total angular momentum. A crucial role is played by elementary j-gates (6j symbols) which satisfy algebraic identities that make the structure of the model similar to "state sum models", employed in discretizing Topological Quantum Field Theories and quantum gravity. The spin network simulator can thus be viewed also as a Combinatorial QFT model for computation. The semiclassical limit (large j's) is discussed.
Tailoring many-body interactions among a proper quantum system endows it with computing ability by means of static quantum computation in the sense that some of the physical degrees of freedom can be used to store binary information and the corresponding binary variables satisfy some given logic relations if and only if the system is in the ground state. Two theorems are proved showing that the universal static quantum computer can encode the solutions for any P and NP problem into its ground state using only polynomial number (in the problem input size) of logic gates. The second step is to read out the solutions by relaxing the system. The time complexity is relevant when one tries to read out the solution by relaxing the system, therefore our model of static quantum computation provides a new connection between the computational complexity and the dynamics of a complex system.
We show that a set of gates that consists of all one-bit quantum gates [U(2)] and the two-bit exclusive-OR gate [that maps Boolean values (x,y) to (x,x\ensuremath{\bigoplus}y)] is universal in the sense that all unitary operations on arbitrarily many bits n [U(2n{2}^{\mathit{n}}2n)] can be expressed as compositions of these gates. We investigate the number of the above gates required to implement other gates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2) transformation to one input bit if and only if the logical and of all remaining input bits is satisfied. These gates play a central role in many proposed constructions of quantum computational networks. We derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two- and three-bit quantum gates, the asymptotic number required for n-bit Deutsch-Toffoli gates, and make some observations about the number required for arbitrary n-bit unitary operations.
A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 × 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. Therefore, it is possible that, The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent with one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.