Pith. sign in

REVIEW 6 major objections 5 minor 62 references

Quantum Information-Theoretical Size Bounds for Conjunctive Queries with Functional Dependencies

T0 review · 6 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that worst-case size bounds for conjunctive queries with functional dependencies can be derived from a quantum Rényi entropy optimization, sound but not tight, and that a head-absorption rule decides when the program…

desk verdict A novel reformulation of conjunctive query size bounds via Rényi entropy, but the abstract promises a dichotomy theorem the paper never states or proves, and the proof of a load-bearing lemma is wrong. read the letter →

arxiv 2506.07552 v2 pith:XERIJZPJ submitted 2025-06-09 quant-ph cs.DB

Valter Uotila , Jiaheng Lu This is my paper · ORCID
classification quant-phcs.DB MSC 68P1594A1781P45
keywords databasetheoryquantuminformationclassicalconjunctivequeriesfunctionaldependenciesworst-casesizeboundsentropyconesRényi
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper attempts to show that worst-case output sizes of conjunctive queries under functional dependencies can be estimated by a quantum information-theoretic program: replace Shannon entropies with Rényi entropies of order $0<\alpha<1$, maximize the entropy of the query head over quantum states, and read off the exponent $h_\alpha(Q)$ from that maximum. The attraction is that for these $\alpha$ values the Rényi entropy cone is entirely characterized by non-negativity, so the optimization avoids the infinite ladder of non-Shannon inequalities that makes the classical Shannon formulation intractable; the price is that the bound is sound but not tight. The paper further claims that the classical Shannon entropy bound returns as the limit $\alpha\to 1$ (Theorem 7), and it announces a dichotomy: if the query satisfies a head absorption rule, the program value is at most one and $|Q(D)|\le \mathrm{rmax}(D)$, while otherwise the program is unbounded. If these claims hold, the paper gives the first bridge from quantum information theory to classical worst-case query size analysis, shifting the hard part of the problem from characterizing entropy cones to identifying classical states inside the quantum relaxation.

What carries the argument

The central object is the quantum Rényi entropy program of Theorem 6: maximize $H_\alpha(\rho_{u_0})$ over states on $\mathcal{H}=\bigotimes_i \mathcal{H}_{X_i}$ with $H_\alpha(\rho)= \frac{1}{1-\alpha}\log \operatorname{Tr}\rho^\alpha$ for $0<\alpha<1$. The enabling result is Theorem 1, from the cited work [31]: for fixed $0<\alpha<1$, every non-negative vector indexed by the non-empty subsets of variables can be approximated by the reduced-state Rényi entropies of some quantum state, so the entropy cone is simply $\mathbb{R}_{\ge 0}^{2^k-1}$. Functional dependencies enter through Definition 17, which declares that $A\to B$ holds exactly when $\rho_A$ and $\rho_{A\cup B}$ have the same spectrum; by the chain-rule definition of conditional Rényi entropy this is equivalent to the constraint $H_\alpha(\rho_{A\cup B})=H_\alpha(\rho_A)$ used in the program. The decohering operator $\Delta$ (Definition 6) is the mechanism meant to force the optimizing states to be diagonal in the computational basis, i.e. classical; the paper's discussion identifies this classical-state selection, not the entropy cone, as the true source of hardness. These pieces carry the argument: Theorem 1 gives a tractable feasible region, Lemma 3 ties FDs to entropy equalities, Theorem 5 relates classical random variables to quantum states, and Theorem 7 converts the relaxation into the tight Shannon bound in the $\alpha\to1$ limit.

What would settle it

Take the two-qubit Bell state $\frac{1}{\sqrt2}(|00\rangle+|11\rangle)$: its global density matrix has spectrum $\{1,0\}$, while the reduced single-qubit state has spectrum $\{1/2,1/2\}$. The reduced eigenvalues are not a subset of the global eigenvalues, contradicting the step used in Lemma 3; computing $H_\alpha$ for both states shows the FD constraint $H_\alpha(\rho_{A\cup B})=H_\alpha(\rho_A)$ fails for this state, so the lemma's proof cannot be correct for general quantum states.

Watch

Extended reading notes

Core claim

For a conjunctive query $Q$ with a fixed set $F$ of functional dependencies and any database $D$ satisfying $F$, the paper's central theorem (Theorem 6) asserts $|Q(D)|\le \mathrm{rmax}(D)^{h_\alpha(Q)}$, where $h_\alpha(Q)$ is the optimum of maximizing $H_\alpha(\rho_{u_0})$ over density operators subject to $H_\alpha(\rho_{u_j})\le 1$ for each relation $R_j$ in the query body, $H_\alpha(\rho_B|\rho_A)=0$ for each functional dependency $A\to B$, and $\Delta(\rho_S)=\rho_S$ for every non-empty attribute set $S$. Conditional Rényi entropy is defined through the chain rule, so the FD constraints become $H_\alpha(\rho_{A\cup B})=H_\alpha(\rho_A)$. The decohering constraint $\Delta(\rho_S)=\rho_S$ is what keeps the optimization inside classical distributions; without it, the relaxation runs over all quantum states and the FD constraints no longer refer to database rows. The paper also claims (Theorem 7) that as $\alpha\to 1$ the program approaches the tight Shannon entropic bound, and the abstract states a dichotomy theorem based on a head absorption rule: when the rule holds the program value is at most one and the query size is bounded by the largest input relation, otherwise the program is unbounded.

Load-bearing premise

The load-bearing premise is that a functional dependency $A\to B$ in the database is correctly represented by the condition that the reduced quantum states on $A\cup B$ and on $A$ have equal Rényi entropy, so the constraint $H_\alpha(\rho_{A\cup B})=H_\alpha(\rho_A)$ in the program is the faithful translation of the FD.

Editorial extensions

If this is right

  • For every conjunctive query with a set of functional dependencies, the quantum Rényi program yields a valid upper bound $|Q(D)|\le \mathrm{rmax}(D)^{h_\alpha(Q)}$, so query planners could use it as a cheap sanity bound even though it is not tight.
  • Letting $\alpha$ approach $1$ recovers the tight Shannon-entropy bound in the limit, meaning the classical theory is a boundary case of the quantum formulation rather than a separate problem.
  • If a query satisfies the head absorption rule, the program value is at most one and the query result cannot exceed the largest input relation, giving an immediately checkable sufficient condition for a trivial bound.
  • If the head absorption rule is not satisfied, the Rényi program is unbounded, which makes the dichotomy a precise quantifier of when the quantum approach fails to give a finite certificate.
  • The non-negativity characterization of the Rényi entropy cone removes the need for infinitely many information inequalities, at the cost of a new constraint that the optimizing states be classical.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A likely consequence the paper leaves implicit: the head absorption dichotomy probably distinguishes queries whose FD constraints are already enforceable by diagonal states from those where the quantum relaxation can exploit entanglement; checking this on small query cycles would map the boundary.
  • Because the FD encoding via spectral equality fails for generic entangled states, a robust fix would be to impose commutativity of all reduced states or to enforce $\Delta(\rho)=\rho$ on the full state; this is an editorial proposal rather than a claim in the paper.
  • The relative-entropy cone mentioned in Section 5.3 is identical for classical and quantum states and is described by non-negativity plus monotonicity; if a query-size encoding in relative entropy can be found, it may yield a tight and practically computable linear program, which is a testable research direction.
  • One could turn the dichotomy into an algorithm: enumerate small conjunctive queries, compute the Rényi program optimum numerically for fixed $\alpha$, and check whether the head absorption rule coincides with program value at most one; agreement would validate the dichotomy on finite data.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

6 major / 5 minor

Summary. The paper proposes a quantum-information-theoretic reformulation of worst-case size bounds for conjunctive queries with functional dependencies. It replaces Shannon entropy in the classical GLVV/Gogacz-Torunczyk framework with quantum Rényi entropy of order α∈(0,1), whose entropy cone is characterized by non-negativity (Theorem 1, from Linden–Mosonyi–Winter). The central technical claim is Theorem 6, which asserts |Q(D)| ≤ rmax(D)^{h_α(Q)} for an optimization over quantum states with constraints H_α(ρ_{u_j})≤1, H_α(ρ_B|ρ_A)=0 for each FD, H_α(ρ_S)≥0, and Δ(ρ_S)=ρ_S. Theorem 7 claims that the bound becomes tight as α→1. The abstract additionally advertises a dichotomy theorem based on a 'head absorption rule', with one branch giving |Q(D)|≤rmax(D) and the other giving an unbounded program. The paper is largely a review of classical results plus a proposed quantum analogue, with worked examples and a pointer to a GitHub repository.

Significance. If the central claims were correct, the paper would introduce a new technical bridge between quantum Rényi entropies and database cardinality bounds, and the non-negativity characterization of the Rényi entropy cone could be a useful simplification. The paper also provides a readable survey of the relevant classical literature, and the availability of computational examples is a positive feature. However, the advertised dichotomy theorem is absent from the body, the equivalence between functional dependencies and conditional Rényi entropy is not proved for general quantum states, and several proof steps in Theorems 5–7 are sketches relying on unjustified assertions. Because these are load-bearing for the main bound, the significance of the paper as a theoretical contribution is not currently established.

major comments (6)
  1. [Abstract and Sections 1–6] The abstract promises a dichotomy theorem based on a 'head absorption rule': if the query satisfies this rule, the Rényi program value is at most one and |Q(D)|≤rmax(D); otherwise the program is unbounded. However, the terms 'head absorption' and 'dichotomy' appear nowhere in the body of the paper, and no theorem, definition, or proof states or establishes such a result. Theorem 6 gives a general upper bound and Theorem 7 is a limit statement; neither implies the dichotomy. Moreover, the 'otherwise unbounded' branch is not credible: for the simple query Q=R(x,y)←S(x)∧T(y) with no functional dependencies, the program with the classical-state constraint Δ(ρ_S)=ρ_S has a finite objective, since H_α(ρ_xy) is bounded under H_α(ρ_x)≤1 and H_α(ρ_y)≤1 for α∈(0,1). This is a missing central result, not a presentational gap.
  2. [§4, Lemma 3] The proof of Lemma 3 is invalid for general quantum states. The converse direction asserts that the eigenvalues of ρ_A are a subset of the eigenvalues of ρ_{A∪B}; this is false, e.g. for a Bell state the reduced state ρ_A has eigenvalues {1/2,1/2} while ρ_{A∪B} has eigenvalues {1,0}, and the two operators generally act on spaces of different dimension. Consequently the claimed equivalence between Definition 17 and H_α(ρ_B|ρ_A)=0 is not established for the quantum states over which Theorem 6 optimizes. Since Theorem 6's functional-dependency constraints are justified solely by Lemma 3, the soundness of the main upper bound is not proven as stated.
  3. [§4, Theorem 5(1)] Theorem 5(1) claims that for every classical random variable X satisfying a functional dependency there exists a quantum state ρ with H_1(X_S)=H_α(ρ_S) for all non-empty S. The proof invokes Theorem 1, which only states that a non-negative entropy vector can be arbitrarily well approximated by Rényi entropies of reduced states; it does not guarantee exact realization. The proof also does not show that the approximating state satisfies the exact FD constraint H_α(ρ_{A∪B})=H_α(ρ_A). The claimed exact equality and the claimed preservation of FDs are therefore unsupported.
  4. [§4, Theorem 5(2)] The proof of Theorem 5(2) takes the equal-eigenvalue condition of Definition 17 together with Δ(ρ_S)=ρ_S and concludes that ρ_{A∪B}=ρ_A as operators, writing an equality of sums over different domains. Equal spectra do not imply operator equality, and the displayed equation ∑_{t∈dom(A∪B)} p_t |t⟩⟨t| = ∑_{t∈dom(A)} p_t |t⟩⟨t| conflates operators on different tensor factors. A valid proof would need to use the functional-dependency property directly to show that the marginal distribution of A∪B has the same support structure as that of A; the given argument does not establish this.
  5. [§4, Theorem 6 proof] The proof of Theorem 6 is a sketch rather than a derivation. The step that a database state satisfies the constraints after normalization is not written out, and the use of Lemma 3 to justify the FD constraints inherits the problems of that lemma. In addition, Theorem 1 provides only an approximation result for non-negative vectors, so the statement that non-negativity characterizes the Rényi entropy cone is only true up to closure; the optimization problem in Theorem 6 may therefore have no attained maximum, and the existence of an optimal h_α(Q) needs separate justification. The proof also does not address why the Δ(ρ_S)=ρ_S constraints are compatible with the entropy-cone characterization used for arbitrary states. A rigorous proof of the upper bound is required.
  6. [§4, Theorem 7] Theorem 7 asserts that the bound becomes arbitrarily tight as α→1, but the proof only says that the Rényi program 'approaches' the Shannon program. To conclude that the optimal values h_α(Q) converge to the Shannon optimal value, one needs an exchange-of-limits or compactness argument, and one must specify how the feasible sets and the FD constraints behave in the limit. The proof does not provide such an argument, and the statement 'the Rényi entropy program will always provide an upper bound compared to the tight Shannon entropy bound' does not establish convergence of the optima. The claim is therefore not proved.
minor comments (5)
  1. [§2.2, Example 4] The basis notation is incomplete: the text reads '{|1⟩,|2⟩ in Hilbert space', where a closing angle bracket is missing; it should be '{|1⟩,|2⟩}'.
  2. [§4, Theorem 6 and Definition 17] The symbol '⊂' is used ambiguously. In the constraint '∀S⊂var(Q), S≠∅', the full set var(Q) must be included for Δ(ρ)=ρ to force classicality of the whole state; the paper should state explicitly whether subsets are proper or not and use '⊆' or '⊊' accordingly.
  3. [§4, Theorem 6 statement] The theorem writes 'R_{i_j} with i_j∈[m]' but the relations are indexed from 1 to m elsewhere; the indexing should be aligned (e.g., use i_j∈[n] with the convention of Section 2.1 or explicitly state the range).
  4. [§5.1] The discussion repeatedly writes the decohering constraint as 'D(ρ_S)=ρ_S', but the definition in §2.2 uses Δ; this typo should be corrected.
  5. [§4, Definition 17] The phrase 'same eigenvalues in their spectral decompositions with respect to the basis defined in Definition 15' is unclear, since eigenvalues are basis-independent; the intended meaning is presumably that the density matrices are diagonal in that basis with matching classical probabilities. This should be restated precisely.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 6 is a direct upper-bound construction using external Rényi-cone and classical-bound results; the missing head-absorption dichotomy and the flawed eigenvalue argument in Lemma 3 are correctness gaps, not self-referential reductions.

full rationale

The paper's central result, Theorem 6, is not circular. The proof constructs, for a given database D, the uniform (maximally mixed) state over the tuples of Q'(D), observes that Rényi entropy is maximized by maximally mixed states, and derives |Q(D)| ≤ rmax(D)^{h_α(Q)} from the ratio of Rényi entropies. The information-theoretic inputs are the Linden–Mosonyi–Winter theorem (Theorem 1 here, external to this paper) that the Rényi cone for 0<α<1 is the non-negative orthant, and the classical tight bound imported from GLVV [16] and Gogacz–Toruńczyk [15]. No fitted parameter is renamed as a prediction, and no step assumes the inequality being proved. Theorem 7 (α→1 limit) uses Lemma 1 and the external Shannon-bound theorem; it is a continuity and limit claim, and even if pointwise convergence does not automatically justify optimizer convergence, that is a technical gap rather than a circular dependence. Lemma 3's assertion that the eigenvalues of ρ_A are a subset of those of ρ_{A∪B} is false for general quantum states (e.g., a Bell state has reduced eigenvalues 1/2, 1/2 versus global eigenvalues 1, 0), and Theorem 5(2) has a related basis-labeling issue; these make the FD encoding unsound as stated, but they are correctness risks, not self-referential reasoning. As the review rules require, I also flag that the abstract announces a 'dichotomy theorem' with a 'head absorption rule' ('if the query satisfies a head absorption rule, then the Rényi program value is at most one and |Q(D)| ≤ rmax(D). Otherwise, the program is unbounded'), but no definition of head absorption and no such theorem appear in Sections 1–6; this is a missing-result problem, not circularity. The authors' self-citations ([37], [53]–[56], [60]) concern other database and quantum-optimization topics and code; none is load-bearing in the proofs of Theorems 5–7. Accordingly, the derivation chain is self-contained with respect to circularity.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The central claim rests on two author-chosen definitions (the eigenvalue-based quantum FD and the chain-rule conditional entropy), on the external Rényi-cone theorem, and on the classical GLVV and Gogacz-Torunczyk framework. There is no numerical fitting; α is a tunable parameter, not a fitted constant.

free parameters (1)
  • Rényi order α = unspecified in (0,1); paper discusses α→1
    The bound h_α(Q) depends on α and the paper varies it toward 1, but no data-fitting or calibration is used to select α.
assumptions (6)
  • standard math For 0<α<1, the Rényi entropy cone is the non-negative orthant: every non-negative vector can be approximated by reduced Rényi entropies of some quantum state (Theorem 1, attributed to [31]).
    Used to replace Shannon entropy cone constraints by simple non-negativity in the quantum program and in Theorem 5.
  • standard math The classical polymatroid bound (Theorem 2, from [16]) and the Shannon entropic bound (Theorem 3, from [15]) are correct.
    These are the external benchmarks the paper builds on and takes the α→1 limit toward.
  • standard math Rényi entropy tends to von Neumann entropy as α→1 (Lemma 1, attributed to [35]).
    Needed for Theorem 7.
  • ad hoc to paper A functional dependency on a database is equivalent to equality of the spectra of the reduced states ρ_{A∪B} and ρ_A (Definition 17).
    This is a new definition introduced by the authors to port FDs into quantum states; its correctness is not independently established and Lemma 3's proof of the associated entropy characterization is flawed.
  • ad hoc to paper The conditional Rényi entropy is defined by the chain rule H_α(B|A)=H_α(AB)-H_α(A) (Definition 11).
    The paper acknowledges multiple definitions of conditional Rényi entropy exist; choosing the chain rule is a modeling decision that affects the FD constraints and the meaning of H_α(B|A)=0.
  • domain assumption The optimization may be restricted to states whose reduced density operators satisfy Δ(ρ_S)=ρ_S without loss of the desired upper bound.
    The paper claims this encodes classical distributions, but the proof does not clarify whether the full variable set is included; if only proper subsets are included, non-classical global states with classical marginals are admitted.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Information-Theoretical Size Bounds for Conjunctive Queries with Functional Dependencies." pith.science (2026). https://pith.science/paper/XERIJZPJ

@misc{pith2026250607552,
  author       = {Pith},
  title        = {Pith review of: Quantum Information-Theoretical Size Bounds for Conjunctive Queries with Functional Dependencies},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XERIJZPJ}},
  note         = {Machine review of arXiv:2506.07552}
}
abstract

Deriving formulations to estimate worst-case size bounds for conjunctive queries under various constraints has been at the core of theoretical database research. If the problem has no constraints or has a single functional dependency, tight worst-case size bounds are computable. If the problem has more than one functional dependency, computing tight bounds can be difficult in practice and may even require an infinite number of linear inequalities in its optimization formulation. While these challenges have been addressed with varying methods, no prior research has employed quantum information theory to address this problem. In this work, we establish a connection between earlier classical information theory-based works and quantum information theory. We propose replacing the classical Shannon entropy formulation with the quantum R\'enyi entropy of order $\alpha \in (0,1)$ whose entropy cone is characterized simply by non-negativity. The first key result is to express the bound in terms of optimizing over quantum states and R\'enyi entropy. Optimizing with respect to quantum states rather than classical distributions transfers the hardness into the problem of characterizing classical states, yielding a sound but generally not tight upper bound. We further quantify this hardness explicitly by proposing a dichotomy theorem: if the query satisfies a head absorption rule, then the R\'enyi program value is at most one and $|Q(D)| \leq \mathrm{rmax}(D)$. Otherwise, the program is unbounded.

Figures

Figures reproduced from arXiv: 2506.07552 by the authors.

Figure 1
Figure 1. The example query in Equation 6 forms a cycle [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Concrete database instance continuing Example 1 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Linear program for Theorem 2 to compute the polymatroid bound. The constraints implicitly assume that expressions [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

62 extracted references · 36 canonical work pages

  1. [1]

    Ngo, and Dan Suciu

    Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. 2016. Computing Join Queries with Functional Dependencies. InProceedings of the 35th ACM SIGMOD- SIGACT-SIGAI Symposium on Principles of Database Systems(San Francisco, Cali- fornia, USA)(PODS ’16). Association for Computing Machinery, New York, NY, USA, 327–342. https://doi.org/10.1145/2902251.2902289

    work page arXiv 2016

  2. [2]

    Ngo, and Dan Suciu

    Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. 2017. What Do Shannon- type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?. InProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. ACM, Chicago Illinois USA, 429–444. https: //doi.org/10.1145/3034786.3056105

    arXiv 2017

  3. [3]

    A. V. Aho, C. Beeri, and J. D. Ullman. 1979. The theory of joins in relational databases.ACM Trans. Database Syst.4, 3 (Sept. 1979), 297–314. https://doi.org/ 10.1145/320083.320091

    arXiv 1979

  4. [4]

    Huzihiro Araki and Elliott H. Lieb. 1970. Entropy inequalities.Communications in Mathematical Physics18, 2 (June 1970), 160–170. https://doi.org/10.1007/ BF01646092

    work page 1970

  5. [5]

    Albert Atserias, Martin Grohe, and Dániel Marx. 2013. Size Bounds and Query Plans for Relational Joins.SIAM J. Comput.42, 4 (2013), 1737–1767. https: //doi.org/10.1137/110859440 arXiv:https://doi.org/10.1137/110859440

    doi:10.1137/110859440 2013

  6. [6]

    Diogo Barbosa, Le Gruenwald, Laurent D’Orazio, and Jorge Bernardino. 2024. QRLIT: Quantum Reinforcement Learning for Database Index Tuning.Future Internet16, 12 (Nov. 2024), 439. https://doi.org/10.3390/fi16120439

    work page doi:10.3390/fi16120439 2024

  7. [7]

    Baumgratz, M

    T. Baumgratz, M. Cramer, and M. B. Plenio. 2014. Quantifying Coherence.Phys. Rev. Lett.113 (Sep 2014), 140401. Issue 14. https://doi.org/10.1103/PhysRevLett. 113.140401

    doi:10.1103/physrevlett 2014

  8. [8]

    Tim Bittner and Sven Groppe. 2020. Avoiding blocking by scheduling transactions using quantum annealing. InProceedings of the 24th Symposium on International Database Engineering & Applications(Seoul, Republic of Korea)(IDEAS ’20). Association for Computing Machinery, New York, NY, USA, Article 21, 10 pages. https://doi.org/10.1145/3410566.3410593

    arXiv 2020

Show all 62 references
  1. [9]

    Tim Bittner and Sven Groppe. 2020. Hardware Accelerating the Optimization of Transaction Schedules via Quantum Annealing by Avoiding Blocking.OJCC7, 1 (2020), 1–21. http://nbn-resolving.de/urn:nbn:de:101:1-2020112218332015343957

    2020

  2. [10]

    F.R.K Chung, R.L Graham, P Frankl, and J.B Shearer. 1986. Some intersection theorems for ordered sets and graphs.Journal of Combinatorial Theory, Series A 43, 1 (1986), 23–37. https://doi.org/10.1016/0097-3165(86)90019-1

    1986 doi

  3. [11]

    Solèr, Rudolf Marcel Füchslin, and Kurt Stockinger

    Tobias Fankhauser, Marc E. Solèr, Rudolf Marcel Füchslin, and Kurt Stockinger

  4. [12]

    Maja Franz, Tobias Winker, Sven Groppe, and Wolfgang Mauerer. 2024. Hype or Heuristic? Quantum Reinforcement Learning for Join Order Optimisation . In2024 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE Computer Society, Los Alamitos, CA, USA, 40...

    2024

  5. [13]

    Kristin Fritsch and Stefanie Scherzinger. 2023. Solving Hard Variants of Database Schema Matching on Quantum Computers.VLDB16, 12 (Aug. 2023), 3990–3993. https://doi.org/10.14778/3611540.3611603

    2023

  6. [14]

    Dmitry Gavinsky, Shachar Lovett, Michael Saks, and Srikanth Srinivasan. 2015. A tail bound for read- k families of functions.Random Structures & Algorithms 47, 1 (Aug. 2015), 99–108. https://doi.org/10.1002/rsa.20532

    2015 doi

  7. [15]

    Tomasz Gogacz and Szymon Torunczyk. 2017. Entropy Bounds for Conjunctive Queries with Functional Dependencies.LIPIcs, Volume 68, ICDT 201768 (2017), 15:1–15:17. https://doi.org/10.4230/LIPICS.ICDT.2017.15

    2017 doi

  8. [16]

    Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, and Paul Valiant. 2012. Size and Treewidth Bounds for Conjunctive Queries.J. ACM59, 3, Article 16 (June 2012), 35 pages. https://doi.org/10.1145/2220357.2220363

    2012

  9. [17]

    Martin Grohe and Dániel Marx. 2014. Constraint Solving via Fractional Edge Covers.ACM Trans. Algorithms11, 1, Article 4 (Aug. 2014), 20 pages. https: //doi.org/10.1145/2636918

    2014 doi

  10. [18]

    Sven Groppe and Jinghua Groppe. 2021. Optimizing Transaction Schedules on Universal Quantum Computers via Code Generation for Grover’s Search Algo- rithm. InProceedings of the 25th International Database Engineering & Applications Symposium(Montreal, QC, Canada)(IDEAS ’21). As...

    2021

  11. [19]

    Le Gruenwald, Tobias Winker, Umut Çalıkyılmaz, Jinghua Groppe, and Sven Groppe. 2023. Index Tuning with Machine Learning on Quantum Computers for Large-Scale Database Applications. InQDSM@VLDB, Vancouver, Canada. https://ceur-ws.org/Vol-3462/QDSM5.pdf

    2023

  12. [20]

    Rihan Hai, Shih-Han Hung, Tim Coopmans, Tim Littau, and Floris Geerts

  13. [21]

    Rihan Hai, Shih-Han Hung, and Sebastian Feld. 2024. Quantum Data Management: From Theory to Opportunities. InICDE. IEEE, 5376–5381. https://doi.org/10. 1109/icde60146.2024.00410

    2024

  14. [22]

    Xinhua Hu and Zhongxing Ye. 2006. Generalized quantum en- tropy.J. Math. Phys.47, 2 (02 2006), 023502. https://doi. org/10.1063/1.2165794 arXiv:https://pubs.aip.org/aip/jmp/article- pdf/doi/10.1063/1.2165794/13657686/023502_1_online.pdf

    2006 doi

  15. [23]

    Ben Ibinson, Noah Linden, and Andreas Winter. 2007. All Inequalities for the Relative Entropy.Communications in Mathematical Physics269, 1 (Jan. 2007), 223–238. https://doi.org/10.1007/s00220-006-0081-6

    2007 doi

  16. [24]

    Manish Kesarwani and Jayant R. Haritsa. 2024. Index Advisors on Quantum Platforms.VLDB17, 11 (July 2024), 3615–3628. https://doi.org/10.14778/3681954. 3682025

    2024 doi

  17. [25]

    Manish Kesarwani and Jayant R. Haritsa. 2024. Is Quantum-Based SQL Query Execution Viable?. InProceedings of Workshops at the 50th International Conference on Very Large Data Bases, VLDB 2024, Guangzhou, China, August 26-30, 2024. VLDB.org. https://vldb.org/workshops/2024/proc...

    2024

  18. [26]

    Mahmoud Abo Khamis, Kyle Deeds, Dan Olteanu, and Dan Suciu. 2024. Pes- simistic Cardinality Estimation. arXiv:2412.00642 (Dec. 2024). https://doi.org/10. 48550/arXiv.2412.00642 arXiv:2412.00642 [cs]

    2024 doi arXiv

  19. [27]

    Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu, and Dan Suciu. 2024. Join Size Bounds using Lp-Norms on Degree Sequences. arXiv:2306.14075 (June 2024). https://doi.org/10.48550/arXiv.2306.14075 arXiv:2306.14075 [cs]

    2024 doi arXiv

  20. [28]

    Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu, and Dan Suciu. 2025. Information Theory Strikes Back: New Development in the Theory of Cardinality Estimation. arXiv:2503.03290 [cs.DB] https://arxiv.org/abs/2503.03290

    2025 arXiv

  21. [30]

    Lieb and Mary Beth Ruskai

    Elliott H. Lieb and Mary Beth Ruskai. 1973. Proof of the strong subadditivity of quantum-mechanical entropy.J. Math. Phys.14, 12 (Dec. 1973), 1938–1941. https://doi.org/10.1063/1.1666274

    1973 doi

  22. [31]

    Noah Linden, Milán Mosonyi, and Andreas Winter. 2013. The structure of Rényi entropic inequalities.Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences(Oct. 2013). https://doi.org/10.1098/rspa.2012.0737

    2013

  23. [32]

    Noah Linden and Andreas Winter. 2005. A New Inequality for the von Neumann Entropy.Communications in Mathematical Physics259, 1 (Oct. 2005), 129–138. https://doi.org/10.1007/s00220-005-1361-2

    2005 doi

  24. [33]

    Tim Littau, Ziyu Li, and Rihan Hai. 2024. Quantum Data Structures for Enhanced Database Performance. InQDSM@VLDB, Guangzhou, China. https://vldb.org/ workshops/2024/proceedings/QDSM/QDSM.6.pdf

    2024

  25. [34]

    Frantisek Matus. 2007. Infinitely Many Information Inequalities. In2007 IEEE International Symposium on Information Theory. 41–44. https://doi.org/10.1109/ ISIT.2007.4557201

    2007

  26. [35]

    Martin Müller-Lennert, Frédéric Dupuis, Oleg Szehr, Serge Fehr, and Marco Tomamichel. 2013. On quantum Rényi entropies: A new gener- alization and some properties.J. Math. Phys.54, 12 (12 2013), 122203. https://doi.org/10.1063/1.4838856 arXiv:https://pubs.aip.org/aip/jmp/artic...

    2013 doi

  27. [37]

    Nitin Nayak, Manuel Schönberger, Valter Uotila, Zhengtong Yan, Sven Groppe, Jiaheng Lu, and Wolfgang Mauerer. 2024. QCE’24 Tutorial: Quantum Annealing – Emerging Exploration for Database Optimization.arXivarXiv:2411.04638 (2024). https://doi.org/10.48550/ARXIV.2411.04638

    2024 doi arXiv

  28. [38]

    Nitin Nayak, Tobias Winker, Umut Çalıkyılmaz, Sven Groppe, and Jinghua Groppe. 2024. Quantum Join Ordering by Splitting the Search Space of QUBO Problems.Datenbank-Spektrum24, 1 (March 2024), 21–32. https://doi.org/10. 1007/s13222-024-00468-3

    2024

  29. [39]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. 2010.Quantum computation and quantum information(10th anniversary ed ed.). Cambridge University Press, Cambridge; New York

    2010

  30. [40]

    Marco Piani, Pawel Horodecki, and Ryszard Horodecki. 2008. No-local- broadcasting theorem for quantum correlations.Physical Review Letters 100, 9 (March 2008), 090502. https://doi.org/10.1103/PhysRevLett.100.090502 arXiv:0707.0848 [quant-ph]

    2008 arXiv

  31. [41]

    Alfréd Rényi. 1961. On measures of entropy and information. InProceedings of the fourth Berkeley symposium on mathematical statistics and probability, volume 1: contributions to the theory of statistics, Vol. 4. University of California Press, 547–562

    1961

  32. [43]

    Manuel Schönberger, Stefanie Scherzinger, and Wolfgang Mauerer. 2023. Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware.Proc. ACM Manag. Data1, 1, Article 92, 27 pages

    2023

  33. [44]

    Manuel Schönberger, Immanuel Trummer, and Wolfgang Mauerer. 2023. Quantum-Inspired Digital Annealing for Join Ordering. InVLDB, Vol. 16

    2023

  34. [45]

    Manuel Schönberger, Immanuel Trummer, and Wolfgang Mauerer. 2023. Quan- tum Optimisation of General Join Trees. InVLDBW’23

    2023

  35. [46]

    C. E. Shannon. 1948. A mathematical theory of communication.The Bell System Technical Journal27, 3 (1948), 379–423. https://doi.org/10.1002/j.1538-7305.1948. tb01338.x

    1948

  36. [47]

    Alexander Streltsov, Gerardo Adesso, and Martin B. Plenio. 2017. Colloquium: Quantum coherence as a resource.Rev. Mod. Phys.89 (Oct 2017), 041003. Issue 4. https://doi.org/10.1103/RevModPhys.89.041003

    2017 doi

  37. [48]

    Andreia Teixeira, Armando Matos, and Luís Antunes. 2012. Conditional Rényi Entropies.IEEE Transactions on Information Theory58, 7 (July 2012), 4273–4277. https://doi.org/10.1109/TIT.2012.2192713

    2012

  38. [49]

    Marco Tomamichel, Mario Berta, and Masahito Hayashi. 2014. Relating different quantum generalizations of the conditional Renyi entropy.J. Math. Phys.55, 8 (Aug. 2014), 082206. https://doi.org/10.1063/1.4892761 arXiv:1311.3887 [quant- ph]

    2014 arXiv

  39. [51]

    Immanuel Trummer and Christoph Koch. 2016. Multiple query optimization on the D-Wave 2X adiabatic quantum computer.VLDB9, 9 (May 2016), 648–659. https://doi.org/10.14778/2947618.2947621

    2016

  40. [52]

    Immanuel Trummer and Davide Venturelli. 2024. Leveraging Quantum Comput- ing for Database Index Selection. InQ-Data (SIGMOD/PODS ’24). ACM, 14–26. https://doi.org/10.1145/3665225.3665445

    2024

  41. [53]

    Valter Uotila. 2024. SQL2Circuits: Estimating Metrics for SQL Queries with a Quantum Natural Language Processing Method. arXiv:2306.08529 [cs.DB] https://arxiv.org/abs/2306.08529

    2024

  42. [54]

    Valter Uotila. 2025. GitHub code examples: size bounds for conjunctive queries. https://github.com/valterUo/size-bounds-for-conjunctive-queries. Accessed: 2025-06-09

    2025

  43. [55]

    Valter Uotila. 2025. Left-Deep Join Order Selection with Higher-Order Uncon- strained Binary Optimization on Quantum Computers. arXiv:2502.00362 [quant- ph] https://arxiv.org/abs/2502.00362

    2025 arXiv

  44. [56]

    Valter Uotila and Jiaheng Lu. 2023. Quantum Annealing Method for Dynamic Virtual Machine and Task Allocation in Cloud Infrastructures from Sustainabil- ity Perspective. In2023 IEEE 39th International Conference on Data Engineering Workshops (ICDEW). 105–110. https://doi.org/10...

    2023

  45. [57]

    V. Vedral. 2002. The Role of Relative Entropy in Quantum Information Theory. Reviews of Modern Physics74, 1 (March 2002), 197–234. https://doi.org/10.1103/ RevModPhys.74.197 arXiv:quant-ph/0102094

    2002 arXiv

  46. [58]

    Martin Vogrin, Rok Vogrin, Sven Groppe, and Jinghua Groppe. 2024. Su- pervised Learning on Relational Databases with Quantum Graph Neural Net- works. InQDSM@VLDB, Guangzhou, China. https://vldb.org/workshops/2024/ proceedings/QDSM/QDSM.5.pdf

    2024

  47. [59]

    Tobias Winker, Umut Çalikyilmaz, Le Gruenwald, and Sven Groppe. 2023. Quantum Machine Learning for Join Order Optimization using Variational Quantum Circuits. InProceedings of the International Workshop on Big Data in Emergent Distributed Environments(Seattle, WA, USA)(BiDEDE ...

    2023

  48. [60]

    Tobias Winker, Sven Groppe, Valter Uotila, Zhengtong Yan, Jiaheng Lu, Maja Franz, and Wolfgang Mauerer. 2023. Quantum Machine Learning: Foundation, New Techniques, and Opportunities for Database Research. InCompanion of the 2023 International Conference on Management of Data(S...

    2023

  49. [61]

    Andreas Winter and Dong Yang. 2016. Operational Resource Theory of Coher- ence.Phys. Rev. Lett.116 (Mar 2016), 120404. Issue 12. https://doi.org/10.1103/ PhysRevLett.116.120404

    2016

  50. [62]

    Haozhe Zhang, Christoph Mayer, Mahmoud Abo Khamis, Dan Olteanu, and Dan Suciu. 2025. LpBound: Pessimistic Cardinality Estimation using ℓ𝑝 -Norms of Degree Sequences. arXiv:2502.05912 (Feb. 2025). https://doi.org/10.48550/arXiv. 2502.05912 arXiv:2502.05912 [cs]

    2025 doi arXiv

  51. [63]

    Zhen Zhang and R.W. Yeung. 1998. On characterization of entropy function via information inequalities.IEEE Transactions on Information Theory44, 4 (1998), 1440–1452. https://doi.org/10.1109/18.681320

    1998 doi

  52. [64]

    Umut Çalıkyılmaz, Sven Groppe, Jinghua Groppe, Tobias Winker, Stefan Prestel, Farida Shagieva, Daanish Arya, Florian Preis, and Le Gruenwald. 2023. Oppor- tunities for Quantum Acceleration of Databases: Optimization of Queries and Transaction Schedules.VLDB16, 9 (2023), 2344–2...

    2023

  53. [2023]

    https://doi.org/10.1109/access.2023.3324253

    Multiple Query Optimization Using a Gate-Based Quantum Computer.IEEE Access11 (2023), 114031–114043. https://doi.org/10.1109/access.2023.3324253

    2023

  54. [2025]

    arXiv:2409.14111 [quant-ph] https://arxiv.org/abs/2409.14111

    Quantum Data Management in the NISQ Era: Extended Version. arXiv:2409.14111 [quant-ph] https://arxiv.org/abs/2409.14111

    arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.