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

Springer eBooks

1 Fundamental Problems for Universal Quantum Computers

Tien D. Kieu, M. Danos

Published Nov 27, 2007• 0 citations
Publisher
DOI
10.1007/3-540-45557-4_28

Related papers

Quantum State Superposition for Universal Computation Architecture

Jincheng Zhang

This paper proposes a novel computational architecture centered around the fundamental principles of quantum state superposition and quantum entanglement. The core claim is the design of a universally applicable quantum computing framework that, without relying on pre-defined algorithms, can tackle any solvable computational problem. The proposed mechanism leverages the creation of highly entangled quantum systems, exploiting superposition to enable parallel information processing and transformation. Unlike existing quantum computing approaches which are often tailored to specific problems, this architecture represents a shift towards a truly general-purpose quantum computer. The theoretical underpinnings of this architecture are explored, focusing on the necessary conditions for achieving universal computation and outlining potential challenges and future research directions. We introduce a framework that moves beyond algorithmic constraints, offering a pathway toward harnessing the full potential of quantum mechanics for computational tasks.

•Sep 5, 2026•0 citations

Remarks on universal quantum computer

Yu Shi

arXiv:quant-ph/9908074•Physics Letters A•Feb 1, 2002•33 citations

Universality and programmability of quantum computers

Willem L. Fouché, Johannes Heidema, Glyn Jones +1 more

arXiv:0710.3329•Theoretical Computer Science•May 19, 2008•5 citations

Physics-Bounded Computational Substrate: A Brief Synthesis of Thermodynamic Limits in Analog and Quantum Information Processing

QNFO

The physical realization of any computational model is fundamentally bounded not by algorithmic complexity alone, but by the thermodynamic and quantum statistical limits of its substrate, a constraint that recasts computationally hard problems as problems of physical resource scaling and forces a distinction between abstract universality and practical realizability.

•Dec 17, 2025•0 citations

Quantum Lower Bounds for Distributed Network Computing

Michael Elkin, Hartmut Klauck, Danupon Nanongkai +1 more

We study lower bounds for quantum distributed computing, where a set of nodes (representing quantum computers) interconnected by an underlying network consisting of (bandwidth-restricted) links, communicate using quantum communication. Nodes have unlimited computational power and may share an unlimited number of entangled qubits. Our main contribution is a simple uniform technique for proving lower bounds for quantum distributed algorithms. In particular, we identify a new quantum communication model called the Server model which provides a connection between distributed algorithms and communication complexity: it is strong enough to capture the hardness of several distributed computing problems, while weak enough that several hard problems in two-party communication complexity remain hard; to this end, we identify a set of communication complexity techniques that can be carried over to the Server model, namely techniques based on nonlocal games. We show that these techniques serve as a fundamental tool in proving lower bounds in quantum distributed computing. The new techniques help us to prove several non-trivial quantum distributed lower bounds (which are the first-known quantum bounds for fundamental global problems such as minimum spanning tree, shortest paths etc.), some of which are new even in the classical setting. First, it allows us to show that all previous classical lower bounds of more than twenty verification and optimization graph problems in [Das Sarma et al., STOC 11] also hold in the quantum setting. Many of these bounds are tight, implying a large class of problems that do not gain an advantage from quantum effects. Our results also imply the following new results in the classical communication models: (1) the first randomized lower bounds for Hamiltonian cycle and spanning tree verification problems in both the distributed computing and the communication complexity model, answering the open problem of Das Sarma et al. and subsuming many bounds in [Babai, Frankl, and Simon, FOCS 96], and (2) the first lower bound that is tight for all weight aspect ratios, matching previous upper bounds of [Elkin, STOC 04]. Submitted for a Regular Presentation. The full version of this paper can be found as [15] at http://arxiv.org/abs/1207.5211. ∗Department of Computer Science, Ben-Gurion University, Beer-Sheva, 84105, Israel. E-mail: elkinm@cs.bgu.ac.il. †Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371 & Centre for Quantum Technologies, National University of Singapore, Singapore 117543. E-mail: hklauck@gmail.com. Research at the Centre for Quantum Technologies is funded by the Singapore Ministry of Education and the National Research Foundation. ‡Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371. Work partially done while at University of Vienna, Austria. E-mail: danupon@gmail.com. §Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371 & Department of Computer Science, Brown University, Providence, RI 02912, USA. E-mail: gopalpandurangan@gmail.com. Supported in part by the following research grants: Nanyang Technological University grant M58110000, Singapore MOE Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082, and a grant from the US-Israeli Binational Science Foundation (BSF).

•Jul 22, 2012•1 citation

Universality in Quantum Computation

Emmanuel Jeandel

Lecture notes in computer science•Jan 1, 2004•6 citations
This paper proposes a novel computational architecture centered around the fundamental principles of quantum state superposition and quantum entanglement. The core claim is the design of a universally applicable quantum computing framework that, without relying on pre-defined algorithms, can tackle any solvable computational problem. The proposed mechanism leverages the creation of highly entangled quantum systems, exploiting superposition to enable parallel information processing and transformation. Unlike existing quantum computing approaches which are often tailored to specific problems, this architecture represents a shift towards a truly general-purpose quantum computer. The theoretical underpinnings of this architecture are explored, focusing on the necessary conditions for achieving universal computation and outlining potential challenges and future research directions. We introduce a framework that moves beyond algorithmic constraints, offering a pathway toward harnessing the full potential of quantum mechanics for computational tasks.
We study lower bounds for quantum distributed computing, where a set of nodes (representing quantum computers) interconnected by an underlying network consisting of (bandwidth-restricted) links, communicate using quantum communication. Nodes have unlimited computational power and may share an unlimited number of entangled qubits. Our main contribution is a simple uniform technique for proving lower bounds for quantum distributed algorithms. In particular, we identify a new quantum communication model called the Server model which provides a connection between distributed algorithms and communication complexity: it is strong enough to capture the hardness of several distributed computing problems, while weak enough that several hard problems in two-party communication complexity remain hard; to this end, we identify a set of communication complexity techniques that can be carried over to the Server model, namely techniques based on nonlocal games. We show that these techniques serve as a fundamental tool in proving lower bounds in quantum distributed computing. The new techniques help us to prove several non-trivial quantum distributed lower bounds (which are the first-known quantum bounds for fundamental global problems such as minimum spanning tree, shortest paths etc.), some of which are new even in the classical setting. First, it allows us to show that all previous classical lower bounds of more than twenty verification and optimization graph problems in [Das Sarma et al., STOC 11] also hold in the quantum setting. Many of these bounds are tight, implying a large class of problems that do not gain an advantage from quantum effects. Our results also imply the following new results in the classical communication models: (1) the first randomized lower bounds for Hamiltonian cycle and spanning tree verification problems in both the distributed computing and the communication complexity model, answering the open problem of Das Sarma et al. and subsuming many bounds in [Babai, Frankl, and Simon, FOCS 96], and (2) the first lower bound that is tight for all weight aspect ratios, matching previous upper bounds of [Elkin, STOC 04]. Submitted for a Regular Presentation. The full version of this paper can be found as [15] at http://arxiv.org/abs/1207.5211. ∗Department of Computer Science, Ben-Gurion University, Beer-Sheva, 84105, Israel. E-mail: elkinm@cs.bgu.ac.il. †Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371 & Centre for Quantum Technologies, National University of Singapore, Singapore 117543. E-mail: hklauck@gmail.com. Research at the Centre for Quantum Technologies is funded by the Singapore Ministry of Education and the National Research Foundation. ‡Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371. Work partially done while at University of Vienna, Austria. E-mail: danupon@gmail.com. §Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371 & Department of Computer Science, Brown University, Providence, RI 02912, USA. E-mail: gopalpandurangan@gmail.com. Supported in part by the following research grants: Nanyang Technological University grant M58110000, Singapore MOE Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082, and a grant from the US-Israeli Binational Science Foundation (BSF).