Created by Valter Uotila

lead by Jiaheng Lu

Problem: modern database management systems do not have a solid theoretical foundation.

Oracle started promoting category theory as a theoretical foundation for various database concepts.

Category theory is very applicable: we published some results in VLDB'21 and its workshops.

Applied category theory for multi-model databases

Quantum computing does not yet outperform classical computers in real-life applications but...

...it might be more sustainable to operate and ...

... we can avoid making ethical mistakes. For example, see Gender BIAS in AI: Perspectives of AI Practitioners.

Initial paper in Nature: Quantum annealing with manufactured spins

D-wave has many examples of use cases:

Goal: finding the global minimum of a given objective function

Google studied that quantum annealing outperforms simulated annealing

General study: Performance of quantum annealing hardware

Ising formulations of many NP problems

by Andrew Lucas

Example: Steiner trees

\[\begin{aligned}
H_{A} & = A\left( 1 - \sum_{v}x_{v,0} \right)^2 + A \sum_{v \in U} \left( 1 - \sum_{i}x_{v,i} \right)^2 \\
& + A \sum_{v \notin U} \left( y_v - \sum_{i} x_{v,i} \right)^2 \\
& + A\sum_{v}\sum_{i = 1}^{N/2}\left(x_{v,i} - \sum_{(uv) \in E}x_{uv,i} \right)^2 \\
& + A \sum_{uv \in E}\left( y_{uv} - \sum_{i}(x_{uv,i} - x_{vu, i}) \right)^2 \\
& + A\sum_{uv, vu \in E}\sum_{i = 1}^{N/2}x_{uv,i}(2 - x_{u,i-1} - x_{v,i})
\end{aligned} \]

Quantum computing companies with different paradigms and hardware

- IQM (gate)
- IBM (gate, superconductor)
- Google (gate, superconductor)
- IonQ (gate, trapped ion)
- Honeywell (gate, trapped ion)
- Rigetti (gate, integrated)
- Microsoft (gate, topological)
- Xanadu (gate, photonic)
- D-wave (annealing & gate coming)

Cars, especially self-driving cars, require multiple sensors to monitor the car's environment. Positioning the sensors is a combinatorically difficult problem and testing different combinations is slow.

In this challenge BMW wanted to research possibilities of quantum computing in the sensor positioning process.

Valter Uotila & Sardana Ivanova

We utilized Quadratic Unconstrained Binary Optimization model and followed the standard approach in D-wave's examples and in the paper Ising formulations of many NP problems.

- Formalizing problem
- Defining suitable binary variables
- Identifying and creating suitable constraints
- Implementing variables and constraints with Ocean software framework

Solving classical database optimization and modeling problems with quantum computing

- Join order optimization
- Estimating result size of conjunctive queries
- Scheduling and deadlock recovery
- Junction'21 idea: sustainability in data infrastructures
- Database query langugages: pregroup grammars

Problem: quantum computing might not scale and bring any benefits

Problem: for a given subset of vertices, select a subset of vertices and edges so that they all together form a tree and the total weight is minimized.

Will we be able to store and query quantum data from quantum databases?

What does it mean?

How would it work?

Why do we need it?

Category theory & quantum computing:

- Quantum annealing aims to minimize an objective function. It is not a universal quantum computing paradigm.
- There are already many real-life applications of quantum annealing.
- Quantum annealing should be applicable to database problems.
- Ising formulations of many NP problems is a concrete paper of formulating problems using Ising model.

Questions, comments, dicussion?

Created by Hakim El Hattab and contributors