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•32 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•13 citations

Digital representation of continuous observables in quantum mechanics

M. G. Ivanov, A. Yu. Polushkin

To simulate quantum systems on classical or quantum computers, the continuous observables (e.g., coordinate and momentum or energy and time) must be reduced to discrete ones. In this paper, we consider the continuous observables represented in the positional systems as power series in the radix multiplied over the summands (“digits”), which turn out to be Hermitian operators with discrete spectrum. We investigate the obtained quantum mechanical operators of digits, the commutation relations between them, and the effects of the choice of a numeral system on lattices and representations. Renormalizations of diverging sums naturally occur in constructing the digital representation.

Theoretical and Mathematical Physics•Mar 1, 2024•2 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•7 citations

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

Quantum Simulation

S. Rajasekar, R. Velusamy

This chapter points out the limitations in simulating quantum systems in classical computers. It describes the various stages of quantum simulation using quantum computers and relevant quantum circuits. Quantum simulators are classified into two types: analog quantum simulators and digital quantum simulators. In an analog quantum simulator the physical properties of a targeted model are reproduced on a physical set-up under externally controlled conditions. Quantum simulation will be considered successful only if the initial state preparation, the implementation of the time evolution and the measurements of observables are realized using only polynomial resources. The chapter discusses the quantum circuits for measurement of the dynamical correlation functions and the spectrum of the Hermitian operators. Computing the time evolution operator is equivalent to the task of implementing a unitary matrix and any unitary transformation can be done in a quantum computer using a universal set of quantum gates.

CRC Press eBooks•Oct 5, 2022•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.
To simulate quantum systems on classical or quantum computers, the continuous observables (e.g., coordinate and momentum or energy and time) must be reduced to discrete ones. In this paper, we consider the continuous observables represented in the positional systems as power series in the radix multiplied over the summands (“digits”), which turn out to be Hermitian operators with discrete spectrum. We investigate the obtained quantum mechanical operators of digits, the commutation relations between them, and the effects of the choice of a numeral system on lattices and representations. Renormalizations of diverging sums naturally occur in constructing the digital representation.
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.
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.
This chapter points out the limitations in simulating quantum systems in classical computers. It describes the various stages of quantum simulation using quantum computers and relevant quantum circuits. Quantum simulators are classified into two types: analog quantum simulators and digital quantum simulators. In an analog quantum simulator the physical properties of a targeted model are reproduced on a physical set-up under externally controlled conditions. Quantum simulation will be considered successful only if the initial state preparation, the implementation of the time evolution and the measurements of observables are realized using only polynomial resources. The chapter discusses the quantum circuits for measurement of the dynamical correlation functions and the spectrum of the Hermitian operators. Computing the time evolution operator is equivalent to the task of implementing a unitary matrix and any unitary transformation can be done in a quantum computer using a universal set of quantum gates.