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

Foundations of Software Technology and Theoretical Computer Science

Analysis of Quantum Functions (Preliminary Version)

Tomoyuki Yamakami

Published Dec 13, 1999• 2 citations
OpenAlex

Abstract

Abstract. Quantum functions are functions that are defined in terms of quantum mechanical computation. Besides quantum computable functions, we study quantum probability functions, which compute the acceptance probability of quantum computation. We also investigate quantum gap functions, which compute the gap between acceptance and rejection probabilities of quantum computation. 1

Related papers

Analysis of Quantum Functions

Tomoyuki Yamakami

This paper initiates a systematic study of quantum functions, which are (partial) functions defined in terms of quantum mechanical computations. Of all quantum functions, we focus on resource-bounded quantum functions whose inputs are classical bit strings. We prove complexity-theoretical properties and unique characteristics of these quantum functions by recent techniques developed for the analysis of quantum computations. We also discuss relativized quantum functions that make adaptive and nonadaptive oracle queries.

arXiv:quant-ph/9909012•Sep 2, 1999•0 citations

ANALYSIS OF QUANTUM FUNCTIONS

Tomoyuki Yamakami

This paper initiates a systematic study of quantum functions, which are (partial) functions defined in terms of quantum mechanical computations. Of all quantum functions, we focus on resource-bounded quantum functions whose inputs are classical bit strings. We prove complexity-theoretical properties and unique characteristics of these quantum functions by recent techniques developed for the analysis of quantum computations. We also discuss relativized quantum functions that make adaptive and nonadaptive oracle queries.

International Journal of Foundations of Computer Science•Oct 1, 2003•17 citations

Bell’s theorem and local reality

Jim Baggott

Abstract If we reject the ‘spooky’ action at a distance that seems to be required in the Copenhagen interpretation of quantum theory, and which is highlighted by the EPR thought experiment, we must accept the EPR argument that the theory is somehow incomplete. In essence, this involves the rejection of the first postulate of quantum theory: the state of a quantum mechanical system is not completely described by the wave function or state vector.Einstein had hinted at a statistical interpretation. In his opinion, the squares of the wave functions or state vectors of quantum theory represented statistical probabilities obtained by averaging over a large number of real particles. The Copenhagen interpretation of the EPR experiment insists that the reality of the physical states that can be measured is defined by the nature of the interaction between two quantum particles and the nature of the experimental arrangement. A completely deterministic, locally real version of quantum theory demands that the physical states of the particles be established at the moment of their interaction and that the particles separate as individually real entities in those physical states. The physical states of the particles are prescribed by the physics of their interaction and independent of how we choose to set up the measuring instrument, and so no reference to the nature of the latter is necessary, except to define how the independently real particles interact with it. The instrument thus probes an observer-independent reality.

•Nov 6, 2003•0 citations

Analyzing Algebraic Quantum Circuits Using Exponential Sums

Dave BaconWim van Dam, Alexander C. Russell

We introduce and analyze circuits that are the quantum mechanical generalization of classical algebraic circuits. Using the algebraic operations of addition and multiplication, as well as the quantum Fourier transform, such circuits are well-defined for rings Z=mZ and finite fields Fq. The acceptance probabilities of such algebraic quantum circuits can be expressed as exponential sums Âx exp(2pi f(x)=m) where the multivariate polynomial f is determined by the circuit, while it is independent of the ring or field over which we interpret the circuit. Dawson et al. [Quantum Information & Computation, 5(2), pp. 102‐112 (2004)] introduced this “sum over paths” description as a discrete version of the path integral approach of standard quantum mechanics. From this perspective, the polynomial f should be interpreted as the “action” of a specific (classical) computational path between the input and output of the circuit. In this article we prove several properties of algebraic quantum circuits. Using the theory of exponential sums, we show that in the limit of large m or q, the acceptance probabilities of a circuit converge to zero or to one. Circuits that do not involve the multiplication operation are the algebraic generalization of Clifford circuits and we show how their acceptance probabilities can be calculated exactly in a classical efficient manner. For algebraic circuits that are defined over rings Z=p r Z we derive a “least action principle” that shows how the behaviour of such circuits is determined by those computational paths whose action polynomials are extremal.

•Jan 1, 2008•8 citations

Towards A Theory Of Quantum Computability

Stefano Guerrini, Simone Martini, Andrea Masini

We propose a definition of quantum computable functions as mappings between superpositions of natural numbers to probability distributions of natural numbers. Each function is obtained as a limit of an infinite computation of a quantum Turing machine. The class of quantum computable functions is recursively enumerable, thus opening the door to a quantum computability theory which may follow some of the classical developments.

arXiv:1504.02817•Apr 10, 2015•1 citation

QISA: Incorporating quantum computation into Simulated Annealing for optimization problems

Zhanghui Chen, Ping Luo

This paper proposes a novel model of QISA (Quantum-Inspired Simulated Annealing) which embeds quantum computation into the Simulated Annealing (SA) process for optimization problems. Compared with previous SA studies, QISA adopts Quantum Bits (Qubits) rather than the conventional binary bits as the coding scheme, and update the entries in the Qubits sequence with different probabilities by the proposed methods of heat observation and quantum rotation gate. By flexibly controlling the heating function and rotation angle, QISA does not have to either accept or reject, but can partially accept a new solution. The careful experiments on a number of numerical optimization and combinatorial optimization problems validate its better convergent performance and lower sensitivity to parameters.

IEEE Congress on Evolutionary Computation (CEC)•Jun 1, 2011•7 citations
Abstract. Quantum functions are functions that are defined in terms of quantum mechanical computation. Besides quantum computable functions, we study quantum probability functions, which compute the acceptance probability of quantum computation. We also investigate quantum gap functions, which compute the gap between acceptance and rejection probabilities of quantum computation. 1
This paper initiates a systematic study of quantum functions, which are (partial) functions defined in terms of quantum mechanical computations. Of all quantum functions, we focus on resource-bounded quantum functions whose inputs are classical bit strings. We prove complexity-theoretical properties and unique characteristics of these quantum functions by recent techniques developed for the analysis of quantum computations. We also discuss relativized quantum functions that make adaptive and nonadaptive oracle queries.
This paper initiates a systematic study of quantum functions, which are (partial) functions defined in terms of quantum mechanical computations. Of all quantum functions, we focus on resource-bounded quantum functions whose inputs are classical bit strings. We prove complexity-theoretical properties and unique characteristics of these quantum functions by recent techniques developed for the analysis of quantum computations. We also discuss relativized quantum functions that make adaptive and nonadaptive oracle queries.
Abstract If we reject the ‘spooky’ action at a distance that seems to be required in the Copenhagen interpretation of quantum theory, and which is highlighted by the EPR thought experiment, we must accept the EPR argument that the theory is somehow incomplete. In essence, this involves the rejection of the first postulate of quantum theory: the state of a quantum mechanical system is not completely described by the wave function or state vector.Einstein had hinted at a statistical interpretation. In his opinion, the squares of the wave functions or state vectors of quantum theory represented statistical probabilities obtained by averaging over a large number of real particles. The Copenhagen interpretation of the EPR experiment insists that the reality of the physical states that can be measured is defined by the nature of the interaction between two quantum particles and the nature of the experimental arrangement. A completely deterministic, locally real version of quantum theory demands that the physical states of the particles be established at the moment of their interaction and that the particles separate as individually real entities in those physical states. The physical states of the particles are prescribed by the physics of their interaction and independent of how we choose to set up the measuring instrument, and so no reference to the nature of the latter is necessary, except to define how the independently real particles interact with it. The instrument thus probes an observer-independent reality.
We introduce and analyze circuits that are the quantum mechanical generalization of classical algebraic circuits. Using the algebraic operations of addition and multiplication, as well as the quantum Fourier transform, such circuits are well-defined for rings Z=mZ and finite fields Fq. The acceptance probabilities of such algebraic quantum circuits can be expressed as exponential sums Âx exp(2pi f(x)=m) where the multivariate polynomial f is determined by the circuit, while it is independent of the ring or field over which we interpret the circuit. Dawson et al. [Quantum Information & Computation, 5(2), pp. 102‐112 (2004)] introduced this “sum over paths” description as a discrete version of the path integral approach of standard quantum mechanics. From this perspective, the polynomial f should be interpreted as the “action” of a specific (classical) computational path between the input and output of the circuit. In this article we prove several properties of algebraic quantum circuits. Using the theory of exponential sums, we show that in the limit of large m or q, the acceptance probabilities of a circuit converge to zero or to one. Circuits that do not involve the multiplication operation are the algebraic generalization of Clifford circuits and we show how their acceptance probabilities can be calculated exactly in a classical efficient manner. For algebraic circuits that are defined over rings Z=p r Z we derive a “least action principle” that shows how the behaviour of such circuits is determined by those computational paths whose action polynomials are extremal.
This paper proposes a novel model of QISA (Quantum-Inspired Simulated Annealing) which embeds quantum computation into the Simulated Annealing (SA) process for optimization problems. Compared with previous SA studies, QISA adopts Quantum Bits (Qubits) rather than the conventional binary bits as the coding scheme, and update the entries in the Qubits sequence with different probabilities by the proposed methods of heat observation and quantum rotation gate. By flexibly controlling the heating function and rotation angle, QISA does not have to either accept or reject, but can partially accept a new solution. The careful experiments on a number of numerical optimization and combinatorial optimization problems validate its better convergent performance and lower sensitivity to parameters.