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

Lecture notes in computer science

A New Sibling of BQP

Tereza Tušarová

Published Jan 1, 2005• 0 citations
Publisher
DOI
10.1007/11560319_19

Related papers

The space around BQP

Adam Bouland

•Jan 1, 2017•0 citations

A new sibling of BQP

Tereza Tušarová

We present a new quantum complexity class, called MQ^2, which is contained in AWPP. This class has a compact and simple mathematical definition, involving only polynomial-time computable functions and a unitarity condition. It contains both Deutsch-Jozsa's and Shor's algorithm, while its relation to BQP is unknown. This shows that in the complexity class hierarchy, BQP is not an extraordinary isolated island, but has ''siblings'' which as well can solve prime-factorization.

arXiv:cs/0507057•Jul 21, 2005•0 citations

BQP-Complete Problems

Shengyu Zhang

Springer eBooks•Jan 1, 2012•4 citations

An Algebraic Formulation of Thermality in Nested Rindler Wedges

Waheed A. Dar, Prince Ahmad Ganai, Nirmalya Kajuri

Padmanabhan and Kolekar had demonstrated the phenomenon of recursive thermality in two dimensional free field theories where the Rindler vacuum appears thermal to an observer accelerated with respect to the Rindler observer. We study the same construction at an algebraic level for conformal field theories. At each step, a parent wedge is conformally mapped to a reference Minkowski spacetime, where a new right Rindler wedge and its left sibling are selected. We illustrate that under the Bisognano--Wichmann property, thermality holds at every generation: the state associated with a parent wedge becomes a KMS state when restricted to its right child. Further, using the modular structure of the wedge and its causal sibling, we identify the sibling algebra with the modular commutant and derive the corresponding recursive modular flow explicitly.

arXiv:2610.27007•Oct 19, 2026•0 citations

A New Relaxation Method for Binary Quadratic Programming: An Application to Densest k-subgraph

Chuan-Hao Guo, Liping Tang

Binary quadratic programming (BQP) problem was an NP-hard problem and had a large number of applications.In this paper, a new relaxation method, that was doubly nonnegative relaxation, was proposed for solving BQP problem.Moreover, we prove that the doubly nonnegative relaxation for BQP is equivalent to a new tighter semidifinite relaxation.When BQP problem reduces to densest k-subgraph problem, the doubly nonnegative relaxation is equivalent to a tighter semidifinite relaxation.Finally, some comparative numerical results are reported to show that the efficiency of the doubly nonnegative relaxation is more promising than that of semidefinite relaxation for solving some specific BQP problems.

International Conference on Mathematics, Modelling, Simulation and Algorithms (MMSA)•Jan 1, 2018•2 citations

The Dawn of a New Era

Marco Giliberti, Luisa Lovisetti

SpringerBriefs in history of science and technology•Jan 1, 2025•0 citations
We present a new quantum complexity class, called MQ^2, which is contained in AWPP. This class has a compact and simple mathematical definition, involving only polynomial-time computable functions and a unitarity condition. It contains both Deutsch-Jozsa's and Shor's algorithm, while its relation to BQP is unknown. This shows that in the complexity class hierarchy, BQP is not an extraordinary isolated island, but has ''siblings'' which as well can solve prime-factorization.
Padmanabhan and Kolekar had demonstrated the phenomenon of recursive thermality in two dimensional free field theories where the Rindler vacuum appears thermal to an observer accelerated with respect to the Rindler observer. We study the same construction at an algebraic level for conformal field theories. At each step, a parent wedge is conformally mapped to a reference Minkowski spacetime, where a new right Rindler wedge and its left sibling are selected. We illustrate that under the Bisognano--Wichmann property, thermality holds at every generation: the state associated with a parent wedge becomes a KMS state when restricted to its right child. Further, using the modular structure of the wedge and its causal sibling, we identify the sibling algebra with the modular commutant and derive the corresponding recursive modular flow explicitly.
Binary quadratic programming (BQP) problem was an NP-hard problem and had a large number of applications.In this paper, a new relaxation method, that was doubly nonnegative relaxation, was proposed for solving BQP problem.Moreover, we prove that the doubly nonnegative relaxation for BQP is equivalent to a new tighter semidifinite relaxation.When BQP problem reduces to densest k-subgraph problem, the doubly nonnegative relaxation is equivalent to a tighter semidifinite relaxation.Finally, some comparative numerical results are reported to show that the efficiency of the doubly nonnegative relaxation is more promising than that of semidefinite relaxation for solving some specific BQP problems.