Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

Left-Deep Join Order Selection with Higher-Order Unconstrained Binary Optimization on Quantum Computers

T0 review · 4 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read This paper claims that a higher-order unconstrained binary optimization model can encode left-deep join order selection so exactly that minimizing it matches the cost of dynamic programming without cross-products, with a heuristic variant…

desk verdict The HUBO encoding is a real step forward, but Theorem 5.1 proves representability, not optimality, and the validity constraints are internally inconsistent. read the letter →

arxiv 2502.00362 v1 pith:EYFKWKEN submitted 2025-02-01 quant-ph cs.DB

Valter Uotila This is my paper · ORCID
classification quant-phcs.DB
keywords joinorderselectionhigher-orderunconstrainedbinaryoptimizationquantumcomputingleft-deeptreesquerydynamicprogrammingannealingQUBO
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

Join order optimization chooses the sequence in which a database joins tables, and a left-deep plan always combines the current intermediate result with one new table. The paper claims that this choice can be encoded as a higher-order unconstrained binary optimization (HUBO) problem—a polynomial over true/false variables whose terms may multiply more than two variables—and that two of its three proposed encodings are the first quantum-oriented formulations to model the join order cost function exactly. The main theorem states that minimizing the cost HUBO together with validity constraints returns exactly the cost of the classical dynamic programming algorithm that forbids cross-products, while a third heuristic encoding is proven no worse than the greedy algorithm without cross-products. Because HUBO problems map naturally to universal quantum computers and to quantum annealers, this connects the quantum search to the standard classical baseline and, if correct, gives a route from small quantum devices to a meaningful database optimization problem.

What carries the argument

The load-bearing object is the ranked-join HUBO. For a query graph $G=(V,E)$, the binary variable $x^r_{i,j}$ means that the join between relations $R_i$ and $R_j$ is performed at rank $r$, where ranks run from $0$ to $|V|-2$. A term of the objective is a product of such variables across consecutive ranks, representing a connected subgraph of the query graph whose tables have been joined so far; its coefficient is the product of all selectivities inside that subgraph times the cardinalities of all its tables, which is exactly the intermediate-result cardinality. Summing these local cardinality terms reproduces the recursive cost function, so the value of the cost HUBO at a valid assignment is the true join plan cost. Validity constraints then force exactly one join per rank, keep previously chosen joins active, and respect the shape of the query graph, and the full objective is $H_{\mathrm{full}}=H_{\mathrm{cost}}+C H_{\mathrm{val}}$.

What would settle it

Enumerate all binary assignments for a small query graph (e.g., a 5-cycle or a 4-relation tree) with randomly chosen cardinalities and selectivities, compute $H_{\mathrm{cost}} + C H_{\mathrm{val}}$ exactly, and check whether every global minimizer corresponds to a valid left-deep join tree that adheres to the query graph and has the cost returned by dynamic programming without cross-products. A single instance where the minimizer is invalid, or where its cost differs from the DP cost, would refute Theorem 5.1 as stated.

Watch

Extended reading notes

Core claim

The central claim is Theorem 5.1: let $H_{\mathrm{cost}}$ be the cost HUBO of Section 3.1, let $H_{\mathrm{val}}$ be the binary validity constraints, and let $x$ minimize $H_{\mathrm{cost}} + C H_{\mathrm{val}}$; then $H_{\mathrm{cost}}(x)$ equals the cost computed by dynamic programming without cross-products. The paper also claims that this is the first quantum computing formulation of join order selection that precisely models the cost function, and Theorem 5.2 shows that the heuristic variant produces a plan whose cost is at most the greedy algorithm's cost without cross-products. In the reported experiments on clique, cycle, star, tree, and chain query graphs, both bounds are respected in practice, and the encoding uses one binary variable type for most graphs (two for cliques) instead of the four used by earlier quantum join-order formulations.

Load-bearing premise

The argument depends on the assumption, not proven in the paper, that the penalty weight $C = H_{\mathrm{cost}}((1,\ldots,1))$ is large enough that every global minimizer of the combined objective is a valid left-deep join tree; the paper chose this value because it worked consistently in practice, and if an invalid low-cost solution wins, the claimed equality to dynamic programming collapses.

Editorial extensions

If this is right

  • If Theorem 5.1 is correct, any solver that finds the global minimum of the HUBO—quantum or classical—returns a plan whose cost matches dynamic programming without cross-products, so the known optimality gap is only the gap caused by excluding cross-products.
  • The single-variable-type formulation and the use of query graph structure make the encoding smaller than earlier quantum join-order models, which used four variable types and grew exponentially for some cases.
  • The heuristic variant's guarantee, at least as good as greedy without cross-products, extends the same encodings to larger instances; the reported experiments reach 60 relations on chains, cycles, trees, and stars.
  • Because HUBO terms map natively to universal quantum computers and to quantum annealers after a HUBO-to-QUBO reduction, the same cost model can be run on both hardware paradigms without changing the problem statement.
  • If the precise formulation is solved by a quantum annealer after reduction, the result quality is expected to match the DP-without-cross-products baseline, with the practical caveat that current noisy hardware may fail to reach the global minimum.

Reading between the lines

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

  • The cost construction itself does not use left-deepness: the coefficient in Eq. (10) is the cardinality of a subgraph regardless of how its tables were combined, so the same term-generation rule should extend to bushy join trees by relaxing the per-rank validity constraints.
  • The penalty weight $C = H_{\mathrm{cost}}(\mathbf{1})$ is an empirical choice; a counterexample instance where an invalid assignment wins would only disprove the theorem's premise for that $C$, and a larger $C$ could restore the guarantee, suggesting the missing piece is a proof that some bounded $C$ always suffices.
  • A concrete testable extension is to check whether the same HUBO reproduces the dynamic programming-with-cross-products optimum when star or chain selectivities are varied: if it does not, the gap is precisely the cross-product-free restriction, which the paper treats as the accepted classical baseline.
  • The rank-based variable scheme is not tied to quantum hardware, so even if quantum solvers remain uncompetitive, the HUBO formulation could serve as a compact classical encoding whose exact optimum is comparable to dynamic programming without cross-products.
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

4 major / 5 minor

Summary. The paper proposes three higher-order unconstrained binary optimization (HUBO) formulations for left-deep join order selection: a precise cost HUBO, a heuristic cost HUBO, and two families of validity constraints. The central theoretical claims are Theorem 5.1, that the global minimizer of the full objective Hcost + C Hval has cost equal to that of dynamic programming without cross-products, and Theorem 5.2, that the heuristic variant achieves cost at most that of the greedy algorithm without cross-products. The paper also reports an experimental evaluation on thousands of clique, cycle, star, tree, and chain query graphs using quantum annealers and classical solvers.

Significance. If the main theorem were established, the paper would provide a useful theoretical bridge between classical join-order optimization and quantum/HUBO formulations, and the variable construction that avoids exponential blowup would be a genuine contribution. The paper also deserves credit for releasing anonymized code, for experimenting with a wide range of query graph shapes, and for attempting to connect HUBO models to both quantum annealers and gate-based quantum computers. However, the central theorem is not proven as stated, and the validity constraints contain internal inconsistencies. Since the abstract and introduction advertise 'precisely model' and 'same plans as DP' as the main results, these gaps are load-bearing rather than cosmetic.

major comments (4)
  1. [Section 5, Theorem 5.1 and its proof] The proof argues by induction that for each rank the cost HUBO contains terms encoding the same intermediate joins as the DP table and concludes that 'there is a point where Hcost achieves the same cost as the DP algorithm.' This establishes representability only. The theorem, however, concerns the global minimizer x of Hcost + C Hval. The proof never shows that this minimizer is a valid left-deep join tree, nor that Hcost(x) equals the DP value, nor that the best valid assignment is preferred over every invalid assignment. Without a lower bound on C and a domination argument for valid over invalid configurations, the claimed equality to dynamic programming does not follow. This gap is load-bearing because the abstract's 'precisely model' and 'encode the same plans' claims rest on it.
  2. [Section 4.2, Eq. (16) and penalty scaling] The model sets C = Hcost((1,...,1)) because this value 'worked consistently in practice,' but no analysis is provided that this C is large enough. This is not a minor tuning detail: Eq. (16) explicitly contains negative coefficients -C, so Hval is not a nonnegative penalty. An invalid assignment that activates many terms of the form x^r_{i,j} x^r_{i',j'} with |{i,j} ∩ {i',j'}| = 1 can obtain Hval < 0 and thereby offset a large Hcost. The proof of Theorem 5.1 therefore cannot rely on C dominating invalid solutions; a concrete argument or counterexample is needed to rule out low-cost invalid global minima.
  3. [Section 4.2, Eqs. (14)-(15) vs. Section 3, Eq. (7) and Example 3.1] The variable semantics are internally inconsistent. Section 3 defines x^r_{i,j} to mean that the join (R_i,R_j) is performed at rank r, and Example 3.1 uses exactly one active variable per rank. Eq. (15), however, requires x^{r-1}_{i,j}=1 to imply x^r_{i,j}=1, which is a cumulative interpretation of the same variable. Eq. (14) similarly requires r+1 active variables at rank r rather than one. Consequently the object Hval that appears in Theorem 5.1 is not uniquely defined, and it is unclear whether the theorem refers to the cost-function-independent validity constraints for clique graphs, for chain/star/cycle graphs, or for tree graphs.
  4. [Section 5, Theorem 5.2] The proof of Theorem 5.2 has the same structure as Theorem 5.1: it shows that the greedy plan can be encoded as terms in the heuristic HUBO and then concludes H(x) ≤ C_greedy for the minimizer x. This does not follow. The minimizer could be an invalid assignment, or a valid assignment whose full objective is lower than the encoded greedy plan for reasons unrelated to the greedy prefix. The proof gives no argument that the full objective value of the encoded greedy plan is no larger than C_greedy, nor that no other assignment has lower full objective. Thus the greedy bound is also unproven.
minor comments (5)
  1. [Section 4.1, Eq. (11)] The notation in Eq. (11) is unclear: h ranges over a set H of higher-order terms, but the definition of h as a product over ranks with indices i_r, j_r is introduced only in prose; writing h explicitly would improve readability.
  2. [Algorithm 1, line 7] The pseudocode line 'joined_tables <- [tables if r-1 var in HUBO[tables]]' is not formally defined; the dictionary representation and the meaning of 'tables' should be specified precisely.
  3. [Example 3.1] The phrase 'left-deep join tree[[0,1],2],3]' contains an unbalanced bracket; it should read '((0⋈1)⋈2)⋈3' or an equivalent well-parenthesized form.
  4. [Appendix D] The statement that the experimental results demonstrate that Theorems 5.1 and 5.2 are 'respected well in practice' is too strong: exact poly solver results only show that the HUBO objective, when optimized, matches DP on the tested instances; they cannot substitute for the missing proof about the global minimizer.
  5. [Abstract and Section 1] The claim that two algorithms are 'the first quantum algorithms to precisely model the join order cost function' depends on Theorem 5.1; given the proof gap, this claim should be softened or supported.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the HUBO encoding is constructed from the query graph and recursive cost function, and the DP comparison is an independent correctness argument rather than a fitted or self-citational prediction.

full rationale

The central construction is not circular. The cost HUBO in Section 3.1 is built directly from the query graph and the recursive cost definition in Eq. (2), using Algorithm 1 to enumerate connected-subgraph join plans; it does not take the DP algorithm's outputs as inputs. Theorem 5.1 then compares this enumeration with the DP table by induction, which is an equivalence/correctness argument rather than a reduction of the claimed result to an input. The validity constraints are separate penalty terms, and the penalty scale C = Hcost(1,...,1) is a hand-tuned multiplier rather than a parameter fitted to the DP optimum, so no fitted value is relabeled as a prediction. The author's self-citations (e.g., [53], [54], [55], [60]) appear in related-work and motivation contexts and are not load-bearing for the derivation. The proof gap noted in the paper's Theorem 5.1 argument -- it asserts a property of the global minimizer but only demonstrates existence of an assignment achieving the DP cost, and the choice of C is not rigorously justified -- is a correctness or completeness weakness, not circularity. No uniqueness theorem, ansatz, or external result from the authors' prior work is invoked to force the model choice. The paper is self-contained against the external DP benchmark, and the derivation's core content is independent of the citations.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central construction rests on the standard recursive join cost model, an unproved penalty bound for C, and the correctness of the validity constraints. The penalty bound is the most fragile free parameter because the theorem's global-minimizer claim depends on it. The heuristic n is an unreported tuning parameter. No new physical entities are introduced.

free parameters (2)
  • penalty weight C = C = Hcost(x) with x = (1,...,1), after normalizing coefficients to (0,1]
    Chosen empirically in Section 4.2 because it 'worked consistently in practice'; the theorem requires a provable bound, not a tuned value.
  • heuristic beam width n = not reported
    Section 3.2 introduces a tunable n for the number of cheapest rank terms kept; the experiments do not state the value used, which also hurts reproducibility.
assumptions (3)
  • domain assumption Join cardinalities factor as products of selectivities of all edges in the induced subgraph, with missing edges treated as selectivity 1.
    This is assumed in Eqs. (8)-(10) to compute intermediate result cardinalities; it is a standard simple cost model but can be false with correlated predicates.
  • ad hoc to paper The penalty C = Hcost((1,...,1)) is large enough that any invalid join tree has higher full objective value than the optimal valid join tree.
    Invoked implicitly by the theorem statements; no proof or bound is given.
  • domain assumption The validity constraints in Section 4.2 enumerate exactly the valid left-deep join trees adhering to the query graph for each graph class.
    This is the intended meaning of Hval in Theorems 5.1-5.2, but the text has internal inconsistencies (Eq. 14 vs Example 3.1).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Left-Deep Join Order Selection with Higher-Order Unconstrained Binary Optimization on Quantum Computers." pith.science (2026). https://pith.science/paper/EYFKWKEN

@misc{pith2026250200362,
  author       = {Pith},
  title        = {Pith review of: Left-Deep Join Order Selection with Higher-Order Unconstrained Binary Optimization on Quantum Computers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EYFKWKEN}},
  note         = {Machine review of arXiv:2502.00362}
}
read the original abstract

Join order optimization is among the most crucial query optimization problems, and its central position is also evident in the new research field where quantum computing is applied to database optimization and data management. In the field, join order optimization is the most studied database problem, usually tackled with a quadratic unconstrained binary optimization model, which is solved with various meta-heuristics such as quantum annealing, quantum approximate optimization algorithm, or variational quantum eigensolver. In this work, we continue developing quantum computing techniques for join order optimization by presenting three novel quantum optimization algorithms. These algorithms are based on a higher-order unconstrained binary optimization model, which is a generalization of the quadratic model and has not previously been applied to database problems. Theoretically, these optimization problems naturally map to universal quantum computers and quantum annealers. Compared to previous research, two of our algorithms are the first quantum algorithms to precisely model the join order cost function. We prove theoretical bounds by showing that these two methods encode the same plans as the dynamic programming algorithm without cross-products, which provides the optimal result up to cross-products. The third algorithm reaches at least as good plans as the greedy algorithm without cross-products. These results set an important theoretical connection between the classical and quantum algorithms for join order selection, which has not been studied in the previous research. To demonstrate our algorithms' practical usability, we have conducted an experimental evaluation on thousands of clique, cycle, star, tree, and chain query graphs using quantum and classical solvers.

Figures

Figures reproduced from arXiv: 2502.00362 by the authors.

Figure 1
Figure 1. SQL query and its corresponding query graph [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Two examples for variable generation in tree query graph [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. We compare the number of mandatory variables in [ [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (15 more)
Figure 4
Figure 4. Figure 4: Circuit implementing the Hamiltonian 𝐻 = 2𝜎 0 𝑧 ⊗ 𝜎 1 𝑧 ⊗ 𝜎 2 𝑧 measurement. Now the sum is the weighted average of the eigenvalues which are precisely the measurement results when measuring the observable: the eigenvalues 𝜆𝑗 are the measurement outcomes, and |⟨𝜑|𝜆𝑗⟩|2…
Figure 5
Figure 5. Figure 5: Precise 1 results using the D-Wave’s exact poly solver [PITH_FULL_IMAGE:figures/full_fig_p023_5.png]
Figure 6
Figure 6. Figure 6: Precise 1 results using Gurobi solver the dynamic program algorithm without the cross products, with some exceptions due to the heuristic nature of the quantum computer: Cycle-6, Chain-7, and Tree-6 [PITH_FULL_IMAGE:figures/full_fig_p024_6.png]
Figure 7
Figure 7. Figure 7: Precise 1 results using D-Wave’s Leap Hybrid solver [PITH_FULL_IMAGE:figures/full_fig_p024_7.png]
Figure 8
Figure 8. Figure 8: Precise 1 results using D-Wave’s standard solver [PITH_FULL_IMAGE:figures/full_fig_p024_8.png]
Figure 9
Figure 9. Figure 9: Precise 2 results using the D-Wave’s exact poly solver [PITH_FULL_IMAGE:figures/full_fig_p025_9.png]
Figure 10
Figure 10. Figure 10: Precise 2 results using Gurobi solver [PITH_FULL_IMAGE:figures/full_fig_p025_10.png]
Figure 11
Figure 11. Figure 11: Precise 2 results using Gurobi solver to obtain better results. On the other hand, we used the developer access to the solver, which is limited to only one minute of quantum computing access per month. Finally, we did not include the results from the D-wave quantum so…
Figure 12
Figure 12. Figure 12: Precise 2 results using D-Wave’s Leap Hybrid solver [PITH_FULL_IMAGE:figures/full_fig_p025_12.png]
Figure 13
Figure 13. Figure 13: Heuristic results for clique query graphs using Gurobi solver [PITH_FULL_IMAGE:figures/full_fig_p026_13.png]
Figure 14
Figure 14. Figure 14: Heuristic results for tree query graphs using Gurobi solver [PITH_FULL_IMAGE:figures/full_fig_p026_14.png]
Figure 15
Figure 15. Figure 15: Heuristic results for chain query graphs using Gurobi solver [PITH_FULL_IMAGE:figures/full_fig_p026_15.png]
Figure 16
Figure 16. Figure 16: Heuristic results for cycle query graphs using Gurobi solver [PITH_FULL_IMAGE:figures/full_fig_p027_16.png]
Figure 17
Figure 17. Figure 17: A figure with two subfigures [PITH_FULL_IMAGE:figures/full_fig_p027_17.png]
Figure 18
Figure 18. Figure 18: A figure with two subfigures [PITH_FULL_IMAGE:figures/full_fig_p028_18.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

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

    quant-ph 2025-06 reject novelty 5.0 of 10

    Worst-case conjunctive query size bounds can be reformulated with quantum Rényi entropy, producing sound but generally non-tight upper bounds whose classical tight version is recovered only in the α→1 limit.

Reference graph

Works this paper leans on

63 extracted references · 29 canonical work pages · cited by 1 Pith paper

  1. [1]

    Scott Aaronson and Lijie Chen. 2016. Complexity-Theoretic Foundations of Quantum Supremacy Experiments. arXiv:1612.05903 [quant-ph] https://arxiv.org/abs/1612.05903

    arXiv 2016

  2. [2]

    Amira Abbas and et al. 2024. Quantum Optimization: Potential, Challenges, and the Path Forward. arXiv:2312.02279 [quant-ph] https://arxiv.org/abs/2312.02279

    arXiv 2024

  3. [3]

    Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. 2004. Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. (2004). https://doi.org/10.48550/ARXIV.QUANT- PH/0405098

    doi:10.48550/arxiv.quant- 2004

  4. [4]

    Tameem Albash and Daniel A. Lidar. 2018. Adiabatic quantum computation. Rev. Mod. Phys. 90 (Jan 2018), 015002. Issue 1. https://doi.org/10.1103/RevModPhys.90.015002 111:16 Uotila

    doi:10.1103/revmodphys.90.015002 2018

  5. [5]

    Anonymous. 2024. Q-Join GitHub Repository. https://anonymous.4open.science/r/Q-Join-PODS25. Accessed: 2024-12-08

    work page 2024

  6. [6]

    Apolloni, C

    B. Apolloni, C. Carvalho, and D. de Falco. 1989. Quantum stochastic optimization. Stochastic Processes and their Applications 33, 2 (1989), 233–244. https://doi.org/10.1016/0304-4149(89)90040-9

    doi:10.1016/0304-4149(89)90040-9 1989

  7. [7]

    Katzgraber

    Maliheh Aramon, Gili Rosenberg, Elisabetta Valiante, Toshiyuki Miyazawa, Hirotaka Tamura, and Helmut G. Katzgraber

    work page

  8. [8]

    Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G

    Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, St...

    2019

Show all 63 references
  1. [9]

    Tim Bittner and Sven Groppe. 2020. Avoiding blocking by scheduling transactions using quantum annealing. In Proceedings of the 24th Symposium on International Database Engineering & Applications (IDEAS ’20) . Association for Computing Machinery, New York, NY, USA, 1–10. https:...

    2020

  2. [10]

    Endre Boros and Peter L. Hammer. 2002. Pseudo-Boolean optimization. Discrete Applied Mathematics 123, 1 (2002), 155–225. https://doi.org/10.1016/S0166-218X(01)00341-9

    2002 doi

  3. [11]

    Sophie Cluet and Guido Moerkotte. 1995. On the complexity of generating optimal left-deep processing trees with cross products. In International Conference on Database Theory . Springer, 54–67

    1995

  4. [12]

    D-Wave. [n. d.]. What is Quantum Annealing? — D-Wave System Documentation documentation. https://docs. dwavesys.com/docs/latest/c_gs_2.html

  5. [13]

    D-Wave. 2024. Reformulating a Problem — D-Wave System Documentation documentation. https://docs.dwavesys. com/docs/latest/handbook_reformulating.html#non-quadratic-higher-degree-polynomials

    2024

  6. [14]

    D-Wave Systems Inc. 2024. dimod.generators.combinations. https://docs.ocean.dwavesys.com/en/stable/docs_dimod/ reference/generated/dimod.generators.combinations.html. Accessed: 2024-10-12

    2024

  7. [15]

    Denchev, Sergio Boixo, Sergei V

    Vasil S. Denchev, Sergio Boixo, Sergei V. Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, and Hartmut Neven. 2016. What is the Computational Value of Finite-Range Tunneling? Phys. Rev. X 6 (Aug 2016), 031015. Issue 3. https://doi.org/10.1103/PhysRevX.6.031015

    2016 doi

  8. [16]

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 [quant-ph]

    2014 arXiv

  9. [17]

    Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. 2000. Quantum Computation by Adiabatic Evolution. arXiv:quant-ph/0001106 (Jan. 2000). https://doi.org/10.48550/arXiv.quant-ph/0001106 arXiv:quant- ph/0001106

    2000 doi arXiv

  10. [18]

    Maja Franz, Tobias Winker, Sven Groppe, and Wolfgang Mauerer. 2024. Hype or Heuristic? Quantum Reinforcement Learning for Join Order Optimisation. arXiv:2405.07770 (May 2024). https://doi.org/10.48550/arXiv.2405.07770 arXiv:2405.07770 [quant-ph]

    2024 doi arXiv

  11. [19]

    Kristin Fritsch and Stefanie Scherzinger. 2023. Solving Hard Variants of Database Schema Matching on Quantum Computers. Proceedings of the VLDB Endowment 16, 12 (Aug. 2023), 3990–3993. https://doi.org/10.14778/3611540. 3611603

    2023 doi

  12. [20]

    Sukhpal Singh Gill, Adarsh Kumar, Harvinder Singh, Manmeet Singh, Kamalpreet Kaur, Muhammad Us- man, and Rajkumar Buyya. 2022. Quantum computing: A taxonomy, systematic review and future directions. Software: Practice and Experience 52, 1 (2022), 66–114. https://doi.org/10.100...

    2022 doi

  13. [21]

    Ovchinnikov

    Rudolf Grimm, Matthias Weidemüller, and Yurii B. Ovchinnikov. 2000. Optical Dipole Traps for Neutral Atoms. Advances In Atomic, Molecular, and Optical Physics, Vol. 42. Academic Press, 95–170. https://doi.org/10.1016/S1049- 250X(08)60186-X

    2000 doi

  14. [22]

    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. Joint Workshops at 49th International Conference on Very Large Data Bases (VLDBW’23) — Internati...

    2023

  15. [23]

    Harrow and A

    A. Harrow and A. Montanaro. 2017. Quantum computational supremacy. Nature 549 (2017), 203–209. https: //doi.org/10.1038/nature23458

    2017 doi

  16. [24]

    Toshihide Ibaraki and Tiko Kameda. 1984. On the optimal nesting order for computing N-relational joins. ACM Trans. Database Syst. 9, 3 (Sept. 1984), 482–502. https://doi.org/10.1145/1270.1498

    1984

  17. [25]

    Stephen Jordan. 2022. Quantum Algorithm Zoo. https://quantumalgorithmzoo.org/. Accessed: 2024-08-20

    2022

  18. [26]

    Tadashi Kadowaki and Hidetoshi Nishimori. 1998. Quantum annealing in the transverse Ising model. Phys. Rev. E 58 (Nov 1998), 5355–5363. Issue 5. https://doi.org/10.1103/PhysRevE.58.5355

    1998 doi

  19. [27]

    Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout van den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, and Abhinav Kandala. 2023. Evidence for the utility of quantum computing before fault tolerance. Nature 618, 79657965 (June 2...

    2023 doi

  20. [28]

    King, Alberto Nocera, Marek M

    Andrew D. King, Alberto Nocera, Marek M. Rams, Jacek Dziarmaga, Roeland Wiersema, William Bernoudy, Jack Raymond, Nitin Kaushal, Niclas Heinsdorf, Richard Harris, Kelly Boothby, Fabio Altomare, Andrew J. Berkley, Martin Boschnak, Kevin Chern, Holly Christiani, Samantha Cibere,...

    2024

  21. [29]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. 1983. Optimization by Simulated Annealing.Science 220, 4598 (1983), 671–

    1983

  22. [31]

    Emanuel Knill, Raymond Laflamme, and Gerald J Milburn. 2001. A scheme for efficient quantum computation with linear optics. nature 409, 6816 (2001), 46–52

    2001

  23. [32]

    Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015. How good are query optimizers, really? Proc. VLDB Endow. 9, 3 (Nov. 2015), 204–215. https://doi.org/10.14778/2850583.2850594

    2015

  24. [33]

    Andrew Lucas. 2014. Ising formulations of many NP problems. Frontiers in Physics 2 (2014). https://doi.org/10.3389/ fphy.2014.00005 arXiv: 1302.5843

    2014

  25. [34]

    Madsen, Fabian Laudenbach, Mohsen Falamarzi Askarani, Fabien Rortais, Trevor Vincent, Jacob F

    Lars S. Madsen, Fabian Laudenbach, Mohsen Falamarzi Askarani, Fabien Rortais, Trevor Vincent, Jacob F. F. Bulmer, Filippo M. Miatto, Leonhard Neuhaus, Lukas G. Helt, Matthew J. Collins, Adriana E. Lita, Thomas Gerrits, Sae Woo Nam, Varun D. Vaidya, Matteo Menotti, Ish Dhand, Z...

    2022 doi

  26. [35]

    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-Spektrum (March 2024). https://doi.org/10.1007/s13222- 024-00468-3

    2024 doi

  27. [36]

    P Neumann, N Mizuochi, F Rempp, Philip Hemmer, H Watanabe, S Yamasaki, V Jacques, Torsten Gaebel, F Jelezko, and J Wrachtrup. 2008. Multipartite entanglement among single spins in diamond. science 320, 5881 (2008), 1326–1329

    2008

  28. [37]

    Thomas Neumann. [n. d.]. Query Optimization. ([n. d.])

  29. [38]

    Thomas Neumann and Bernhard Radke. 2018. Adaptive Optimization of Very Large Join Queries. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD ’18) . Association for Computing Machinery, New York, NY, USA, 677–692. https://doi.org/10.1145/3183713.3183733

    2018

  30. [39]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. 2010. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press

    2010

  31. [40]

    Wolfgang Paul. 1990. Electromagnetic traps for charged and neutral particles. Reviews of modern physics 62, 3 (1990), 531

    1990

  32. [41]

    Love, Alán Aspuru-Guzik, and Jeremy L

    Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien. 2014. A variational eigenvalue solver on a photonic quantum processor.Nature Communications 5, 11 (July 2014), 4213. https://doi.org/10.1038/n...

    2014 doi

  33. [42]

    Bakalov, Frédéric Sauvage, Alexander F

    Michael Ragone, Bojko N. Bakalov, Frédéric Sauvage, Alexander F. Kemper, Carlos Ortiz Marrero, Martín Larocca, and M. Cerezo. 2024. A Lie algebraic theory of barren plateaus for deep parameterized quantum circuits. Nature 111:18 Uotila Communications 15, 1 (Aug. 2024), 7172. h...

    2024 doi

  34. [44]

    Manuel Schönberger, Stefanie Scherzinger, and Wolfgang Mauerer. 2023. Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware. Proc. ACM Manag. Data 1, 1, Article 92 (may 2023), 27 pages. https: //doi.org/10.1145/3588946

    2023 doi

  35. [45]

    Manuel Schönberger, Immanuel Trummer, and Wolfgang Mauerer. 2023. Quantum-Inspired Digital Annealing for Join Ordering. Proc. VLDB Endow. 17, 3 (Nov. 2023), 511–524. https://doi.org/10.14778/3632093.3632112

    2023

  36. [46]

    Manuel Schönberger. 2022. Applicability of Quantum Computing on Database Query Optimization. In Proceedings of the 2022 International Conference on Management of Data . ACM, Philadelphia PA USA, 2512–2514. https://doi.org/10. 1145/3514221.3520257

    2022

  37. [47]

    Manuel Schönberger, Immanuel Trummer, and Wolfgang Mauerer. 2023. Quantum Optimisation of General Join Trees. Joint Workshops at 49th International Conference on Very Large Data Bases (VLDBW’23) — International Workshop on Quantum Data Science and Management (QDSM’23) (Sept. 2023)

    2023

  38. [48]

    Griffiths Selinger, M

    P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. 1979. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data (Boston, Massachusetts) (SIGMOD ’...

    1979

  39. [49]

    Michael Steinbrunn, Guido Moerkotte, and Alfons Kemper. 1997. Heuristic and randomized optimization for the join ordering problem. The VLDB Journal 6, 3 (Aug. 1997), 191–208. https://doi.org/10.1007/s007780050040

    1997 doi

  40. [50]

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

    2016

  41. [51]

    Immanuel Trummer and Christoph Koch. 2017. Solving the Join Ordering Problem via Mixed Integer Linear Program- ming. In Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD ’17) . Association for Computing Machinery, New York, NY, USA, 1025–1040. ...

    2017

  42. [52]

    Immanuel Trummer and Davide Venturelli. 2024. Leveraging Quantum Computing for Database Index Selection. In Workshop on Quantum Computing and Quantum-Inspired Technology for Data-Intensive Systems and Applications, Q-Data 2024, Santiago, Chile, June 9-15, 2024 , Ibrahim Sabek,...

    2024

  43. [53]

    Valter Uotila. 2022. Synergy between Quantum Computers and Databases. Proceedings of the VLDB 2022 PhD Workshop co-located with the 48th International Conference on Very Large Databases (VLDB 2022) 3186 (Sept. 2022), 4

    2022

  44. [54]

    Valter Uotila. 2023. SQL2Circuits: Estimating Metrics for SQL Queries with A Quantum Natural Language Processing Method. arXiv:2306.08529 (June 2023). https://doi.org/10.48550/arXiv.2306.08529 arXiv:2306.08529 [quant-ph]

    2023 doi

  45. [55]

    Valter Uotila. 2024. Tensor Decompositions and Adiabatic Quantum Computing for Discovering Practical Matrix Multiplication Algorithms. In 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) . arXiv:2406.13412 [quant-ph] https://arxiv.org/abs/2406.13412

    2024 arXiv

  46. [56]

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

    2023

  47. [57]

    Zoé Verchère, Sourour Elloumi, and Andrea Simonetto. 2023. Optimizing Variational Circuits for Higher-Order Binary Optimization. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) , Vol. 01. 19–25. https://doi.org/10.1109/QCE57702.2023.00011

    2023

  48. [58]

    G Wendin. 2017. Quantum information processing with superconducting circuits: a review. Reports on Progress in Physics 80, 10 (sep 2017), 106001. https://doi.org/10.1088/1361-6633/aa7e1a

    2017 doi

  49. [59]

    Gonzalez Calaza, Fengping Jin, Hans De Raedt, Marika Svensson, and Kristel Michielsen

    Dennis Willsch, Madita Willsch, Carlos D. Gonzalez Calaza, Fengping Jin, Hans De Raedt, Marika Svensson, and Kristel Michielsen. 2022. Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems. Quantum Information Processing 21, 4 (April 2022), 141. h...

    2022 doi

  50. [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. In Companion of the 2023 International Conference on Management of Data ...

    2023

  51. [61]

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

    2023

  52. [62]

    Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-...

    2020 doi

  53. [63]

    Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong- Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chu...

    2021 doi arXiv

  54. [680]

    https://doi.org/10.1126/science.220.4598.671 arXiv:https://www.science.org/doi/pdf/10.1126/science.220.4598.671

    doi

  55. [2019]

    Frontiers in Physics 7 (April 2019), 48

    Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer. Frontiers in Physics 7 (April 2019), 48. https://doi.org/10.3389/fphy.2019.00048

    2019

Pith tools

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