Quantum Speedup for Hypergraph Sparsification
Authors: Chenghua Liu
Minbo Gao
Zhengfeng Ji
Mingsheng Ying
Venue: ICML 2025 poster (2025)
Keywords: Quantum Algorithms
Hypergraph Sparsification
Primary area: theory->everything_else
TL;DR: We propose the first quantum algorithm for sparsifying hypergraphs with near-optimal time complexity.

Abstract: Graph sparsification serves as a foundation for many algorithms, such as approximation algorithms for graph cuts and Laplacian system solvers. As its natural generalization, hypergraph sparsification has recently gained increasing attention, with broad applications in graph machine learning and other areas. In this work, we propose the first quantum algorithm for hypergraph sparsification, addressing an open problem proposed by Apers and de Wolf (FOCS'20). For a weighted hypergraph with $n$ vertices, $m$ hyperedges, and rank $r$, our algorithm outputs a near-linear size $\varepsilon$-spectral sparsifier in time $\widetilde O(r\sqrt{mn}/\varepsilon)$. This algorithm matches the quantum lower bound for constant $r$ and demonstrates quantum speedup when compared with the state-of-the-art $\widetilde O(mr)$-time classical algorithm. As applications, our algorithm implies quantum speedups for computing hypergraph cut sparsifiers, approximating hypergraph mincuts and hypergraph $s$-$t$ mincuts.

Quantum Speedup for Hypergraph Sparsification
Chenghua Liu Minbo Gao
Zhengfeng Ji Mingsheng Ying*
Abstract
number of edges by adjusting edge weights while (approx- imately) preserving the spectral properties of the original graph. Over the past two decades, graph sparsification has experienced several breakthroughs (see Spielman & Srivas- tava (201 1); Batson et al. (2012)), ultimately leading to the discovery of algorithms that finds spectral sparsifiers of lin- ear size in nearly- -ineer time (Lee & Sun, 2018). Graph sparsification algorithms are used for crucial tasks such as Laplacian system solver (Cohen et al., 2014), computing random walk properties (Cohen et al., 2016), and solving maximum flow problem (Chen et al., 2022). Additionally, they have found widespread applications in machine learn- ing domains, including computer vision (Simonovsky & Komodakis, 2017), clustering (Peng et al., 2015; Laenen Sun, 2020; Agarwal al., 2022), and streaming machine learning algorithms (Braverman et al., 2021).
Graph sparsification serves foundation for many algorithms, such as approximation algo- rithms for graph cuts and Laplacian system solvers. As its natural generalization, hypergraph sparsification has recently gained increasing at- tention, with broad applications in graph machine learning and other areas. In this work, we propose the first quantum algorithm for hypergraph spar- sification, addressing an open problem proposed by Apers & de Wolf (2020). For weighted hyper- graph with n vertices, m hyperedges, and rank v, our algorithm outputs a near- linerr size E-spectral sparsifier in time ((rymm/e)) This algorithm matches the quantum lower bound for constant r and demonstrates quantum speedup when com- pared with the state-of-the-an oft (mmr) clas- sical algorithm. As applications, our algorithm implies quantum speedups for computing hyper- graph cut sparsifiers, approximating hypergraph mincuts and hypergraph s-t mincuts.
Hypergraphs, generalization of graphs, naturally emerge in various real- wellworld scenarios where interactions go beyond pairwise relationships, such as group dynamics in biochem- istry, social networks, and trade networks, as they allow a single edge to connect any number of vertices (the max num- ber of vertices an edge contains is called the rank). Thus, natural generalization of the garph sparsification, the task of sparsifying hypergraphs are investigated by many researchers, starting from Soma & Yoshida (2019). Hyper- graph sparsification significantly reduces the computational cost of calculating hypergraph energy, a crucial quantity for many machine learning tasks, including clustering (Zhou et al., 2006; Hein et al., 2013; Takai al., 2020), semi- supervised learning (Hein et al., 2013; Zhang et al., 2020; Yadati et al., 2019; Li et al., 2020), and link prediction (Ya- dati et al., 2020).
1. Introduction
Sparsification serves as a foundational algorithmic paradigm wherein a densely constructed entity is transitioned to a sparse counterpart while preserving its inherent character- istics. Such a process invariably enhances various facets of algorithmic efficiency, from reduced execution time to optimized space complexity, and even more streamlined communication. A typical instance of this paradigm is the graph sparsification, where the objective is to reduce the
With the rapid development of quantum computing, many graph algorithms and machine learning tasks have benefited from quantum speedups. the context of the sparsification paradigm, the groundbreaking work of Apers & de Wolf (2020) introduced the first quantum speedup for graph spar- sification with nearly optimal query complexity, showcasing the potential of quantum computing for sparsification tasks. They further proposed several open questions about the po- tential for quantum speedups in broader sparsification tasks. Among these, a natural and important question is:
Keey Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China 'University of Chinese Academy of Sciences, Beijing, China 'Department of Computer Science and Technology, Tsinghua University. Beijing, China *Centre for Quantum Software and Information, University of Technology Sydney, Sydney, Australia. Correspondence to: Zhengfeng Ji <jizhengteng @ tisinguua.edu.cn.. edu.cn">.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
We use Ö(f) to represent O (f polylog(m, n,,,, 1/2)) throughout this paper to suppress polylogarithmic factors.
there a hypergraph sparsification algorithm

---

Quantum Speedup for Hypergraph Sparsification
that enables quantum speedups?
Kapralov et al. (2021) and Kapralov al. (2022) reduced the sparsifier size nearly linear, achieving (nn/e*) in polynomial time. The current state-of-the-ar algorithm for hypergraph sparsification, proposed by Jambulapati et al. (2023), produces a sparsifier of size O(n/E²) in almost linear time ((mr). Independently and concurrently, Lee (2023) presented a polynomial time algorithm achieving a sparsifier of the same size. For a detailed comparison of these results, see Table 1.
In this paper, we give an affirmative answer to this question. Specifically, we develop a quantum algorithm for construct- ing an e-spectral sparsifier of hear-linear size for a weighted hypergraph with n vertices, m hyperedges, and rank r. Our algorithm achieves near-linear output size-matching the current best classical algorithm-whid operating in sublin- ear time Ó /mrm///=) which improves the time complex- ity Ö(mr) of the best known classical algorithm². For the constant rank this time complexity matches the quantum lower bound of $2( (0(ymm) /mn/s) established by Apers & de Wolf (2020) and contrasts with the classical lower bound of (2(m) (see Remark 4.3). Additionally, for dense hypergraphs, where m E (nn"), our algorithm achieves near- near-quadratic improvement, reducing the time complexity from Ö(rn") classically to ((rn(++1//)) quantumly.
Prior to the emergence of spectral sparsification, early re- search focused on relatively weaker notion called the cut sparsification. In the domain of hypergraphs, extensive re- search has been conducted on hypergraph cut sparsifiers, yielding significant theoretical and practical advances (Ko- gan & Krauthgamer, 2015; Chekuri & Xu, 2018). These sparsifiers have proven particularly valuable in efficiently approximating eut minimization problems in hypergraphs, facilitating applications across multiple domains. Notable applications include VLSI circuit partitioning (Alpert & Kahng, 1995; Karypis et al., 1999), optimization of sparse matrix multiplication (Akbudak et al., 2013; Ballard et al., 2016), data clustering algorithms (Li & Milenkovic, 2017, 77; Liu et al., 2021), and ranking data analysis (Li & Milenkovic, 2017).
Hypergraph Sparsification To extend the graph spar- sification task to hypergraphs, we need to generalize the quadratic form of the graph Laplacian. This generalization leads to the concept of hypergraph energy, first introduced by Chan et al. (2018); Yoshida (2019). For hypergraph H = (V, E, w), the energy of a vector x E RV is defined as a sum over all hyperedges e E E, where each term is the product of the edge weight we and the "quadratic form" (x)... Here, (z) represents the maximum squared dif- ference between any two vector components In and Ty corresponding to vertices u and v in the hyperedge e (see Definition 2.4 for a formal description). The concept of energy captures the spectral properties of the hypergraph, while its inherent nonlinear structure introduces significant computational challenges (Chan et al., 2018).
Main Results In this work, we propose the first quantum algorithm for hypergraph sparsification that produces a spar- sifier of size ( in O(r ((n/////)) time, which breaks the linear barrier of classical algorithms.
Theorem 1.1 (Informal version of Theorem 4.1). There exists a quantum algorithm that, given query access to a hypergraph H (V, E, w) with [V] = n. |E| = m, w Z0 rank r and & > O, outputs with high probability an e-spectral sparsifier of H with ((n/e)) hyperedges, in time Ö(r/mm///
The task of hypergraph sparsification aims to reduce the number of hyperedges while maintaining the energy of the original hypergraph, ultimately producing a hypergraph sparsifier (see Definition 2.5). Hypergraph sparsification not only of great theoretical interest, but also has wide applications in many fields, especially in graph machine learning. Consequently, researchers have been develop- ing increasingly sophisticated and analytically refined algo- rithms for hypergraph sparsification in recent years. Soma & Yoshida (2019) were the first to demonstrate that an E- spectral sparsifier of size Ö(n²* could be constructed in time Ömmr + n²² /²²). Subsequently, Bansal et al. (2019) improved the sparsifier size to n/=") with a construc- tion time of Ö(mr² =²)) Further advancements by
As a corollary, our algorithm could be used construct cut sparsifier for a hypergraph in sublinear time. This enables quantum speedups for approximating hypergraph mincuts and s-t mincuts, achieving sublinear time complexity with respect to the number of hyperedges. For further details, we refer readers to Section 5.
Techiques Our algorithms are inspired by a sampling- based framework appearing in classical hypergraph sparsifi- cation algorithms. The overall idea behind the framework is to compute a proper importance weight for each hyperedge, and sample the hyperedges based on the weights.
To be more precise. our algorithm runs in Ö(r/mn/e + ry mmer) time, of which the second term is usually smaller in most situations. See Remark 4.2 for more detailed discussion. 'Typically, we assume that a 2 / /n/m, as sparsification is only advantageous when the number of hyperedges in the sparsifier at most m.
Specifically, we adopt the method proposed in Jambulap- ati et al. (2023), where the weight on each hyperedge is
'Throughout this paper, we say something holds "with high probability" it holds with probability at least - O (1/n).
2

---

Quantum Speedup for Hypergraph Sparsification
Table I. Summary of results on hypergraph sparsification
Reference
Type
Sparsifier size
Time Complexity
Soma & Yoshida (2019)
Classical
O( log n/=²)
Ö(mrr + n²/ /=2)
Bansal et al. (2019)
Classical
O(r"n log n//²²)
Ö(mr² + n//2
Kapralov et al. (2021)
Classical
ar(logn/E) (1)
O(mr²) + ((1)
Kapralov et al. (2022)
Classical
O(nlog" n/=*)
Ö(mr + (oly(n))
Jambulapati et al. (2023); Lee (2023)
Classical
On nog log
Ö(mr)1
This work
Quantum
Moglognlorr// log
Ö(rymar + rv/m//e)
This ((mr) complexity corresponds to the algorithm proposed in Jambulapati et al. (2023).
set to be the group leverage score overestimate (which we call hyperedge leverage score overestimate in our paper to avoid ambiguity). Classically, computing these overesti- mates would require (mmr) time by an iterativeccontractvve algorithm which mainly follows the algorithm for comput- ing an approximate John ellipse (Cohen et al., 2019). Then, one can sample (nn/s²) hyperedges in Ö(n/e²) time, and reweight them to get hypergraph sparsifier.
tasks through the sparsification paradigm, offering both theoretical advances and practical applications.
The seminal work of Apers & de Wolf (2020) established quantum algorithms for graph sparsification, demonstrating speedups in cut approximation, effective resistance compu- tation, spectral clustering, and Laplacian system solving, while also providing fundamental lower bounds for quan- tum graph sparsification. This work catalyzed several break- through results for graph problems. Apers & Lee (2021) developed quantum algorithm for exact minimum cut com- putation, achieving quantum speedups when the graph's 's weight ratio is bounded. Apers et al. (2024) extended these techniques to solve the exact minimum s-t cut problem. The versatility of quantum graph sparsification was further demonstrated in Cade et al. (2023), where it enabled accel- erated motif clustering computations.
We discover that, with the assistance of series of classi- cal and quantum techniques, the computation of hyperedge leverage score overestimate can be accelerated. To be more precise, we realize that the computation of hyperedge lever- age score overestimate could be executed in a sequence of sparse underlying graphs (see Definition 3.3 for more details), and these sparse underlying graphs can be effi- ciently constructed (in Orr/mmrr time) by the quantum graph sparification algorithm proposed by Apers & de Wolf (2020). Thus, obtain quantum algorithm (Algorithm 1) that allows efficient queries to the hyperedge leverage score overestimate running in sublinear time.
A significant theoretical advancement emerged in Apers & Gribling (2024), which generalized the quantum graph sparsification framework to quantum spectral approxima- tion by combining leverage score sampling with Grover search. This generalization enabled efficient approxima- tion of Hessians and gradients in barrier functions for inte- rior point methods, yielding quantum speedups for linear programming under specific conditions. These spectral ap- proximation techniques have found recent applications in various machine learning problems. Song et al. (2023) and Li et al. (2024) applied the quantum spectral approximation and leverage score sampling algorithms to achieve quantum advantages in linear regression and John ellipsoid approxi- mation, respectively.
The quantum procedure described above, however, intro- duces a new challenge for the sampling step: the exact sampling probabilities cannot be directly accessed. To re- solve this issue, we utilize the technique of "preparing many copies of quantum state" (Hamoudi, 2022) to get ((n/=²) samples in (ry/m//e) time without explicitly computing the normalization constant for the sampling probability. Af- ter sampling hyperedges, we encounter problem in the reweighting stage due to the unknown normalization con- stant. We address this issue partially using the quantum sum estimation procedure (Theorem 2.9), while the imprecision introduced during this procedure necessitates a more rig- orous analysis. We complete the correctness analysis by employing the novel chaining argument proposed in Lee (2023).
2. Preliminaries
2.1. Notation
For clarity, we use [n] to represent the set (1,2,...,,) and [n]o to represent the set {0, 10.1,...,, 1}. Throughout this paper, we use = (V, F, C) to denote a graph, where
.., n
Related Works Quantum algorithms have demonstrated significant potential in graph-theoretic and optimization
3

---

Quantum Speedup for Hypergraph Sparsification
V is the vertex set, F is the edge set, and c : F Rz0 represents the edge weights. For undirected weighted hypergraph, we denote it as H = E, w), where V is the vertex set, E' is the hyperedge set, and w E + Rz0 represents the hyperedge weights. We use n, m to denote the size of V and E respectively. Typically, we denote edges (consisting of two vertices) with f and g. while reserving for hyperedges. Given a hyperedge e, we use (5) denote the corresponding induced edge set (f e: 2).
proportional to their effective resistances. This importance sampling approach is foundational graph sparsification and has also inspired advancements in hypergraph sparsifi- cation. Next, we define the effective resistance.
Definition 2.3 (Effective Resistance), Given graph G = (V, F, c). the effective resistance of pair of i, E V is defined as
Raj = (6, -(
2.2. Laplacian and Graph Sparsification
where L denotes the Poooree inverse of LG. and 6g denotes the vector with all elements equal 0 except for the i-th being 1.
For an undirected weighted graph G (V, F.c,, the weighted degree of vertex i is defined by
For further details, including key properties of effective resistance used in this work, we refer the readers to Ap- pendix A.
deg(i)= = Σ cfp
SEFRES
where the sum is taken over all edges I that contain i, and of represents the weight of edge f.
2.3. Hypergraph Sparsification
Definition 2.1 (Laplacian). The Laplacian of a weighted graph G (V, F, is defined as the matrix LG E RVXV such that
Here, we formally define the fundamental concept in hyper- graph sparsification, namely the energy.
Definition 2.4 (Energy). Let H (V, E, w) be weighted hypergraph. For every vector x E RV, we define its associ- ated energy in H as
deg(i)
j if(i.5) F, otherwise.
(Lo)
Cij
Qu(z): = Σ We (e())(z))
0
(2)
EE
The Laplacian of graph G is given by LG = Da Ag. with Ag the weighted adjacency matrix (Ac)ss Gjj and D the diagonal weighted degree matrix DG diag (deg (i): i E V). LG is positive semidefinite matrix
where (e(z)= = max (x, xz) )
In the special case when the rank of H is 2, (meaning H is actually a graph), the energy reduces to the quadratic form of graph Laplacian (see Equation (1)).
whenever weight function e is nonnegative. The quadratic form of LG can be written
Similar to graph sparsification, the goal of hypergraph spar- sification is produce hypergraph spectral sparsifier with fewer hyperedges. The hypergraph spectral sparsifier of hypergraph H is reweighted subgraph of H that approxi- mately preserves the energy for any vector & E RVV.
x LGG
Σ cij (z, x2)²
(6JEEF
for arbitrary vector x R.V. Graph sparsification produces reweighted graph with fewer edges, known graph (spectral) sparsifier. A graph spectral sparsifier of G is re- weighted subgraph that closely approximates the quadratic form of the Laplacian for any vector r E Y
Definition 2.5 (Hypergraph Spectral Sparsifier). Let H = (V, F, w) be a weighted hypergraph. A re-weighted hy- pergraph H w E R20 and E le E W. 0}. For any E > 0, H is an e-spectral sparsifier of G if for any vector x E R.V. the following holds:
(V, E, w) is subgraph of H, where
Definition 2.2 (Graph Spectral Sparsifier). Let G = (V, F.c) be a weighted graph. A re-weighted graph G F, 2) is subgraph of G, where ē F + R20 and F (ʃ E :T > 0}. For any > 0, G an e-specraal sparsifier of G if for any vector E RY, the following holds:
(((=))Q((())) (H(()).
The hypergraph cut sparsifier is a weaker notion of spar- sification than the spectral sparsifier. Specifically, for a weighted hypergraph H (V, E, w). we restrict x e RV to be the characteristics vector 1s E {0, 13V of a vertex subset S C V. The energy QH (1s), or simply Qn(S), can be expressed as (H()) Eees, We, where ös denotes the
LT - Loa S xx.xTT ILa..
In the groundbreaking work by Spielman & Srivastava (2011), the authors demonstrated that graphs can be effi- ciently sparsified by sampling edges with weights roughly

---

Quantum Speedup for Hypergraph Sparsification
set of hyperedges crossing the eut (S, \ 8). The e-cul
employed in numerous time-efficient quantum algorithms. QRAM enables the storage modification of an arryy Cl..... Cn of classical data while allowing quantum query access via a unitary UORAM {t) [0} + |t) [c)). Although QRAM is a natural quantization of the classical RAM model and is widely utilized, it is important to acknowledge that, given the current advancements of quantum computers, the feasibility of implementing practical QRAM remains some- what speculative.
sparsifier H of the hypergraph H is a subgraph that satisfies the following:
Qu (S) - Qu (S) Se (S), ASSA
(3)
2.4. Quantum Computing and Speedup
In quantum mechanics, a d-dimensional quantum state
(e) (uo....,.d_1)' is unit vector in a complex Hilbert space Cd, namely, Eie |og|² 1. We define the com- putational basis of the space Cd by {1i) Hej4,, where (i) (O..... 0, 1, 0, ........) .) T with the i-th entry (0-indexed) being 1 and others being O. The inner product of quantum states |u). ,1) E Cdd is defined by (ule) Ei uz 2/g where 2" denotes the conjugate of & C. The tensor product of quan- tum states (u) E Cdd. and (u) E Cd is their Kronecker prod- uct, (u) @ (o) (u ug ..... Ud, -1d, T which can be abbreviated as (n) (v).
A quantum (query) algorithm A is a quantum circuit con- sisting of a sequence of unitaries U1...., .r, where each U2 could be a quantum gate, a quantum oracle, or a QRAM operation. The time complexity of A is deter- mined by the number T of quantum gates, oracles and QRAM operations it contains. The algorithm A operates n qubits, starting with the initial state |0] (hn The uni- tary operators U1...., Ur are then applied sequentially to the quantum state, resulting in the final quantum state (v)) = UT U1 10)@m @* Finally, a measurement is per- formed on (b) in the computational basis (t) for i E [2"]o- yielding a classical outcome i with probability Kile))
A quantum bit, or qubit, is a quantum state ( in C2, ex- pressible as (い5 = a (0) + 3 [1), where a, B E C and |a|2 + | = 1. Furthermore, an n-qubit state is in the tensor product space of n Hilbert spaces C2, denoted as (C²) C with the computational basis {1t) (e(())) To extract classical information from n--ubit state (v)) we measure it in the computational basis, yielding outcome i with probability p (i) = [² for i E [2" The op- erations in quantum computing are described by unitary matrices U. satisfying UUT = UUU = J, where Ut is the Hermitian conjugate of U, and is the identity matrix.
In our paper, we incorporate quantum algorithms from pre- vious research as basic components of our algorithm. One such algorithm is quantum graph sparsification, initially pro- posed by Apers de Wolf (2020) using adjacency- input queries, and later revisited through alternative techniques in Apers & Gribling (2024) using edge-vertex incidence queries. The query access described below refers to the latter approach.
We consider the following edge-vertex incidence oracle Og for the graph G (V, F,c) with n vertices and m edges. This oracle consists of two unitaries, O and Out which are defined as follows for any edge f = [
Theorem 2.6 (Quantum Graph Sparsification, Theorem 1 in Apers & de Wolf (2020)). There exists quamium algo- rithm GraphSparsify(OG... that, given query access Og to a weighted graph G = (V, F7,FFc) with [V| = n, F m, c E IRE5 and E 2 vn/mm, outputs with high probability the explicit description of an E-spectral sparsifier of G with Ö(n/²²) edges, using Ö(Vmn/e) queries to OG and in time Ö O(/nn//s).
OG (f) (0) + (f) (1) (5), Og 1f) (0) + ley).
where lff E C",, 11),, 1b) E C", and oj is represented as floating-point number with ley) E Cddas. Taking duce (1) allows for achieving arbitrary desired Doating-point accuracy. Similarly, we assume access to hyperedge oracle Oh for the hypergraph H- (V, E, w). which consists of three unitaries Oure, O and Ow. These unitaries allow for the following queries for any hyperedge e E E:
The next quantum algorithm proposed by Hamoudi (2022) provides an efficient approach to prepare many copies of a quantum state.
Theorem 2.7 (Preparing Many Copies of a Quantum State, Theorem in Hamoudi (2022)). There exists a quantum algorithm that, given oracle access Ow to a vector w E R2 (0-indexed) (O.. : 1V) (0) + (t) (ws)) Vi E [m]), and k E [m], with high probability, outputs l copies of the state (w). where
Ouee: : le) (0) + |e) ||e|)
O : le) |0) @r + le)
X iEe
lii) 10) 0
OH |e) 10)
+ le) (w)).
Iw)
1
Σ
Vui li)
W
sElmio
In many quantum algorithms, information can be stored and retrieved in quantum-read classical-write random ac- cess memory (QRAM) (Giovannetti et al. (2008)), which is
with W Eieto, wi The algorithm uses Ö(
queries to Ow, and runs in Ö (V Ö(Vnk) time.
5

---

Quantum Speedup for Hypergraph Sparsification
By performing measurements on each of the generated quan- tum state copies, sample sequence is produced, where each element i is selected with probability proportional to wi. This leads to the following corollary.
where R. max(Ry : VS E (5)), and R2 represents the effective resistance of the edge f in the underlying graph G.
We remark that, the choice of the underlying graph G will greatly influence the hyperedge leverage scores. For our sparsification purpose, we want to bound the total sum of hyperedge leverage scores by Onn), which determines the the size of the resulting hypergraph sparsifiers. Therefore, we define the following notion of hyperedge leverage score overestimates, which are entry-wise upper bounds for lever- age scores with a specific underlying graph, such that the total sum is bounded by a parameter y = O(n).
Corollary 2.8. There exists a quantum algorithm MultiSample( k) that, given query access Ow to a vec- tor R22o and integer k E [m), outputs with high proba- bility a sample sequence E [n]* such that each element i is sampled with probability proportional to wi The al- gorithm uses ((kkk) queries to Ow, and runs in O(ynk)
time.
Definition 3.2 (Hyperedge Leverage Score Overestimate, adapted from Jambulapati et al. (2023, Definition 1.3)). Given a hypergraph H = (V, E, w), we say 2 E &o is a v-(bounded hyperedge leverage score) overestimate for H if ||||| I v and there exists a corresponding underlying graph G (V, F, c). satisfying the constraints Equation (4), such that for all e E E, Ze 2 Le.
In addition the quantum algorithms mentioned above, we also require quantum sum estimation, which provides quadratic speedup over classical approaches.
Theorem 2.9 (Quantum Sum Estimation, Lemma 3.1 in Li et al. (2019)). There exists a quantum algorithm SumEstimate(( (Qatte(ww= w: that, given query access Ow to a vec- tor w IR5 and & > O, outputs with high probability an estimate for Eie(n) W; satisfying [3 - s| S ss, using Ö( ((/)))) queries to Ow and in ((Vi//)) time.
To obtain an overestimate, we need to handle the weights of the underlying graph, which contains 0(mr²) edges. Nevertheless, it is sufficient to manage only ((mr) edges by replacing each hyperedge with a sparse subgraph (e.g.. star graph with up clique (Definition 3.1). We refer to the resulting graph as sparse underlying graph.
3. Quantum Algorithm for Leverage Score Overestimates
1 edges) rather than a complete
In this section, we will introduce the notion of hyperedge leverage scores, which is generalization of leverage scores of edges in a graph. We then define the concept of leverage score overestimates, which are one-side bounded estimates of hyperedge leverage scores. Finally, we propose quan- tum algorithm that computes the overestimates given query access to hypergraph.
Definition 3.3 (Sparse Underlying Graph). Given an undi- rected weighted hypergraph H = (V,E, w). a sparse un- derlying graph of H is defined as G = (V, e) with edge set F = {(e. f) : f Se,e E E} and weights c E R satisfying
We
Eeer FES.
Ve E.
(6)
To define hyperedge leverage scores, we first introduce the concept of underlying graphs.
For each e E E, we fix an arbitrary vertex ae E e and define
Definition 3.1 (Underlying Graph). Given an undirected weighted hypergraph H = =VV F, w). an underlying graph of H is defined as multigraph G F, with edge set F = {(e, : f (2)e E} and weights R- satisfying
S. = [f E (2) 0, E f].
Now we present our quantum algorithm of hyperedge lever- age score overestimates, which is a key step for our main quantum algorithm for hypergraph sparsification. Our al- gorithm is inspired by the approximating John ellipsoid algorithm proposed in Cohen et al. (2019) and the group leverage score overestimate algorithm in Jambulapati et al. (2023). The input of our algorithm includes a quantum ora- cle to the hypergraph, the number of iterations T, the graph sparsification parameter an, and the effective resistance ap- proximation factor ag. The output of our quantum algorithm is data structure, which could provide query access to the hyperedge leverage score overestimates (see Proposition B.6 for a formal description of the output).
We Σ Ce. FE(
Vee E.
(4)
Note that if the hypergraph contains m hyperedges with rank r. its underlying graph can have up to mr(r - 1)/2 edges. The multiple edges in the underlying graph are la- beled according to the hyperedges they originate from.
With this concept, we define the hyperedge leverage score as follows: Given hypergraph H and one of its corresponding underlying graphs G, the leverage score of a hyperedge e E E, is defined as
Recall that the choice of the underlying graph G determines the hyperedge leverage scores, as well as their overesti- mates. Our algorithm iteratively adjusts the edge weights
La : we Rey
(5)
6

---

Quantum Speedup for Hypergraph Sparsification
of the underlying graph over roughly logr rounds con- struct a suitable G. In each iteration, use quantum graph sparsification to reduce the graph's size and reassign hy- peredge weights to the edges of the underlying graph ac- cording to edge leverage scores. To maintain overall ef- ficiency, this process is implemented entirely quantumly through a series of quantum subroutines. The process begins with Weightlnitialize, which is employed during the first it- eration to establish quantum query access the weights of the underlying graph via queries to the original hyper- graph (Proposition B.1) In each iteration, the system uti- lizes UGraphStore to provide quantum query access to the stored weights of the sparsifier obtained from GraphSparsify (Proposition B.4). Subsequently, EffectiveResistance en- ables efficient quantum queries to the approximate effee- tive resistance of graph (Proposition B.3). For the next iteration, WeightCompute implements quantum query ac- cess to the updated weights of the sparse underlying graph (Proposition B.5). The complete algorithm is presented in Algorithm
4. Quantum Hypergraph Sparsification
Assuming query access to a u-overestimate, we aim to im- plement the sampling scheme in a quantum framework. By leveraging Corollary 2.8, we can sample sequence (o; oi E E) where each element is sampled with probability proportional to Ze- By combining the in- formation of each sampled e with the normalization factor obtained via SumEstimate, we assign appropriate weights to the sampled edges to construct the final sparsifier. The complete algorithm is outlined in Algorithm 2.
Algorithm 2 Quantum Hypergraph Sparsification QHypergraphhpasee(Onn..
Require: Quantum Oracle Oh to a hypergraph H (V, E,w)) with [V| n, |E m, rank r; accuracy
<> 0.
Ensure: An e-spectral sparsifier of H. denoted by H EV,E, w), |E| = O(n log log r/²)).
1: E = 0, ã = 0, M + θ (n log logr/e2).
2: 2 + QHLSO(On, - 0).1....1)..
Algorithm Quantum Hyperedge Leverage Score Overes-
3: + MultiSample(Z.Quu
timates QHLSO(O,, T, a. (2)
4: 8 + ManEstimatte2.Queyy000
Require: Quantum Oracle H to a hypergraph H (V, E, w) with [V| = n, E = m, rank r; the number of episodes T E N: positive real numbers 01, a2 R. Ensure: An instance 2 of QOverestimate which stores the vector being an ooversttvttt for H.
5: for i = 1 to M do
W,, <- measurement outcome of the second register
of Ow lo.) 10).
20. <- measurement outcome of the second register of Z.Query (o,) 10).
1: Let UG(1) = Weightlnitialize((n)))
E Eu { mo; + ww + Wo. s/(M zo.).
2: for = 1 to I" do
end for
3: G(t) = (V, (1)) + GraphSparsiyyUUuttn..)))
4: g(t) + (CraphhStore(:""))
Theorem 4.1 (Quantum Hypergraph Sparsification). There exists a quantum algorithm that, given query access to a hypergraph H = (V, F,, w) with |F] = m. [V] = n, w E R rank т, and E >> O, outputs with high probability the explicit description of an e-spectral spur- sifier of H with O(nlog n logr/E?) hyperedges, in time Ö(r + wrr///////
5: R(O) + EffectiveeResitannce((Ci (1)) (2)).
6: UG(+1) = WeightCompute((11 (1), (()))
7: end for
8: C1 + +2(+1 + d exp (log BlgrrTT rT).
9: Z + QOverestimate((("") : E [T]}, (R(0. :t t
OT}.O,.C. CT,T)
The proof of correctness for the algorithm follows closely the chaining argument in Lee (2023) and Jambulapati et al. (2023). Due to space constraints, we provide the detailed proof in Appendix C.
The algorithm's complexity is described in the following theorem.
Theorem 3.4 (Quantum Hyperedge Leverage Score Overestimates). There exists a quantum algorithm QHLSO(O T, 01, a2)) that, given integer T = Ollog r). positive real numbers 0r1, 022 < 1 and query access Oh to hypergraph H- = (V, E, w) with |E| = m. V n, w E E and rank r, the algorithm runs in time Ö(rr/mnr). Then, with high probability, it provides query access to a u-overestimate z with On), where each query to requires Ö(r) time.
Remark 4.2. We assume 8 2 Vn/m, as sparsification is beneficial only when the sparsifier contains less m hyper- edges. It is also generally the case that m 2 nr, as the objects being sparsified are dense. It's worth noting that the time complexity Ô (rymer + //mm//) simplifies to Ô (r/mmn/e) whenever & 2 vn/m and m 2 nr.
Remark 4.3. For the hypergraph with constant rank the above complexity contrasts with the classical lower bound of 2(m). This lower bound arises from the fact that, in the case of graphs (r = 2), there exists an 2 (m) classical query lower bound for determining whether a graph con-
Due to space constraints, the proof of Theorem 3.4 is de- ferred to Appendix B.
7

---

Quantum Speedup for Hypergraph Sparsification
nected, which establishes the same lower bound for both cut sparsifiers and spectral sparsifiers.
Rg rank r, two verfices 8, 6, E V, and O, outpuls with high probability the (1 + --approximate s-t mincut of H in time O(r + r//mn/e + + 32
5. Applications
6. Conclusion and Future works
As a direct corollary of Theorem 4.1, we can compute a cut sparsifier for a hypergraph sublinear time.
In this paper, we present quantum algorithm for hyper- graph sparsification with time complexity (r//m//E + ryy ry mnr),, where m, n. r, are the number of hyperedges, the number of vertices, rank of hypergraph and precision of sparsifier, respectively.
Corollary 5.1 (Quantum Hypergraph Cut Sparsification). There exists a quantum algorithm that, given query access to a hypergraph H (V, L3, w) with |E| = m = n, w R& rank v, and ε > O, outputs with high prob- ability the explicit description of an E-cut sparsifier of H with On log n log r/e) hyperedges in time Ofry/mmr /mnr +
Our paper naturally raises several open questions for future work. For instance:
r r/mm/s).
Similar to the case for graphs, quantum hypergraph cut sparsification facilitates faster approximation algorithms for cut problems. Below, we highlight two such applications.
Quantum graph sparsification has directly led to the de- velopment of numerous quantum algorithms, including max-cut for graphs (Apers & de Wolf, 2020), graph minimum cut finding (Apers & Lee, 2021), graph min- imum s-t cut finding (Apers et al., 2024), motif clus- tering (Cade et al., 2023). A natural question arises: for more related problems in hypergraphs, such as hypergraph-k-cut, minmax--yypergrahhkk pergraph spectral diffusion (Ameranis et al., 2023), can we design faster quantum algorithms compared to classical ones?
Mincut Given hypergraph H = (V, E,E,,)) w). the hyper- graph mincut problem asks for a vertex set S: 0 ç SSS & V that minimizes the energy Q (S). To the best of our knowl- edge, the fastest algorithm for computing the mincut in hypergraph without error runs in (mmrr time (Klimmek & Wagner, 1996; Mak & Wong, 2000). By applying Corol- lary 5.1, we first sparsify the hypergraph and then apply the mincut algorithm to the cut sparsifier. This gives a quantum algorithm that, with high probability, outputs (1 + E)- approximate mincut in time sublinear in the number of hyperedges.
hy-
We conjecture that the runtime of our quantum al- gorithm is tight up to polylogarithmic factors when e S 1/V7. Can we establish a quantum lower bound of (ory/m/// for hypergraph sparsification? Al- ternatively, can we improve the time complexity for quantum hypergraph sparsification, further enhance the runtime for hypergraph cut sparsification? Fur- thermore, state-of-the therttrrrt hypergraph cut sparsification achieves size of O(n log n/=²) (without the log fac- tor) in Ö + 1 /c") time (Chen et al., 2020)-20000 can we design faster quantum algorithm that matches this size?
+ rn?), which is
Corollary 5.2 (Quantum Hypergraph Mincut Solver). There exits a quantum algorithm that, given query access to a hypergraph H- = (V, E, w) with [E] = m. [V| = n. w E B rank r, and ε > 0, outputs with high probability the (1 + -approxmaitt mincut of H in time Ö(r /mnr + T rymm/s++ + rn?).
s-t mincut Given a hypergraph H = (V, E, w) and two vertices 8, E V. the s-1 mincut problem seeks a vertex set S S V with |S n [s,t]] = 1(i.c., either s E S or t E S) that minimizes the energy (S). The standard approach for computing an s-/ mincut in hypergraph is computing the s-t maximum flow in an associated digraph with O( + m) vertices and ((r) edges (Lawler, 1973). And an s-t maximum flow in such graph can be found in 0mrr/m + n) time (Lee & Sidford, 2014). By com- bining Corollary 5.1 with the aforementioned approach, we can compute a (1 + a)appooxie s-t mincut in time (rr/mn/e) whenever m = M(n²), which is sublinear in number of hyperedges.
Hypergraph sparsification has been extended to various frameworks, including online hypergraph sparsifica- tion (Soma et al., 2024; Khanna et al., 2025), directed hypergraph sparsification (Oko et al., 2023), submodu- lar hypergraph sparsification (Kenneth & Krauthgamer, 2024), generalized linear models sparsification (Jam- bulapati et al., 2024), and quotient sparsification for submodular functions (Quanrud, 2024). A natural ques- tion is can we develop specialized quantum algorithms for these settings?
A Acknowledgements
Corollary 5.3 (Quantum Hypergraph s-t Mincut Solver).
There exits a quantum algorithum that, given query access to a hypergraph H- = (V, F, w) with |F] = m. [V = n, w E
The work was supported by National Key Research and Development Program of China (Grant No.
8

---

Quantum Speedup for Hypergraph Sparsification
2023YFA 1009403), National Natural Science Foun- dation of China (Grant No. 12347104), Beijing Natural Science Foundation (Grant No. Z220002), and Tsinghua University.
Bansal, N., Svensson, O., and Trevisan, L.. New notions and constructions of sparsification for graphs and hypergraphs. In 2019 IEEE 60th Annual Symposium Foundations of Computer Science, pp. 910-928, 2019, doi: 10.1109/ ROCCS2019..00000
Impact Statement
Batson, J., Spielman, A., and Srivastava, N. Twice- ramanujan sparsifiers. STAM Journal on Computing, 41 (6):1704-17))) 1721, 2012. doi: 10.1137/090772873.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Braverman, V., Hassidim, A., Matias, Y., Schain, M., Silwal, S., and Zhou, S. Adversarial robustness of streaming algorithms through importance sampling. In Advances in Neural Information Processing Systems, volume 34, pp. 3544 3144-3557,22 2021.
References
Agarwal, A., Khanna, S., Li, H., and Patil, P. Sublinear algorithms for hierarchical clustering. Advances in Neural Information Processing Systems, 35:3417-3433 2022.
Cade, C.,, Labib, F., and Niesen, I. Quantum Motif Clus- tering. Quantum, 7:1046, 2023. ISSN 2521-327X. doi: 10.2233 20223330-02022-000----000000
Akbudak, K., Kayaaslan, E., and Aykanat, C. Hyper- graph partitioning based models and methods for ploiting cache locality in sparse matrix-vector multipli- cation. SIAM Journal on Scientific Computing, 35(3): C237-C262, 2013. doi: 10. 10.1137/108813956
Chan, T.-H. H., Louis, A., Tang, Z. G., and Zhang, C. Spec- tral properties of hypergraph laplacian and approxima- tion algorithms. Journal of the ACM, 65(3), 2018. doi: 10. 10.1145/3178123
Alpert, C. J. and Kahng, A. B. Recent directions in netlist partitioning: survey. Integration, 19(1):1-1,, 1995. ISSN 0167-9260.
Chekuri, C. and Xu, C. Minimum cuts and sparsification in hypergraphs. SIAM Journal on Computing, 47(6):2118- 2156, 2018. doi: 00.117//1MM1638860
doi: https://doi.or//1.000///
0167-9260195)00088-4,
Chen, I.., Kyng, R., Liu, Y. Peng, R., Gutenberg, M. P., and Sachdeva, S. Maximum flow and minimum-cost flow in almost-linear time. In Proceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, pp. 612-623. IEEE, 2022.
Ameranis, K., Chen, A., DePavia, A., Orecchia, L., and Tani, E. Hypergraph diffusions and resolvents for based hypergraph laplacians. arXiv preprint arXiv: 1042, 2023.
Apers, S. and de Wolf, Quantum speedup for graph sparsification, cut approximation and laplacian solving. In 2020 IEEE sl Annual Symposium Foundations of Computer Science (FOCS), pp. 637-648, 2020. doi: 10. 10000//0CS4470022220000000
Chen, Y., Khanna, S., and Nagda, A. Near-linear size hy- pergraph cut sparsifiers. In 2020 IEEE 61 Annual Sym- posium Foundations of Computer Science, pp. 61-72, 2020. doi: 10.1 N0.199/FFCCS4470022220000
Cohen, M. B., Kyng, R., Miller, G. L.,, Pachocki, J. W., Peng, R., Rao, A. B., and Xu, S. C. Solving SDD linear systems in nearly m log' 1/2 n time. In Proceedings of the forty- sixth annual ACM symposium on Theory of computing. pp. 343-352, 2014.
Apers, and Gribling, S. Quantum speedups for linear programming via interior point methods, 2024. URL https: //aa:////vvv... org/abs/ 2211 03215.
Apers, S. and Lee, Quantum complexity of minimum cut. In Proceedings of the 36th Computational Complexity Conference, 2021. doi: 10.4230/LIPIcs. CCC.:cc2CCC.22.2.2
Cohen, M. B., Kelner, J., Peebles, J., Peng, R., Sidford, A., and Vladu, A. Faster algorithms for computing the stationary distribution, simulating random walks, and more. In Proceedings of the 2016 IEEE 57th annual symposium on foundations of computer science, pp. 583- 592. IEEE, 2016.
Apers. S., Auza, A., and Lee, T. A sublinear query quantum algorithm for s-t minimum cut on dense sim- ple graphs, 2024. URL htttp:://aartttt org/ abs/ 2110.11 15587.
Ballard, G., Druinsky, A., Knight, N., and Schwartz, O. Hypergraph partitioning for sparse matrix-matrix multi- plication. ACM Trans. Parallel Comput., 3(3), December 2016. ISSN 2329-4949. doi: 10. 145/3015144.
Cohen, M. B., Cousins, B., Lee, Y. T., and Yang. X. A near-optimal algorithm for approximating the John el- lipsoid. In Beygelzimer, A. and Hsu. D. (eds.), Pro- ceedings of the Thirty-Sconnl Conference on Learning

---

Quantum Speedup for Hypergraph Sparsification
Theory, volume 99 of Proceedings of Machine Learn- ing Research, pp. 849-873. PMLR, 25-28 Jun 2019. httpstt::1 http///oceeengs..../ mlr, www..mrr.....r..e........eeemme. www.spressss... /v99/ cohen1 hammml......m......
and Svensson, O. (eds.), 51st International Collo- quium Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPlcs), Pp. 97:1- 97:17, Dagstuhl, Germany, 2024. Schloss Dagstuhl für Informatik. ISBN 978-3-95977- 322-5. doi: 1042200IPPss.CAALP2224... attps://dres dawstuth..de/eetiitt.i.......... document 2tt.:/11..222//1I///.. TTT.LIIIII.II..........IE ICALP 2024. 97.
Giovannetti, V., Lloyd, S., and Maccone, L. Quantum ran- dom access memory. Phys. Rev. Lett., 100: 160501, Apr 2008. doi: 10.1103/hyysReeeectt100...
URL
Hamoudi, Y. Preparing many copies of quantum state in the black-box model. Phys. Rev. A. 105:062440, Jun 2022. doi: 10.1 htw.PPyyyyeeA..0...62...
Khanna, S., Li, H., and Putterman, A. Near-optimal linear sketches and fully-dynamic algorithms for hypergraph spectral sparsification. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), 2025. To appear.
Hein, M., Setzer, S., Jost, L., and Rangapuram, S. S. The total variation on hypergraphs - learning on hypergraphs revisited.
Burges, C., Bottou, L.. Welling, M., Ghahramani, Z.., and Weinherger, K. (eds.), Advances in Neural Information Process- ing Systems, volume 26. Curran Associates, Inc., 2013. URL https: htttps://proceediini meurriisss oc
Klimmek, R. and Wagner, F. A simple hypergraph min cut algorithm. Technical Report B, 02, 1996. URL http://edocs wtw.:eees...--beee.ddee...e doca/ seevaatts/GGRLLeeeddeereeeerrrr derivate__00c00002771992...
8a3363abe (al666aae77222222276666636333333 Pape.. pdf.
Kogan, D. and Krauthgamer, R. Sketching cuts in graphs and hypergraphs. In Proceedings of the 2015 Confer- ence on Innovations in Theoretical Computer Science, pp. 367-376, 2015. doi: 211144//688073.26888999
Jambulapati, A., Liu, Y. P., and Sidford, A. Chaining, group leverage score overestimates, and fast spectral hypergraph sparsification. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 196- 206, New York, NY, USA, 2023, doi: 10. 10.1145/3564446.3585111
Laenen, S. and Sun, H. Higher-order spectral clustering of directed graphs. Advances in neural information process- ing systems, 33:941-951, 2020.
Jambulapati, A., Lee, R., Liu, Y. P., and Sidford, A. Spar- sifying generalized linear models. In Proceedings of the 56th Annual ACM Symposium puting, STOC 2024, pp. 1675, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400703836. doi: 10.1 17733668260.36466444
Lawler, E. L. Cutsets and partitions of hypergraphs. Ner- works, 3(3):275-285, 1973. doi: https://doi.or//10.. net.3230030306.
Theory of Com-
Lee, J. R. Spectral hypergraph sparsification via chaining. Proceedings of the 55th Anmual ACM Symposium on Theory of Computing, pp. 207-218, 2023. doi: 10. 10.1
Kapralov, M., Krauthgamer, R., Tardos, J., and Yoshida, Y. Towards tight bounds for spectral sparsification of hyper- graphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pp. 598-611, 2021.
3564246.3585165.
Lee, Y. T. and Sidford, A. Path finding methods for linear programming: Solving linear programs in Ö(Vrank) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 424-433, 2014. doi: 10.1109/ FOCS.2014.52.
doi: 10. 00..14//344632533551111
Kapralov, M., Krauthgamer, R., Tardos, J., and Yoshida, Y. Spectral hypergraph sparsifiers of nearly linear size. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, pp. 1159-1170, 2022. doi: 10.1 10.1109/ FOCS522999202110011
Lee, Y. T. and Sun, H. Constructing linear-sized spec- tral sparsification in almost-linear time. SIAM Journal on Computing, 47(6):2155-2366, 2018. doi: 10.1137/
Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. Mul- tilevel hypergraph partitioning: applications in vlsi do- main. IEEE Transactions on Very Large Scale Integra- tion (VLSI) Systems, 7(1):69-79, 79, 1999. doi: 10.1109/92. 748202.
16M1061850.
Li, P. and Milenkovic, O. Inhomogeneous hypergraph clus- tering with applications. In Proceedings of the 31st Inter- national Conference on Neural Information Processing Systems, NIPS' 17, pp. 2305-2315, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Kenneth, Y. and Krauthgamer, R. Cut Sparsification and Succinet Representation of Submodular Hyper- graphs. In Bringmann, K., Grohe, M., Puppis, G.,
10

---

Quantum Speedup for Hypergraph Sparsification
Li, P.. He, N., and Milenkovic, O. Quadratic decomposable submodular function minimization: Theory and prac- tice. Journal of Machine Learning Research, 21(106):1- 49, 2020. URL http:/tp///// /ttt:///mlrr org/ wttpg/apprs/v/2/ 18-790. htmll.
Soma, T., Tung, K. C., and Yoshida, Y. Online algorithms for spectral hypergraph sparsification. In Vygen, J. and Byrka, J. (eds.), Integer Programming and Combinatorial Optimization, pp. 605-417. Cham, 2024, Springer Nature Switzerland. ISBN 178-3-031-598355
Li, T., Chakrabarti, S., and Wu, X. Sublinear quantum al- gorithms for training linear and kernel-based classifiers. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceed- ings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pp. 3815-3824. PMLR, 09-15 Jun 2019. URL htwps::tpp.........t. http://oceedddde ngs ml wwwps/v977 1i19b.html.
Song, Z.,, Yin, J., and Zhang. R. Revisiting quantum algo- rithms for linear regressions: Quadratic speedups with- out data-dependent parameters, 2023. URL https:
/ //arxiv. org. abs/ 2311 14823.
Spielman, D. A. and Srivastava, N. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6): 1913-1926, 2011. doi: 10. 00.1137080773402,
Takai, Y. Miyauchi, A., Ikeda, M., and Yoshida, Y. Hy- pergraph clustering based on pagerank. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1970-1978, 2020. doi: 10.1 (0.114453334448834403444
Li, X.,
Song, Z., and Yu, J. Quantum speedups for ap- proximating the John ellipsoid, 2024. URL https: //arxiv.org /rrg/ivorg//o... abs/2408 14018.
Liu, M., Veldt, N., Song, H., Li, P., and Gleich, D. Strongly local hypergraph diffusions for clustering and semi-supervised learning. Proceedings of the Web Conference 2021, WWW "21, pp. 2092-2103, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383127. doi: 10. 11555/342231..44499955
Yadati, N., Nimishakavi, M., Yadav, P. Nitin, V., Louis, A., and Talukdar, P. Hypergen: A new method for training graph convolutional networks on hypergraphs. In Advances in Neural Infor- mation Processing Systems, volume 32, 2019. URL cc cc/paper_ffie tefa90caae6399011111666633333333 Paper. Paper. pdf.
Mak, W.-K. and Wong, D. A fast hypergraph min-cut al- gorithm for circuit partitioning. Integration, 30(1):1-11, 2000. ISSN 0167-9260. doi: 10.1016/50167-9260000)) 00008-0.
Yadati, N., Nitin, V., Nimishakavi, M., Yadav, P., Louis, A., and Talukdar, Nhp: Neural hypergraph link prediction. In Proceedings of the 29th ACM International Conference Information & Knowledge Management, CIKM '20, pp. 1705-1714, 2020. doi: 10.1145/3340531.33 137.111180
Oko, K., Sakaue, S., and Tanigawa, S.-i. Nearly Tight Spectral Sparsification of Directed Hypergraphs. In 50th International Colloquium on Automala, Languages, and Programminng volume 261, pp. 94:1-94:19, 2023. doi: 1044230/IPPcs..CALPP.000
Yoshida, Cheeger inequalities for submodular transfor- mations. In Proceedings of the Thirtieth Annual ACM- SIAM Symposium Discrete Algorithums, pp. 2582-2601, 2019.
Peng, R., Sun, H., and Zanetti, L. Partitioning well-clustered graphs: Spectral clustering works! In Conference on learning theory, pp. 1423-1455, PMLR, 2015.
Quanrud, K. Quotient sparsification for submodular func- tions. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 5209-5248, 2024. doi: 10.113771 111133//1.9781111979992..88
Zhang, C., Hu, S., Tang, Z. G., and Chan, T.-.. H. Re- revisiting learning on hypergraphs: Confidence interval, subgradient method, and extension to multiclass. IEEE Transactions Knowledge and Data Engineering, 32 (3):506-518, 2020. doi: 10.1109/TKDE:201 2.8800448.
Simonovsky, M. and Komodakis, N. Dynamic edge- conditioned filters in convolutional neural networks graphs. In Proceedings of the IEEE conference puter vision and pallern recognition, pp. 3693-3702, 2017.
Zhou, D., Huang, J., and Schölkopf, B. Learn- ing with hypergraphs: Clustering, classification, and embedding. In Advances in Neural Infor- mation Processing Systems, volume 19, 2006. URL
cc cc//spppr__illlespppe////////eee neurips.. Aff6:22ac333155405eeee92299 Paper.
Soma, Т. and Yoshida, Y. Spectral sparsification of hyper- graphs. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2570570-2222 2570-2581, 2019. doi: 00..137/1.7786119999
pdf.

---

Quantum Speedup for Hypergraph Sparsification
A. Useful properties of effective resistance
It's the well-known fact in graph theory that the effective resistance defines a metric on the vertices graph. Below, we outline several key properties effective resistance that will be utilized in this work.
Lemma A.1 (Foster). For a weighted graph G (V, c), let Raj represent the effective resistance between vertices and j. Then, holds that E(t))er Cij Rig n..
Proof. For a edge {i,j]. recall that Rig = (d; 8,) L (ō, - -8 then
Σ
Cij
Raj
E
Tr Cij (ó: 6,) (o. -ōz) LT) -Tr (Lrbl Sn-1
(U))
since rank of LG is at most n 1.
Lemma A.2 (Convexity, Lemma 3.4 in Cohen et al. (2019)). For weighted graph G FV,F,c). the function log Ry(c) is convex with respect to c.
B. Proof of Theorem 3.4
For hyperedge e, let Se represent the {f (:) : f}. where fixed vertex in e.
Proposition B.1 (Weight Initialization for Overestimates). Suppose H (V, E, w) is hypergraph with vertex set of size n, edge set E of size m, weight function : E 12z0 and On is a quantum oracle H. Then, there exists quantum algorithm Weightlnitialize((0) ) that satisfies
Weightlnittiliiz((#))\) (f) lf) (6())
(1) with Ce. we/((e)- Ve E and = (i,j} Se, and performs no action if ʃ (i,5) $ Se, using ((1) queries On, in (1) time. Here, we represent (f) as (i) (j) for f {i,5}.
Proof. Consider the following procedure: for any e E and Se, we have
le) lff) (0) (0) 10)
|c) [f) (we) ) ||l|) 10)
Unet
(e) [f) (w.) ||e| 1) 10)
Unv
le) (w:)) |||| - 1) ()
Ut
(e) [5) /w.) ||e|) (c0)))
0
.on
(e) (f) (0) (0) (c())
where Urud satisfies Urwal li) - 1). Uni satisfies Uni (x) (5) 00) = (1) (5) (i/j)) This procedure uses 4 queries to O and Õ1)) additional arithmetic operations. Therefore, let Weightinitialize((O))) =O O Uan Out we know satisfies the requirement stated the proposition.
Recall the following classical algorithm for efficiently computing the effective resistances of graph proposed by Spielman Srivastava (2011). 1).
Theorem B.2 (Effective Resistance Oracle, Theorem 2 in Spielman & Srivastava (2011)). There exists a (classical)
algorithm ClassiallffectiivReesssanccll (Ge, such that for any E > 0 and graph G (V, F, c) with vertex set V of size n, edge set F of size m, and weights B with high probability, returns a matrix Zg of size p x n with p [24 n/=21 satisfying
(1 R) Zo - 5b)1 < (1 e)
for every pair of a, E V, where Ras the effective resistance between and b, in Ō(m/c²) time.
12

---

Quantum Speedup for Hypergraph Sparsification
We require a quantum variant of this effective resistance computation, outlined below.
Proposition B.3 (Quantum Effective Resistance Oracle, Apers & de Wolf (2020, Claim 7.9)). Let G (V,F,O c) be graph with veriex set V of size n, an edge set F of size and weights :E 20 For > O, there is quantum data structure EffectiveResistance, that supports the following operations:
Initialization: EffectiveReeistanne([:, E), ouiputs an instance R. in ((m/62) time.
Query: R. Query, outputs a unitary satisfying
R. Query (a) (b) 10) = la) (0) (Rab)
with (1 - E1 S Rab= S (1 Rab for every pair of vertices a, V, and Rub being the effective resistance between verlices a and b, O(1/E2) time.
Proof. First, we use the algorithm CassicalEfectiveeessttnnnCC to obtain the matrix Zg and store each entries of matrix in QRAM. This allows to access the matrix through unitary Uzo such that
Uz (1) 15) (0) = (0) (b) (Za(i,)))
where Za (i is the entry in the i-th row and j-th column of the matrix Za, i E [m],j E [g] with q- = [2g n/e?1. The time of computing and storing Za is O(m/s²), and each query of Uza has time complexity of O(1). Consider the following procedure:
Uz
(4) (5) 10) 10) 10)
1))
X
Zo (1, (1,
X R=1
Zali. R))) oo(;
1=1
denote
(1) 15) 2 ( 10)
Umina
(1) (2)) Zig Z'a)
Square
(1) 15) (Z))))))
U2a
(1) 15) (0) 10) Rly)
where Zg is the i-th row of the matrix ZG, and U22 can be implemented using Ogg) queries of Uza: Uninu satisfies Uminus {i) 1b) (0) 1b) bb) ji j). U quare satisfies Usquare 1t) 10) |1) (12). This procedure uses Ö(1/s²) queries to Uze and Õ(1) additional arithmetic operations. Therefore, let RuQuery = U Usquree Uminus U U we confirm that this satisfies the requirements outlined the proposition.
The following proposition formalizes the procedure of storing graph in QRAM, which is made straightforward by the capabilities of QRAM.
Proposition B.4 (Quantum Underlying Graph Storage). Let H (V, E,w) is hypergraph with vertex set V of size
edge set E of size m, weights I Suppose G = (V, F,c) is a spurse underlying graph G of H. There is quantum data structure UGraphStore, that supports the following operations:
Initialization:: UGraphStore(G), outputs an instance G, in Ö(mr) time.
Query: G. Queur,, outputs a unitary satisffying
G.Query (e) (f) 10) = (e) If) Ice.))
for every edge (e, f) F, where = [i,j} E So, and performs no action if (e, & F, in Õ(1) time. Here, we represent If) as (6) l5) for f {i,j}.
Proof. For the graph G with edge set F of size at most m(r 1), the initialization step is store all the weights ce, for the edges with indices (c, f) E F into an array using a QRAM of size Ö(mr) and Ö(mr) QRAM classical write operations.
For the query operation, the G. Q.Query is the QRAM quantum query operation the above array.
13

---

Quantum Speedup for Hypergraph Sparsification
The following proposition concerns weight updates in the quantum overestimation algorithm.
Proposition B.5 (Weight Computation for Overestimates). Let H = EV, w) be a hypergraph with vertex set V of size n, edge set of size m, weights E 22 Suppose Oh is quantum oracle to H, 9 and R. represent the instances of UGraphStore and EffectiveReesitance.. for the sparse underlying graph (V, F)c,, respectively. Then, there exists quanlum algorithm WeightCoopute (n ,,, R)), such that
Weighttompuute(uu... lc) 10) = =10
where
Ees Eges, Ce.g Rg
Wes
and Ry is the query result of R. vertices of f. The algorithm requires O(1) queries to Oh, O(r) queries both R and g, and runs in Ö(r) time.
Proof. Consider the following procedure: for any e E E and f E Se, we have
|e) lif 10)
Oh
(e) If') (0) (Oie (8)) [0) ws2) 10)
Unn, le) (f) (0) (oyes, (g) (0)) u.e) 10)
Q.Query, |e) I (c..f) 10) (ggEs. (g) (ca.g) (0)) (mse) (0)
R.Query,
le) (f) (ce.f) (Rt) 10) (8ges, (n) (Ce.g) [Rg) (0)) (wr)) 10)
Umm,
(e) lf) ke,r) Rg)) [ R,y) (8yes, 1g) (ce.g) (Ry) |ce,g Rg)) (we) 10)
0j G. Q.eurrrrr_rur. RR. Query'
(e) lf) W. 1 R (8gEs, R.).) 10) Unn (e) (f) [e,Ce, R2) (8yEs, Ice,g Rgy) Aae) 10)
Unn |e) (f) [WeCe, Rg) (8yEs. Ice Rg)) Ae) de.))
where Ag represents the sum Eges, Rg. Una satisfies Una (Oree (()) 10) @ges, (g) 10), and Umuts Usum; Univ denote basic arithmetic iivrrttionsmmutippiiicae addition, and division, respectively, previously. It's clear that this procedure meets the requirements stated in the proposition, since [Sel O(r) for Ve E.
Proposition B.6 (Preparation for Overestimates). Let N, CEERR R, and H (V,E.w) be hypergraph with rank r. Assume Of quanium oracle H. Suppose (g E [T]} represents a sequence of instances of UGraphStore for the sparse underlying graphs G(f) = (V, F(t), ((t)) of H, and (R()) eE [T]} represents sequence of instances of EffectiveResistance, for the corresponding underlying graphs (! and e. Then, there is quantum data structure QOverestimate, that supports the following operations:
Initialization: QOverestimate( (( t [T]}, (R() it E [T]}, Oh, C,T), outputs an instance Z in Ö(EtE(T T() time, where Ti denotes the needed time of both UGraphStore(G(0) and Effectiveeeesstanne(((
Query: 2. B.Query, outputs a unitary such that, for every e E E
2. Z.Query (e) 10) = (e) (ze)
with
2e = C 1 Σ
Σ
(0) e.
T
LE
gES.
where e. = 22) and Rg (t) is the query result of (1) on vertices of This query is executed in Ö(r Σ 4)) time, where 4 represents the time required for querying both UGraphStore and EffectiveResistance, for G(O)
14

---

Quantum Speedup for Hypergraph Sparsification
Proof. The case of initialization operation is straightforward. Aside from initializing for UGraphStore and EffectiveResistance, store C, 7 in QRAM in O(1) time, allowing access through unitary Ucr = (0) (0) (0) (C/T). For the query operation, we consider the following procedure:
le) (0) On,Uer le) (0 (GSES S. (g) (0))) (0)
g Query,R(1)) Query, (e) (oL OgES. (o)
10)
Unuti
le)
(8/m)
8gES. (o)
)) (0)
Uam, (e)
T 11=1
CgES. (g)
Σ4.000
(e)
SgES, (g) (c( R (4
Σ A (ze)
where A represents the sum Eges. Co.g and Uetique Umult: sum denote basic arithmetic operations of clique genera- tion, multiplication, and addition, respectively, as previously. The procedure can be executed in O(r Eie(n] (2) time, since [Sa] = (r) for Ve E E.
(8) p(t)
Proposition B.7. Let Z be the output of QHLSO(O 01, 02)) (Algorithu 1). Then, the vector z stored in Z is T, u-overestimate for H, where v (1 + Cin and C₁ determined by an, 02, F, T, defined in line 8 of Algorithm
Proof. In the algorithm, ((t) is as-spectral sparsifier of G Let R and R be the effective resistances of ((tt) and (L)) respectively. Since effective resistances correspond to quadratic forms in the pseudo-inverse of the Laplacian, we have T - S R S R R Vf F. According Proposition B.3, we know that (1 - a2) R - R( <
(1 (1+ag) 02) R f vf e F. Combining two inequalities we obtain
+ 02 R() VEEF. 02 R(()) S R(()) S an
1 a1
Let 03 max (00)
1-02
1+02
1}
00+02
(1)) then R is ay-approximate of R/O for Vf F. We define
1ta1
1-a1
off = 20 7(0
We will show that z is a v-overestimate with corresponding underlying graph G = FV,F,e), where ē = + E 200 Specifically, we need to verify the following two conditions:
1. || S v,
2. de 2 Re for all E where Re maxx{R Ry: if E (,)
We show the first condition first. As
7(t) e,
= (()) (((t)
R. < < + a2 (2(() 10
we have
|| - > M
Σ
70
Ci
T Σ
ΣΣ
700 c.g
Sc
eg
EEE
LE[T]
gES.
tE[T]
BEE
SES.
where the final inequality is derived from Lemma A.1.
We now prove that the second condition also holds. For any E E we fix e. Since effective resistance is metric on vertices, for any u, v E e, it follows that
Ruv S Rua + Rav-
Consequently, at least one of the two terms on the RHS must be at least Rav/2 2.. By taking the maximum on both sides, we obtain
max Rug S 2 max Rux M,vEe
wEe
15

---

Quantum Speedup for Hypergraph Sparsification
Thus, for any e E E, we have
log (we (2)) & log (we- 2 max (2)) f S.))
demote
log(us We (Rg((c))
log R5. (c11)
T tE|2
T
Σ
log
205e (1+ + a1)) R2y.))
= - 1E[2]
Σ log (2 0z)) we 200 22..-16.)
LE[2]
(l++)) c,f-
7(t)
))
(6)
Σ
log
Dges
fill
+ log + a3))
T
[1) Cr.s
[E|T]
11++1) c
1 Σ
= T TE(T]
log
+ log
Σ
7(t)
+ log(2(1++ +
((t)
c.
C
9E
(T+1)
(0)
log
Ce,f*
+ log
1
Σ
70 cig
+ +oog(2(1 + a3)))
T
Ce.
LE(T)) gES.
(d) 1 log + log
T Σ
+ 1og(2(1 + aa)))
T
c,g
1E[T) gES.
( log (ze)
where inequality (a) holds since log (R)(c)) is convex with respect to (see Lemma A.2), equality (b) follows from definition of WeightCompute (Equation (7)), inequality (c) follows from the concavity of log, and inequality (d) arises from the fact that
(T+1)
We
ST. we/ we/(lel- -1
the last equality (c) follows directly from the definition of ze in Proposition B.6, with the parameter C' selected as in line 8 of Algorithm
Proof of Theorem 3.4. By taking 01 = 02 = 0.1 as constants and T logr, 2 becomes 4n-overestimate according to Proposition B.7. remains analyze the time complexity of the algorithm.
First, we note that the Weightlnitializee(On)) procedure runs in Ō(1) time, established in Proposition B.1. In each round t [T], GraphSparsifyUCaqq).. a1) is executed Ö(r/mmr) time, following Theorem 2.6, where Ö(r) accounts for the query cost of UG(O)- The resulting graph ((t) is cy-spectral sparsifier of G(t), and crucial fact is that (+)) is sparse and the number of edges in ((4) is Ö(n). Hence, we can initialize the data structures UGraphStore (G())) and EffectiveReesitaanee(("" (z))) in Ö(n) time, as per Proposition B.3 and Proposition B.4. The procedure WeightCompute( Oh, R(1,, g()) provides Uc(++1), with each query taking Ö(r) time according to Proposi- tion B.5. In the final step of the algorithm, 2 can be initialized in Ö(n) time and each Z.Quer, can be executed in Ö(r) time, following Proposition B.6 with T, (()) and 4. = Ō(1)
To summarize, the total preprocessing time is Ö(rymnr)), and the per-query time is Ö(r)
C. Proof of Theorem 4.1
The proof of correctness for the algorithm follows closely the chaining proofs in Lee (2023) and Jambulapati et al. (2023). In particular, we rely on the following crucial technical bound from Lee (2023), which is derived using Talagrand's generic chaining method.
16

---

Quantum Speedup for Hypergraph Sparsification
Lemma C.1 (Corollary 2.13 in Lee (2023)). Let A: l IR be a linear map, with d1,...., , representing the rows of A.
The functions .1,..., Um R - IR are in the form of (x(x) = maxjes, wi Kaj, 1 some Ss [s] and w E [0, 1]
Let D = max [ Then, for any T C BB == { E R ||=/|| - 13, the following inequality holds:
1/2
m
m Σ
E sup
(,) S Co -1A112 Vlog(s + n) log D sup EET
23 (x)))²
zET
for some universal constant Co. The variables fI...., are i.idd Bernoulli random variables taking values +1, and ||A Al12-00 is defined by ||Al|2->>a == max AaxlllAxxllo x E B3)
To provide clarity on how this lemma applies, we explain its connection to hypergraphs. Let H = (V, E, w) be a hypergraph with E m, |V| = n, and weights E R The rank of the hypergraph is max E |e]. In the lemma, n and m correspond to the number of vertices and hyperedges, respectively. The functions o; capture the maximization over all edges in the clique generated by replacing each hyperedge, corresponding to the energy of the hyperedges. The number refers to the number of edges in the complete graph Kn. i.e., s = n(n - 1)/2. The parameter D represents the maximum number of edges in the clique generated by replacing each hyperedge, i.e., D = r(r - 1)/2.
Before proving the Theorem 4. we present the following fact. Proposition C.2. Let H (V, E, w) be hypergraph with vertices, and let G FV, represent its underlying graph. +/2x) x) 2 || holds.
For any x E RK such that x L 1, the inequality QH (LG
Proof. For any E R,, we have
QH (v) = Σ
We max (n+ - u2)² (iJSSe
EEE
Σ
max (t: - uz)²
(w))
EEE Hirke
Σ
ci (v. -0-))) 0j)²
E (i,)ie
LGU.
Taking u = / x achieves we desired.
Proof of Theorem 4.1. Utilizing Algorithm 1 obtain query access to v-overestimate with 2(1 +a2) ag) n O (n) in Ö(rymnr) time. Each query can be executed in Örr) time. Combining with quantum sampling algorithm (Corollary 2.8), we can sample a subset E S E of size M = Ö(n/=2) in Ö(VMm r) = Ō(r/mm/ss) time. The quantum sum estimation (Theorem 2.9) is executed in ((r/m)) time, obtaining ş as 0.1 -apppooximaiionn of s = ||=/|1- We then move on to demonstrate the correctness of the algorithm, showing that the output H is indeed E-spectral sparsifier of H.
For hyperegde e E F, we introduce the following notations
Pe = 2e/3,
ag = L t/2 (ò. 8,), Viij} e [n],
d sw, aaij
((.j) Se,
de (x) = max ((<aE;
E
0 (x) = max :V.,)
where R, := max(R, f E (.). Suppose we sample a hyperedge sequence on (ef ..... e (( such that each element e sampled with probability proportional μe (also proportional zQ). For the new obtained hypergraph H,s the weight of sampled hyperedge is
# {t [M] e = =e]
We
w
Ve E.
M
He
17

---

Quantum Speedup for Hypergraph Sparsification
Recall the definition that (x) max Fz)², the energy of sampled hypergraph H is given by
M w (
QH = M Hop
Q to
(z).
We want choose sample time M sufficiently large such that
E [1QH (x) QH (x) S QH (z), Vz e R..
(8)
H
Equivalently, it suffices to show that
E max
Qu (v) - QH, (v) sc.
H. [1
It is worth noting that for Vx
E R,"
We
Qe (T,122)
We
3 max (ittEe
(1,t/2x,0, 6, - -,,)
max (r,aGy)== = 02 (x))
He
Ze
(6,)ee
Then we have
QH
[ (1+//2²)
1
Σ 33 (x)
(9)
M
JE[M]
where Φy (x)) corresponds to the j-th sampled hyperedge using μ.. Let H be an independent copy of H,,. and &,, t E [M] be the i.i.d. Bernoulli 11 random variables. Note that EH, [QH, (x)] $ 2u (a) and 8/8 E [0.9, 1.1). By convexity of the absolute value function, for any x E ==
= f E : QH (2+ < 1 }. we have
E max H₁, SET QH (1.12gg) Q11 (r.t120)
concavity
(L+/2x) - -QH, (Lt/?x))
E E max Hy Hp DET
<
=
8
E E max H Hy ZET
Qi,, (1+ Q1, (L+/2x)) |
+ ( -1
1)
E max Hp TET
QuI (I+/2x)
Equation (9)
8 H H. DET
E max
M
1
(x)
0² 10y (x)
+
s
- 1)
E max H ZET
M
1
Σ
2
(
(x)
(E[M]
SEiM]
E E max 3 EHH Hp .ET
Σ &
(0
(x)
2 ray (x)
+
(
8
1)
E max H .ET
Σ
E
(x)
M BE[ND]
M
BE[ad]
28 E E max { H. RET
Σ (E[M)
ENO (o) (x)
+
=
88
E max E H₁ .ET'
1
Σ
Eers? e/0)
(x)
M
5
M
(E(M]
38
E E max E H EET
Eo oft
(z)
M
LE[M)]
Note that for any function f, the inequality max.er [f(x) S maxxmax f(x), 0} + max 0} holds. Now, let f(z) = M EtEM Erd? (z). The second term 0 in max(- 0}, can be attained by the first term, since
e,. +1 Qu(v) = 0. combined with the identity Equation (9). Consequently, we have
E max H 2ET
QH
(L (L+/2x) - -QH, (L+/2))
38
1)
E E max f(z) + EE max - ((x) E fr EET
(10)
& EH TET
2
38
E E max
1
Σ
Eop u (x).
E H. FE
M
KE[M]
18

---

Quantum Speedup for Hypergraph Sparsification
The last equality holds because Ee: & [7] are i.i.d. Bernoulli +11 random variables. Consider the random process V2 M Eje(a E50 (z), where Φ (x) corresponds to the j-th sampled hyperedge using J.,
E T. By applying Lemma C.I with the linear map A R" + 1n("=1))) 1)/2 defined as
max (Ax)1z (E
|لريا| (or,aa////a II)
and using Proposition C.2 to ensure that T [ B3, as required by Lemma C.I, we obtain:
1/2
E sup V S Co. || Vlog (n(n 1)/2 + n) log (r(r 1)/2) xET
Σ
(x)
max zET
VM
M
JE[M
(1I)
1/2
I 20% ||A||2-000 v Vlo logr
1 M
Σ
कf (x)
max #ET
VM
JE(M]
where
|| = max : x E BB] = max max cEE (ij]Ce
layll
SWe
Rij V3
Rag
max max eEE (i.j)Ce
max max e (we)
Ze.
Ze
Observe that the component in RHS of Equation (11) can be written as
max ZET M
Σ
(x) = max (.QA(e)s M JELM
1 Σ of (1+P))
max (.Qa(v)
Qh, (v).
JE(M/]
The first equality holds because (1)(x) = Q (x') whenever x - x' E ker(La). Then we have
T:= E max Hy (:Qu(()s
1Q (v) QH, (v)
E max Hμ, SET
QH (L+12x)
QH, (L+/2z))
Equation (10)
6s
max H2 ZET M
Σ
E
(x)
8
Ox
tE(M
Equation (11)
38
-1 1)
Co v V/llo logr/M
E. max
QH, (v)
1/2
8
H (.(u())))
1/2
comcavity
38
1)
Co v 3 V5llgnnoog///
E max v:Qu(v)S
QH, (0)
H
38
<
1
Co v Vlog logr r/M (1 + 7)
5
38
<
Co v 8log n logr/M
(1
1 27
< 10C
Vollg n Blognloor//h logr/M
Therefore, we have т < 20Co /oov/slogg n logr rggrM whenever M
2
100C,'s log n logr.
Choosing M =
400053log n logr/e² = (n log n log r ee2) yields
E max H. [1
Qu (v) - QH, (v) = =TSE
19


Reviews:
[{"review_id": "pjZRzOS4AP", "reviewer": "Reviewer_Kw2T", "summary": "Hypergraph sparsification is the process of reducing the number of hyper edges of a graph while preserving (as much as possible) the energy of the graph. \n\nThe paper introduces an algorithm for hypergraph sparsification, addressing an open problem proposed in a previous paper by Apers and de Wolf. More specifically, the authros show that  give an hypergraph with n vertices, m hyper edges and rank r, and error parameter e, e-eparsifier with Õ(n/e^2) edges, in time Õ(r*sqrt(mn)/e). \n\nWhen rank r is constant, the proposed algorithm matches the quantum lower bound. Additionally, it provides a quantum speedup with respect to state of the art classical algorithms, which run in time Õ(mr). \n\nTo obtain the results, the authors obtain a faster quantum algorithm to compute the hyperedge leverage score overestimate, providing a quantum speedup over a classical algorithm proposed by Lee and Jambulapati (2023). They also use of a technique introduced by Hamoudi to make copies of a quantum state specified by an oracle.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments and suggestions. We will carefully\nrevise our paper to correct all typos, especially we will change the\nword \"adopts\" in the last paragraph of page 2 to \"adopt\".", "claims_and_evidence": "Yes, the proofs of the claims are provided in the appendix, although I did not check carefully all proofs.", "methods_and_evaluation_criteria": "This is a purely theoretical paper.", "theoretical_claims": "I read carefully the first part of the paper, and skimmed through the appendix. I did not check carefully the correctness of the proofs in the appendix.", "experimental_designs_or_analyses": "Not applicable. The paper is purely theoretical.", "relation_to_broader_scientific_literature": "The paper refers to relevant literature in an appropriate way. Most of the main cited papers are recent, and are actually used as a basis for the development of quantum the new quantum algorithms. Notably, the paper from Apers and De Wolf, where the hypergraph sparsification problem is mentioned, the paper by Lee and Jambulapati which is used as a basis for the new quantum algorithm for hyperedge leverage score overestimate, and the paper by Hamoudi, which describes a technique to prepare multiple copies of a quantum state specified by an oracle.", "essential_references_not_discussed": "Not that I’m aware of.", "other_strengths_and_weaknesses": "The main strength of the paper is that it addresses an open problem proposed in a previous paper (Apers and de Wolf). Another interesting aspect is that the proposed solution comes by adapting and extending results obtained quite recently in neighboring areas (eg, the papers by Lee and Jambulapati , and the poper by Hamoudi 2022).", "other_comments_or_suggestions": "I caught some very minor grammar typos when reading the paper. So I would recommend the authors to make a revision in this aspect. (Eg: “we adopts” in the last paragraph of page 2.)", "questions_for_authors": "No question", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q8hbzoVC8R", "reviewer": "Reviewer_EHoy", "summary": "This work introduces the first quantum algorithm for hypergraph sparsification, producing an $\\varepsilon$-spectral sparsifier of size $\\widetilde{O}(n / \\varepsilon^2)$ in time $\\widetilde{O}(r \\sqrt{m n} / \\varepsilon)$ for a weighted hypergraph with $n$ vertices, $m$ hyperedges, and rank $r$. This result demonstrates a quantum speedup over the classical state-of-the-art $\\widetilde{O}(m r)$-time algorithm (Jambulapati et al., 2023; Lee, 2023) and matches the quantum lower bound of $\\widetilde{\\Omega}(\\sqrt{m n} / \\varepsilon)$ for $r = 2$ (Apers & de Wolf, 2020). The method combines a classical sampling-based framework with quantum techniques, including quantum graph sparsification (Apers & de Wolf, 2020), state preparation (Hamoudi, 2022), and sum estimation. Applications include sublinear-time quantum algorithms for computing hypergraph cut sparsifiers and approximating hypergraph mincuts and $s$-$t$ mincuts.\n\nThe three primary contributions align with Sections 3, 4, and 5, summarized as follows.\n\n**Quantum Algorithm for Leverage Score Overestimate (Section 3)**\n\nThe authors introduce a quantum algorithm (Algorithm 1) to estimate hyperedge leverage score overestimates, based on classical approaches from Cohen et al. (2019) and Jambulapati et al. (2023). They adapt the previous concept of group leverage score overestimate and give a slightly different algorithm. The algorithm iteratively updates the weights $c^{(t)}$ of the underlying graph (line 2 of Algorithm 1), sparsifying the underlying graph (GraphSparsify), and then letting $c^{(t+1)}$ take the weight of the hyperedge with the proportion of its energy (WeightCompute). Then, it outputs the average of energies $\\ell^{(t)}$ with appropriate scaling (QOverestimate). Of course, this algorithm is in a quantum way, and specially, the authors describe their subroutines and output as quantum data structures with initialization and query capabilities. The overestimate property (Proposition B.7) is proven using a telescoping argument akin to Cohen et al. (2019). The time complexity of this algorithm hinges on the graph sparsification step, and the quantum speedup here is mainly achieved through the result of Apers & de Wolf (2020).\n\n**Quantum Hypergraph Sparsification (Section 4)**\n\nAlgorithm 2 presents a quantum sampling approach for hypergraph sparsification. It leverages the MultiSample subroutine to access the leverage score overestimate vector and samples a sequence of hyperedges with probabilities proportional to their overestimates. By combining the information of each sampled hyperedge with the normalization factor obtained via SumEstimate, the algorithm then reweights the hypergraph. Correctness is established via a chaining argument, adapted from Lee (2023) and Jambulapati et al. (2023). The time complexity is dominated by the sampling phase, which benefits from the precomputed overestimate data structure from Algorithm 1 and the quantum sampling subroutine from Corollary 2.8.\n\n**Applications (Section 5)**\n\nAs a direct application, a cut sparsifier for hypergraphs is obtained. Since the hypergraph cut sparsifier preserves the cut energy, the quantum speedup for hypergraph sparsification extends to mincut and $s$-$t$ mincut problems.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer’s thorough evaluation and constructive feedback. Below, we address the key concerns raised:\n\n1. Unitary Operations:\n\nThe unitary operators $U_{\\mathsf{mult}},U_{\\mathsf{sum}},U_{\\mathsf{div}},U_{\\mathsf{square}},U_{\\mathsf{minus}}$  are\nquantum gate implementation of the basic\narithmetic operations. Specifically,\nthey satisfy:\n$U_{\\mathsf{mult}}\\ket{a}\\ket{b}\\ket{0} = \\ket{a}\\ket{b}\\ket{ab}$,\n$U_{\\mathsf{sum}}\\ket{a}\\ket{b}\\ket{0} = \\ket{a}\\ket{b}\\ket{a+b}$,\n$U_{\\mathsf{div}}\\ket{a}\\ket{b}\\ket{0} = \\ket{a}\\ket{b}\\ket{a/b}$,\n$U_{\\mathsf{square}}\\ket{a}\\ket{0} = \\ket{a}\\ket{a^2}$,\n$U_{\\mathsf{minus}}\\ket{a}\\ket{b}\\ket{0} = \\ket{a}\\ket{b}\\ket{a-b}$.\nAnd $U_{\\textup{star}}$ satisfies $U_{\\textup{star}}(\\otimes_{i \\in e}\\ket{i})\\ket{0}=\\otimes_{g \\in S_e}\\ket{g}\\ket{0}$, as defined in line 746.\nThese unitary transformations offer quantum counterparts to classical operations while preserving computational efficiency.\n\n2. Initialization of EffectiveResistance (Proposition B.3):\n\nWe sincerely appreciate your careful reading and would like to clarify the technical details here.  In Claim 7.9 of the AW paper, the stated runtime $\\widetilde{O}\\left(\\sqrt{m n} / \\varepsilon+n / \\varepsilon^4\\right)$ comprises two components:\n(a). The first term $\\widetilde{O}(\\sqrt{m n} / \\varepsilon)$: This corresponds to the time for quantum sparsification, which produces a sparse graph with $m^{\\prime}=\\widetilde{O}\\left(n / \\varepsilon^2\\right)$ hyperedges.\n(b). The second term $\\widetilde{O}\\left(n / \\varepsilon^4\\right)$: This arises from applying the classical algorithm (Theorem B.2 and Theorem B.3 in our paper) to compute effective resistances on the sparsifier. Specifically, this step incurs a cost of $\\widetilde{O}\\left(m^{\\prime} / \\varepsilon^2\\right)=$ $\\widetilde{O}\\left(n / \\varepsilon^4\\right)$.\nOur processing is consistent with that in the AW paper, but for the sake of algorithm clarity, we carefully write out the implementation of each step.\n\n3. Appendix C:\n\nWe acknowledge the need for greater clarity and will revise the text to explicitly outline the equivalence between the original claim (line 940)\n$$\nE_{H_\\mu}\\left[\\left|Q_H(x)-Q_{H_\\mu}(x)\\right|\\right] \\leq \\varepsilon \\cdot Q_H(x), \\quad \\forall x \\in {R}^n,\n$$\nand the proved result (line  1043)\n$$\nE_{H_\\mu} \\max_{x: Q_H(x) \\leq 1}   \\left|Q_H(x)-Q_{H_\\mu}(x)\\right| \\leq \\varepsilon\n$$\nMore specifically, for any $x \\perp 1$, we have  $Q_H(x)>0$. We then define $z=x / \\sqrt{Q_H(x)}$. By homogeneity of $Q_H$, this ensures $Q_H(z)=1$, placing $z$ in the set $T=\\lbrace x: Q_H(x) \\leq 1\\rbrace$. The result in Line 1043 implies that for all $z\\in T$,\n$$\nE_{H_\\mu}\\left[\\left|Q_H(z)-Q_{H_\\mu}(z)\\right|\\right] \\leq \\varepsilon.\n$$\nSubstituting $z=x / \\sqrt{Q_H(x)}$ gives:\n$$\nE_{H_\\mu}\\left[\\left|\\frac{Q_H(x)-Q_{H_\\mu}(x)}{Q_H(x)}\\right|\\right] \\leq \\varepsilon.\n$$\nMultiplying through by $Q_H(x)$ yields the original claim.\n\n4. Technical Contributions:\n\nWe agree that our algorithms builds on the previous results\n (e.g., Lee, 2023; Jambulapati et al.,\n2023; Apers de Wolf, 2020). The non-trivial\ncontribution lies in identifying, adapting, and synthesizing\nexisting classical frameworks to the quantum setting---a task\nrequiring meticulous integration of recent classical and quantum\nalgorithmic tools. The classical\nliterature on hypergraph sparsification encompasses numerous\nadvanced approaches, and selecting the right framework for quantum\nacceleration demanded substantial domain-specific insight.\n\n5. About the write-up:\n\nWe appreciate the reviewer’s feedback on the balance between the introduction and formal techniques. We will carefully revise the manuscript to streamline the preliminaries and move some important parts from the appendix to the main text, thereby enhancing clarity and facilitating the verification of our claims.\n\n\n6. Typos and Grammar:\n\nWe sincerely appreciate the reviewers’ careful reading and for pointing out these typos. We will meticulously proofread the manuscript to correct grammatical errors, including the noted typos. \n\n7. Dependency on rank:\n\nThe linear dependency on $r$ arises because our quantum algorithm QHLSO converts each hyperedge into a star graph (with $O(r)$ edges) to construct the underlying Laplacian system. This step inherently scales linearly with $r$, as each hyperedge of size $r$ requires explicit interactions among its vertices.\nNotably, our algorithm's linear dependence on $r$ is already an improvement over the quadratic dependency $O(r^2)$, which is achieved by utilizing a sparse underlying graph (see Definition 3.3) instead of general underlying graph (see  Definition 3.1).\nFurther reducing this dependency is challenging: classical hypergraph sparsification methods face fundamental limits, and quantum representations inherently require enumerating all $r$ vertices in a hyperedge for unitary operations. Thus, both classical and quantum approaches encounter a barrier for hyperedge processing.", "claims_and_evidence": "The primary claim—that the algorithm constructs an $\\varepsilon$-spectral sparsifier in $\\widetilde{O}(r \\sqrt{m n} / \\varepsilon)$ time—is substantiated by Theorem 1.1 (formalized as Theorem 4.1). A detailed proof, provided in Appendices, employs leverage score overestimates and adapts a chaining argument from Lee (2023) to establish correctness. The speedup over the classical $\\widetilde{O}(m r)$ bound is evident under reasonable assumption $\\varepsilon \\ge \\sqrt{n/ m}$. To achieve the speedup, the authors design many quantum subroutines (e.g., GraphSparsify, MultiSample), which are derived using known techniques such as quantum graph sparsification (Apers & de Wolf, 2020) and basic operations such as addition and multiplication. Applications outlined in Section 5 are straightforward to see, though details are not fully provided. No other unsupported claims stand out; all the evidence is theoretical analysis.", "methods_and_evaluation_criteria": "The methods presented make sense for the challenges of hypergraph sparsification. The algorithm is built on a sampling-based framework, utilizing hyperedge leverage score overestimates derived by quantum graph sparsification (Apers & de Wolf, 2020) and some calculations. Other quantum techniques are employed, including preparing multiple state copies (Hamoudi, 2022) for sampling and sum estimation (Li et al., 2019) for reweighting. The evaluation centers on theoretical time complexity, the number of quantum gates, queries and QRAM operations. This is an increasingly adopted way to evaluate quantum algorithms (e.g., Apers & de Wolf, 2020). No benchmark datasets are used, as expected for a theoretical contribution.", "theoretical_claims": "I almost reviewed the entire theoretical claims in this paper, including the proofs in Appendices. I think the following needs to be addressed. \n\n1. **Unitary Operations:** It would be helpful to include brief explanations of the unitary properties of some basic operations (e.g., $U_{\\mathrm{div}}, U_{\\mathrm{square}}, U_{\\mathrm{star}}$). \n\n2. **Initialization of EffectiveResistance in Proposition B.3:** This part is quite confusing. \n\n- The authors attribute their approach to Claim 7.9 from Apers & de Wolf (2020) (abbreviated as the AW paper). However, Claim 7.9 in the AW paper does not mention or use the $ \\tilde{O}(m/\\epsilon^2)$  time complexity stated in Proposition B.3.\n\n- Moreover, the AW paper actually provides a quantum method for obtaining $Z_G$  with a better time complexity, specifically $\\widetilde{O}(\\sqrt{mn}/\\varepsilon + n/\\varepsilon^4)$. Despite this, the authors opt for the slower classical algorithm with  $\\tilde{O}(m/\\epsilon^2)$ time complexity instead of leveraging the more efficient quantum approach.\n\n- Thus, the authors should either justify their preference for the classical method or consider adopting the faster quantum alternative from the AW paper.\n\n3. **Appendix C:** In line 940, you want to prove the claim that : $E_{H_{\\mu}} [ | Q_H(x) - Q_{H_{\\mu}}(x) | ] \\leq \\epsilon \\cdot Q_H(x), \\quad \\forall x \\in \\mathbb{R}^n$. Later, you proved in Line 1047 that $E_{H_{\\mu}} \\max_{x: \\|x\\| \\leq 1} | Q_H(x) - Q_{H_\\mu}(x) | \\leq \\epsilon$. How do you use this result to complete the proof of the original claim?", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "The paper builds on and extends several areas of prior literature:\n\n- Graph Sparsification: It utilizes the result of quantum graph sparsification (Apers & de Wolf, 2020) and generalizes the graph case to hypergraphs, addressing future research directions outlined in Apers & de Wolf (2020). \n\n- Hypergraph Sparsification: By incorporating quantum speedups, it advances classical algorithms (Lee, 2023; Jambulapati et al., 2023), achieving sublinear time complexity while preserving near-linear size.\n\n- Quantum Algorithms: It leverages and extends quantum tools like state preparation (Hamoudi, 2022) and sum estimation (Li et al., 2019) to achieve the speedup.", "essential_references_not_discussed": "All essential references appear to be appropriately discussed.", "other_strengths_and_weaknesses": "Strengths:\n\n- The paper presents the first quantum algorithm for the fundamental problem of hypergraph sparsification.\n\nWeakness:\n\n- The techniques employed in this paper are largely adapted from previously established methods (e.g., Lee, 2023; Jambulapati et al., 2023; Apers & de Wolf, 2020), and the technical contribution appears to be somewhat incremental.\n\n- About the write-up: The main content of the submission does not provide much detail on the formal techniques, instead devoting too much space to preliminaries. I suggest that the authors expand the later sections with more substantive information and include some proofs to help readers better understand and verify the claims.", "other_comments_or_suggestions": "Some typos and minor comments are listed below:\n\n1. In Section 2, line 190 (left), notation $D$ is redundant; line 210 (right), 'an weighted' -> 'a weighted';\n2. In Section 3, line 308 (left), 'a underlying' -> 'an underlying'; line 329 (left), 'a underlying' -> 'the underlying'; line 304 (right), $c_{e,f}$;\n3. In Section 4, line 347 (right), 'denote by' -> 'denoted by'; line 348 (right), $|\\tilde{E}| = O(n \\log n \\log r / \\varepsilon^2)$;\n4. In Section 5, line 390 (left), 'directly corollary' -> 'direct corollary'; line 410 (left), 'sparsity the' -> 'sparsify the';\n5. In Section 6, line 392 (right), $O$ -> $\\widetilde{O}$; line 429 (right), 'whether we' is redundant; line 437 (right), 'none which' -> 'none of which';\n6. In Appendix, line 617, lack an 'is'; line 793, 'corresponds' -> 'correspond'; line 816, lack an 'is'; line 887, $\\xi_1, \\ldots, \\xi_M$ -> $\\xi_1, \\ldots, \\xi_m$;\n7. In Proposition B.5, the time seems to be $\\widetilde{O}(r/\\varepsilon^2)$, since each query to $\\mathcal{R}$ requires $\\widetilde{O}(1/\\varepsilon^2)$ time from Proposition B.3;\n8. In Proposition B.6, the first step seems to use $U_{\\mathrm{star}}$ instead of $U_{\\mathrm{clique}}$, as in Proposition B.5;\n9. In line 1047, I suggest additional justification for the first inequality.", "questions_for_authors": "- I have provided some comments in the *Theoretical Claims* section above. It would be great if the authors could address them.\n\n- Furthermore, could you briefly explain why the time complexity has a linear dependency on  $r$? What are the main barriers to improving this dependency in your current approach?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aZYZEljVq9", "reviewer": "Reviewer_fTGG", "summary": "The authors claim to give the first quantum algorithm for hypergraph sparsification. Their main theorem claims that they can find a sparsifier of size $O(n/\\epsilon^2)$ in time $O(r \\sqrt{mnr} + r\\sqrt{mn}/ \\epsilon)$ with high probability. Besides the introduction, the paper is concerned with proving this result.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and review. Feel free to reach out if\nadditional clarifications are needed.", "claims_and_evidence": "All theorems and claims are supported with proofs. I am unable to verify that the proofs are correct.", "methods_and_evaluation_criteria": "The paper does not contain any experiments, or other evaluation methods.", "theoretical_claims": "I have read the proofs and skimmed the appendix, and the claims look plausible, but since I lack expertise in quantum algorithms I can't judge the correctness very well.", "experimental_designs_or_analyses": "The paper does not contain any experiments.", "relation_to_broader_scientific_literature": "I am not an expert in quantum algorithms, however, the fact that this algorithm can provide sublinear running times in dense hypergraphs is of interest, as in the classical setting this seems like an unlikely result.", "essential_references_not_discussed": "I am unfamiliar with the literature on quantum algorithms, so I am not sure if any references were missed.", "other_strengths_and_weaknesses": "Unsure", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qRhVDrdC1U", "reviewer": "Reviewer_vTAd", "summary": "Graph sparsification has been extensively studied [SS11, BSS12, LS17] and has numerous applications in graph algorithms and machine learning. As a natural generalization of graphs, hypergraphs have gained increasing attention. Similarly, hypergraph sparsification has attracted significant interest following the pioneering work of [SY'19]. Motivated by the successful application of quantum computing to graph sparsification [AD'20], this paper presents the first quantum algorithm for hypergraph sparsification. Specifically, for a hypergraph $H$ with $n$ vertices and $m$ edges, the proposed algorithm constructs an $\\epsilon$-spectral sparsifier of size $O(n \\log n \\log r / \\epsilon^2)$ in time $\\widetilde{O}(r \\sqrt{mn} / \\epsilon)$, where $r$ denotes the rank. This result significantly outperforms the best known sequential algorithm, which runs in $\\widetilde{O}(mr)$ time [JLS'23]. \nMoreover, the proposed quantum algorithm extends naturally to quantum hypergraph cut sparsification, mincut solving, and $s-t$ mincut solving, broadening its applicability to fundamental problems in hypergraph optimization.  \n\n$\\textbf{Reviewer vTAd update after rebuttal:}$ I thank the authors for their clear clarification. I will retain my score and am inclined to recommend acceptance of this paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thorough evaluation and\nconstructive feedback. Below, we address the key concerns raised:\n\n1. Essential References Not Discussed:\n\nThanks for point out these two references, we will add them for the\nrevision. Thanks for pointing out these references. We will add them in\nthe revised version of our paper.\n\n2. Running Time Assumptions:\n\nRegarding the assumptions ($\\varepsilon>\\sqrt{n / m}$ and $m>n r$), we\nwould like to point out that they are reasonable and arise naturally in\nthe context of the sparsification task: (a) $\\varepsilon>\\sqrt{n/m}$ is\na natural assumption in the sparsification task, as this is equivalent\nto that the resulting sparsified graph (with $O(n/\\varepsilon^2)$ edges)\ncontains less edges than the original graph ($O(m)$ edges). This\nassumption also appears in previous works quantum sparsification\nalgorithms (e.g., [AdW'20]). (b) $m>n r$ naturally holds whenever\nhypergraphs are not highly sparse. In dense hypergraphs, the number of\nhyperedges scales as $m=\\Theta\\left(n^r\\right) \\gg n r$. In practice,\n$r$ is typically treated as a constant greater than 2, which means that\nthe number of hyperedges only needs to be larger than the linear size of\nthe number of vertices.\n\n3. Novelty and Technical Contributions:\n\nWe acknowledge that our algorithmic analysis builds on the results of\n[JLS'23]. However, our core subroutine, QHLSO, is inspired by another\ncritical work [Jambulapati et al.'2023]. The non-trivial contribution\nlies in identifying, adapting, and synthesizing existing classical\nframeworks to the quantum setting---a task requiring meticulous\nintegration of recent classical and quantum algorithmic tools, including\n[AdW'20, Hamoudi'22]. The classical literature on hypergraph\nsparsification encompasses numerous advanced approaches, and selecting\nthe right framework for quantum acceleration demanded substantial\ndomain-specific insight. Furthermore, we intentionally prioritized\nreadability to provide the quantum algorithms community with a clear\nfoundation for exploring broader applications in this domain, while\ndemonstrating how classical and quantum techniques can be cohesively\ncombined to achieve novel efficiencies.\n\n4. Future Work Suggestion:\n\nWe thank the reviewer for directing us to the resolvent computation work\nby Ameranis et al. Exploring quantum speedups for hypergraph diffusion\nis a compelling direction, and we will mention this in our revised\nfuture work section.\n\n5. Typos and Grammar:\n\nWe will meticulously proofread the manuscript to address grammatical\nerrors, including the noted typo (Line 100: \"adopts\" → \"adopt\").", "claims_and_evidence": "The main theorem 4.3 and three corollaries 5.1, 5.2, and 5.3 are clearly stated and proved.", "methods_and_evaluation_criteria": "This paper is purely theoretical and has no experiments.", "theoretical_claims": "I reviewed the proofs in the supplementary material but didn't read them carefully.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "This paper outlines several potential directions for future work. Given the wide range of applications of graph and hypergraph sparsification, the proposed quantum graph/hypergraph sparsifier algorithm naturally opens the door to developing quantum algorithms for other graph-related problems. Additionally, considering existing research on directed and online hypergraph sparsification, it would be interesting to explore quantum algorithms for these settings as well.", "essential_references_not_discussed": "(1) $\\textbf{Cut Sparsification and Succinct Representation of Submodular Hypergraphs}$, ICALP 2024.   \nThis paper explored the cut sparsifier of submodular hypergraphs.   \n(2) $\\textbf{Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification}$, STOC 2025.   \nThis paper proposed algorithms for hypergraph spectral sparsifier under the fully-dynamic settings, which allow hyperedge insertions/deletions.", "other_strengths_and_weaknesses": "$\\textbf{Strengths:}$ (1) Hypergraph sparsification has various applications and has been extensively studied in the past few years. This paper proposed the first quantum algorithm for hypergraph sparsification.    \n(2) The proposed quantum hypergraph sparsifier has nearly linear size $\\widetilde{O}(n / \\epsilon^2)$ and takes time $\\widetilde{O}(r \\sqrt{mn} / \\epsilon)$, which outperforms the running time $\\widetilde{O}(m r)$ of [JLS'23, Lee'23], under the settings $\\epsilon \\ge \\sqrt{n/m}$ and $m \\ge n r$. When $r$ is a constant, this time complexity almost matches the lower bound $\\Omega(m)$.    \n(3) The motivation and idea of this paper are straightforward and natural. Additionally, this paper is well-written and easy to understand.        \n$\\textbf{Weaknesses:}$ (1) The running time of the proposed quantum algorithm improves the classical complexity $\\widetilde{O}(m r)$ under the two assumptions $m \\ge n r$ and $\\epsilon \\ge \\sqrt{n / m}$, which weakens this paper's contribution.     \n(2) This paper follows the sampling-based framework of [JLS'23] and primarily builds on existing techniques from [AD'20, Hamoudi'22], which somewhat limits its novelty.", "other_comments_or_suggestions": "(1) In the paper \"Hypergraph Diffusions and Resolvents for Norm-Based Hypergraph Laplacians\", Ameranis et al. proposed the first nearly-linear-time algorithm for approximately computing resolvents of the hypergraph Laplacian operator. An intriguing direction for future research could be exploring quantum speedup techniques to further improve its running time.    \n(2) Typo: Line 100, adopts -> adopt", "questions_for_authors": "See Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents the first quantum algorithm for hypergraph sparsification, and demonstrates quantum speedups for computing hypergraph cut sparsifiers, and related combinatorial problems for hypergraphs. All the reviewers give positive evaluation on the paper, and  appreciate the theoretical contribution of the work. The reviewers mentioned a few minor questions, and the authors gave satisfactory answers to the questions. I would recommend acceptance of the paper.
Decision: Accept (poster)