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

Journal of Modern Optics

Necessary and Sufficient Conditions for Quantum Computation

Seth Lloyd

Published Dec 1, 1994• 19 citations
Publisher

Abstract

Necessary and sufficient conditions are given for a quantummechanical system to possess a coordinate system with respect to which its behaviour at discrete times is that of a universal digital computer. The form of the diagonal representation for the unitary time evolution operator for quantum universal computers is derived; aspects of the transformation between the diagonal representation and the computational representation are shown to be uncomputable. A quantum-mechanical treatment of macroscopic, dissipative computers is given.

DOI
10.1080/09500349414552341

Related papers

Quantum-mechanical computers and uncomputability

Seth Lloyd

The time evolution operator for any quantum-mechanical computer is diagonalizable, but to obtain the diagonal decomposition of a program state of the computer is as hard as actually performing the computation corresponding to the program. In particular, if a quantum-mechanical system is capable of universal computation, then the diagonal decomposition of program states is uncomputable. As a result, in a universe in which local variables support universal computation, a quantum-mechanical theory for that universe that supplies its spectrum cannot supply the spectral decomposition of the computational variables. A ``theory of everything'' can be simultaneously correct and fundamentally incomplete.

Physical Review Letters•Aug 9, 1993•31 citations

Universal construction of unitary transformation of quantum computation with one- and two-body interactions

Xijia Miao

Any unitary transformation of quantum computational networks is explicitly decomposed, in an exact and unified form, into a sequence of a limited number of one-qubit quantum gates and the two-qubit diagonal gates that have diagonal unitary representation in usual computational basis. This decomposition may be simplified greatly with the help of the properties of the finite-dimensional multiple-quantum operator algebra spaces of a quantum system and the specific properties of a given quantum algorithm. As elementary building blocks of quantum computation, the two-qubit diagonal gates and one-qubit gates may be constructed physically with one- and two-body interactions in a two-state quantum system and hence could be conveniently realized experimentally. The present work will be helpful for implementing generally any N-qubit quantum computation in those feasible two-state quantum systems and determining conveniently the time evolution of these systems in course of quantum computation.

arXiv:quant-ph/0003068•Mar 17, 2000•6 citations

Conditions for unitarity in timeless quantum theory

Anonymous

Quantum timeless approaches solve the problem of time by recovering the usual unitary evolution of quantum theory relative to a clock in a stationary quantum universe. For some Hamiltonians of the universe, such as those including an interaction term with the clock, the dynamics is substantially altered and can be nonunitary. This work derives necessary and sufficient conditions for the relative dynamics to be unitary and finds the general form of the unitary evolution operator. A physical interpretation of these conditions is given in terms of the clock’s rate. Unitary dynamics is associated with rates that are constant in time and independent of the clock’s internal structure.

arXiv:2504.01579•Physical review. D/Physical review. D.•Jun 18, 2026•0 citations

Digital representation of continuous observables in Quantum Mechanics

M. G. Ivanov, A. Yu. Polushkin

To simulate the quantum systems at classical or quantum computers, it is necessary to reduce continuous observables (e.g. coordinate and momentum or energy and time) to discrete ones. In this work we consider the continuous observables represented in the positional systems as a series of powers of the radix mulitplied over the summands (``digits``), which turn out to be Hermitean operators with discrete spectrum. We investigate the obtained quantum mechanical operators of digits, the commutation relations between them and the effects of choice of numeral system on the lattices and representations. Furthermore, during the construction of the digital representation renormalizations of diverging sums naturally occur.

arXiv:2301.09348•Jan 23, 2023•1 citation

The quantum computer condition: requirements for viable computation

Gerald N. Gilbert, Michael Hamrick, F. Javier Thayer +1 more

In this paper we review the content of the Quantum Computer Condition, which is a rigorously specified criterion that provides a set of mathematical constraints that must be satisfied by a physical system if we intend to use that system as a quantum computing machine, and we discuss an important consequence of it known as the Quantum Computing No-Go Theorem, which establishes a bound for decoherence and dissipation beyond which quantum computation is not possible. In connection with this theorem, we explicitly calculate a universal critical damping value for fault-tolerant quantum computation. We also discuss a relevant class of time-dependent generalizations of the Lindblad equation.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 5, 2006•0 citations

Non-degenerate Ground State of the Spin-Boson Model under Abelian Diagonalization

Liu, Tao, Juhao Wu, Ying, Mark

By utilizing a unitary transformation, we derive the necessary and sufficient conditions for the degeneracy between the even- and odd-parity energy states of the spin-boson model (SBM). Employing the Rayleigh quotient of matrix algebra, we rigorously prove that the ground state energy of the SBM is lower than the systems lowest possible degenerate energy and possesses a definite parity. Based on the necessary and sufficient conditions for parity breaking, we provide an analytical expression for the parity-breaking critical value, which is closely related to the expansion order and computational accuracy. This expression reproduces the SBM phase diagram obtained by quantum Monte Carlo (QMC) and logarithmic discretization numerical renormalization group (NRG) methods. However, this phase diagram does not characterize the ground state of the system.

arXiv:2506.14818•Jun 9, 2025•0 citations
Necessary and sufficient conditions are given for a quantummechanical system to possess a coordinate system with respect to which its behaviour at discrete times is that of a universal digital computer. The form of the diagonal representation for the unitary time evolution operator for quantum universal computers is derived; aspects of the transformation between the diagonal representation and the computational representation are shown to be uncomputable. A quantum-mechanical treatment of macroscopic, dissipative computers is given.
The time evolution operator for any quantum-mechanical computer is diagonalizable, but to obtain the diagonal decomposition of a program state of the computer is as hard as actually performing the computation corresponding to the program. In particular, if a quantum-mechanical system is capable of universal computation, then the diagonal decomposition of program states is uncomputable. As a result, in a universe in which local variables support universal computation, a quantum-mechanical theory for that universe that supplies its spectrum cannot supply the spectral decomposition of the computational variables. A ``theory of everything'' can be simultaneously correct and fundamentally incomplete.
Any unitary transformation of quantum computational networks is explicitly decomposed, in an exact and unified form, into a sequence of a limited number of one-qubit quantum gates and the two-qubit diagonal gates that have diagonal unitary representation in usual computational basis. This decomposition may be simplified greatly with the help of the properties of the finite-dimensional multiple-quantum operator algebra spaces of a quantum system and the specific properties of a given quantum algorithm. As elementary building blocks of quantum computation, the two-qubit diagonal gates and one-qubit gates may be constructed physically with one- and two-body interactions in a two-state quantum system and hence could be conveniently realized experimentally. The present work will be helpful for implementing generally any N-qubit quantum computation in those feasible two-state quantum systems and determining conveniently the time evolution of these systems in course of quantum computation.
Quantum timeless approaches solve the problem of time by recovering the usual unitary evolution of quantum theory relative to a clock in a stationary quantum universe. For some Hamiltonians of the universe, such as those including an interaction term with the clock, the dynamics is substantially altered and can be nonunitary. This work derives necessary and sufficient conditions for the relative dynamics to be unitary and finds the general form of the unitary evolution operator. A physical interpretation of these conditions is given in terms of the clock’s rate. Unitary dynamics is associated with rates that are constant in time and independent of the clock’s internal structure.
To simulate the quantum systems at classical or quantum computers, it is necessary to reduce continuous observables (e.g. coordinate and momentum or energy and time) to discrete ones. In this work we consider the continuous observables represented in the positional systems as a series of powers of the radix mulitplied over the summands (``digits``), which turn out to be Hermitean operators with discrete spectrum. We investigate the obtained quantum mechanical operators of digits, the commutation relations between them and the effects of choice of numeral system on the lattices and representations. Furthermore, during the construction of the digital representation renormalizations of diverging sums naturally occur.
In this paper we review the content of the Quantum Computer Condition, which is a rigorously specified criterion that provides a set of mathematical constraints that must be satisfied by a physical system if we intend to use that system as a quantum computing machine, and we discuss an important consequence of it known as the Quantum Computing No-Go Theorem, which establishes a bound for decoherence and dissipation beyond which quantum computation is not possible. In connection with this theorem, we explicitly calculate a universal critical damping value for fault-tolerant quantum computation. We also discuss a relevant class of time-dependent generalizations of the Lindblad equation.
By utilizing a unitary transformation, we derive the necessary and sufficient conditions for the degeneracy between the even- and odd-parity energy states of the spin-boson model (SBM). Employing the Rayleigh quotient of matrix algebra, we rigorously prove that the ground state energy of the SBM is lower than the systems lowest possible degenerate energy and possesses a definite parity. Based on the necessary and sufficient conditions for parity breaking, we provide an analytical expression for the parity-breaking critical value, which is closely related to the expansion order and computational accuracy. This expression reproduces the SBM phase diagram obtained by quantum Monte Carlo (QMC) and logarithmic discretization numerical renormalization group (NRG) methods. However, this phase diagram does not characterize the ground state of the system.