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

Science China Information Sciences

Committed-programming reductions: formalizations, implications and relations

Jiang Zhang, Yu Yu, Dengguo Feng, Shuqin Fan, Zhenfeng Zhang

Published Sep 26, 2024• 0 citations
Publisher
DOI
10.1007/s11432-022-3893-3

Related papers

On the Efficiency of Bit Commitment Reductions

Samuel Ranellucci, Alain Tapp, Severin Winkler +1 more

Lecture notes in computer science•Jan 1, 2011•11 citations

Decomposition of large-scale 0-1 programs

Peter John Ryan

•Jan 1, 1973•0 citations

Epistemic Physics: Scope, Boundaries, and Structural Commitments (Version 2.0)

SPIROS P. KALALIS

Epistemic Physics: Scope, Boundaries, and Structural Commitments (Version 2.0) This article develops a formally delimited account of “Epistemic Physics” as a structural research program situated at the intersection of quantum foundations, relational approaches, information-theoretic reconstruction, and scientific machine learning. The term is not introduced as a new metaphysical doctrine, but as a rigorously constrained framework in which epistemic commitments are considered operative only when they modify admissible state spaces, transformation rules, or stability structures of physical description. The paper proceeds in three stages. First, it reconstructs the historical trajectories through which epistemic considerations became structurally relevant in modern physics. Second, it formalizes Epistemic Measurement Dynamics (EMD) within C*-algebraic quantum theory, introducing sensitivity metrics, spectral stability constraints, completely positive trace-preserving (CPTP) contractivity, and a bounded-sensitivity theorem under weak-* compactness. Third, it clarifies the relationship of this structural layer to ontological-model no-go theorems, including the Pusey–Barrett–Rudolph result, and to QBist approaches, establishing domain separation rather than refutation. The deposit includes two canonical publication-rendered PDF variants and the full canonical release archive (ZIP). Canonical Release SHA256: 1CD95CEDCF03EBFA77B7C5074F7C2B281A73FE77F31CB3F1D1BA6266521850EB This SHA256 corresponds to: EpistemicPhysics_v2_0_RELEASE.zip Any modification of the archive will alter the hash. Integrity may be independently verified using SHA256. Date: 2026-02-27

•Feb 28, 2026•0 citations

A First Step to the Categorical Logic of Quantum Programs

Xin Sun, Feifei He

The long-term goal of our research is to develop a powerful quantum logic which is useful in the formal verification of quantum programs and protocols. In this paper we introduce the basic idea of our categorical logic of quantum programs (CLQP): It combines the logic of quantum programming (LQP) and categorical quantum mechanics (CQM) such that the advantages of both LQP and CQM are preserved while their disadvantages are overcome. We present the syntax, semantics and proof system of CLQP. As a proof-of-concept, we apply CLQP to verify the correctness of Deutsch's algorithm and the concealing property of quantum bit commitment.

Entropy•Jan 24, 2020•7 citations

Optimal multi-bit commitment reductions to weak bit commitments

Anderson C. A. Nascimento, Joern Mueller-Quade, Hideki Imai

Bit commitments are very fundamental protocols in modern cryptography. In this paper, we introduce a model to study bit commitment schemes with a probability of failure (we call them, weak bit commitments). We characterize when it is possible to reduce bit commitments to weak bit commitments. We introduce a new concept in cryptographic reductions called the rate. We prove that our reductions are optimal regarding the rate. Additionally, we show that, when written in the appropriate way, several reductions among cryptographic primitives are equivalent to well known problems in Shannon theory.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2003•1 citation

Unconventional Models of Computation

Cristian S. Calude, John L. Casti, MJ Dinneen

Springer eBooks•Jan 1, 1998•230 citations
Epistemic Physics: Scope, Boundaries, and Structural Commitments (Version 2.0) This article develops a formally delimited account of “Epistemic Physics” as a structural research program situated at the intersection of quantum foundations, relational approaches, information-theoretic reconstruction, and scientific machine learning. The term is not introduced as a new metaphysical doctrine, but as a rigorously constrained framework in which epistemic commitments are considered operative only when they modify admissible state spaces, transformation rules, or stability structures of physical description. The paper proceeds in three stages. First, it reconstructs the historical trajectories through which epistemic considerations became structurally relevant in modern physics. Second, it formalizes Epistemic Measurement Dynamics (EMD) within C*-algebraic quantum theory, introducing sensitivity metrics, spectral stability constraints, completely positive trace-preserving (CPTP) contractivity, and a bounded-sensitivity theorem under weak-* compactness. Third, it clarifies the relationship of this structural layer to ontological-model no-go theorems, including the Pusey–Barrett–Rudolph result, and to QBist approaches, establishing domain separation rather than refutation. The deposit includes two canonical publication-rendered PDF variants and the full canonical release archive (ZIP). Canonical Release SHA256: 1CD95CEDCF03EBFA77B7C5074F7C2B281A73FE77F31CB3F1D1BA6266521850EB This SHA256 corresponds to: EpistemicPhysics_v2_0_RELEASE.zip Any modification of the archive will alter the hash. Integrity may be independently verified using SHA256. Date: 2026-02-27
The long-term goal of our research is to develop a powerful quantum logic which is useful in the formal verification of quantum programs and protocols. In this paper we introduce the basic idea of our categorical logic of quantum programs (CLQP): It combines the logic of quantum programming (LQP) and categorical quantum mechanics (CQM) such that the advantages of both LQP and CQM are preserved while their disadvantages are overcome. We present the syntax, semantics and proof system of CLQP. As a proof-of-concept, we apply CLQP to verify the correctness of Deutsch's algorithm and the concealing property of quantum bit commitment.
Bit commitments are very fundamental protocols in modern cryptography. In this paper, we introduce a model to study bit commitment schemes with a probability of failure (we call them, weak bit commitments). We characterize when it is possible to reduce bit commitments to weak bit commitments. We introduce a new concept in cryptographic reductions called the rate. We prove that our reductions are optimal regarding the rate. Additionally, we show that, when written in the appropriate way, several reductions among cryptographic primitives are equivalent to well known problems in Shannon theory.