# quantum_speedup_for_hypergraph_sparsification__e98da290.pdf

Quantum Speedup for Hypergraph Sparsification

Chenghua Liu 1 2 Minbo Gao 1 2 Zhengfeng Ji 3 Mingsheng Ying 4

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 & de Wolf (2020). For a weighted hypergraph with n vertices, m hyperedges, and rank r, our algorithm outputs a near-linear size ε-spectral sparsifier in time e O(r mn/ε)1. This algorithm matches the quantum lower bound for constant r and demonstrates quantum speedup when compared with the state-of-the-art e 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.

1. Introduction

Sparsification serves as a foundational algorithmic paradigm wherein a densely constructed entity is transitioned to a sparse counterpart while preserving its inherent characteristics. 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

1Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China 2University of Chinese Academy of Sciences, Beijing, China 3Department of Computer Science and Technology, Tsinghua University, Beijing, China 4Centre for Quantum Software and Information, University of Technology Sydney, Sydney, Australia. Correspondence to: Zhengfeng Ji <jizhengfeng@tsinghua.edu.cn>.

Proceedings of the 42 nd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s). 1We use e O(f) to represent O (f polylog(m, n, r, 1/ε)) throughout this paper to suppress polylogarithmic factors.

number of edges by adjusting edge weights while (approximately) preserving the spectral properties of the original graph. Over the past two decades, graph sparsification has experienced several breakthroughs (see Spielman & Srivastava (2011); Batson et al. (2012)), ultimately leading to the discovery of algorithms that finds spectral sparsifiers of linear size in nearly-linear 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 learning domains, including computer vision (Simonovsky & Komodakis, 2017), clustering (Peng et al., 2015; Laenen & Sun, 2020; Agarwal et al., 2022), and streaming machine learning algorithms (Braverman et al., 2021).

Hypergraphs, a generalization of graphs, naturally emerge in various real-world scenarios where interactions go beyond pairwise relationships, such as group dynamics in biochemistry, social networks, and trade networks, as they allow a single edge to connect any number of vertices (the max number of vertices an edge contains is called the rank). Thus, as a natural generalization of the garph sparsification, the task of sparsifying hypergraphs are investigated by many researchers, starting from Soma & Yoshida (2019). Hypergraph 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 et al., 2020), semisupervised learning (Hein et al., 2013; Zhang et al., 2020; Yadati et al., 2019; Li et al., 2020), and link prediction (Yadati et al., 2020).

With the rapid development of quantum computing, many graph algorithms and machine learning tasks have benefited from quantum speedups. In the context of the sparsification paradigm, the groundbreaking work of Apers & de Wolf (2020) introduced the first quantum speedup for graph sparsification with nearly optimal query complexity, showcasing the potential of quantum computing for sparsification tasks. They further proposed several open questions about the potential for quantum speedups in broader sparsification tasks. Among these, a natural and important question is:

Is there a hypergraph sparsification algorithm

Quantum Speedup for Hypergraph Sparsification

that enables quantum speedups?

In this paper, we give an affirmative answer to this question. Specifically, we develop a quantum algorithm for constructing an ε-spectral sparsifier of near-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 while operating in sublinear time e O(r mn/ε)2, which improves the time complexity e O(mr) of the best known classical algorithm3. For the constant rank r, this time complexity matches the quantum lower bound of eΩ( mn/ε) established by Apers & de Wolf (2020) and contrasts with the classical lower bound of Ω(m) (see Remark 4.3). Additionally, for dense hypergraphs, where m Ω(nr), our algorithm achieves near-quadratic improvement, reducing the time complexity from e O(rnr) classically to e O(rn(r+1)/2) quantumly.

Hypergraph Sparsification To extend the graph sparsification 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 a hypergraph H = (V, E, w), the energy of a vector x RV is defined as a sum over all hyperedges e E, where each term is the product of the edge weight we and the quadratic form Qe(x). Here, Qe(x) represents the maximum squared difference between any two vector components xu and xv 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).

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 is of great theoretical interest, but also has wide applications in many fields, especially in graph machine learning. Consequently, researchers have been developing increasingly sophisticated and analytically refined algorithms for hypergraph sparsification in recent years. Soma & Yoshida (2019) were the first to demonstrate that an εspectral sparsifier of size e O(n3/ε2) could be constructed in time e O(nmr + n3/ε2). Subsequently, Bansal et al. (2019) improved the sparsifier size to e O(r3n/ε2) with a construction time of e O(mr2 + r3n/ε2). Further advancements by

2To be more precise, our algorithm runs in e O(r mn/ε + r mnr) time, of which the second term is usually smaller in most situations. See Remark 4.2 for a more detailed discussion. 3Typically, we assume that ε p

n/m, as sparsification is only advantageous when the number of hyperedges in the sparsifier is at most m.

Kapralov et al. (2021) and Kapralov et al. (2022) reduced the sparsifier size to nearly linear, achieving e O(n/ε4) in polynomial time. The current state-of-the-art algorithm for hypergraph sparsification, proposed by Jambulapati et al. (2023), produces a sparsifier of size e O(n/ε2) in almost linear time e O(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.

Prior to the emergence of spectral sparsification, early research focused on a relatively weaker notion called the cut sparsification. In the domain of hypergraphs, extensive research has been conducted on hypergraph cut sparsifiers, yielding significant theoretical and practical advances (Kogan & Krauthgamer, 2015; Chekuri & Xu, 2018). These sparsifiers have proven particularly valuable in efficiently approximating cut 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; Liu et al., 2021), and ranking data analysis (Li & Milenkovic, 2017).

Main Results In this work, we propose the first quantum algorithm for hypergraph sparsification that produces a sparsifier of size e O(n/ε2) in e O(r mn/ε) 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 RE 0, rank r and ε > 0, outputs with high probability4 an ε-spectral sparsifier of H with e O(n/ε2) hyperedges, in time e O(r mn/ε).

As a corollary, our algorithm could be used to construct a 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 samplingbased framework appearing in classical hypergraph sparsification 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.

Specifically, we adopt the method proposed in Jambulapati et al. (2023), where the weight on each hyperedge is

4Throughout this paper, we say something holds with high probability if it holds with probability at least 1 O (1/n).

Quantum Speedup for Hypergraph Sparsification

Table 1. Summary of results on hypergraph sparsification Reference Type Sparsifier size Time Complexity

Soma & Yoshida (2019) Classical O(n3 log n/ε2) e O(mnr + n3/ε2)

Bansal et al. (2019) Classical O(r3n log n/ε2) e O(mr2 + r3n/ε2)

Kapralov et al. (2021) Classical nr(log n/ε)O(1) O(mr2) + n O(1)

Kapralov et al. (2022) Classical O(n log3 n/ε4) e O(mr + poly(n))

Jambulapati et al. (2023); Lee (2023) Classical O(n log n log r/ε2) e O(mr)

This work Quantum O(n log n log r/ε2) e O(r mnr + r mn/ε)

This e O(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 overestimates would require e O(mr) time by an iterative/contractive algorithm which mainly follows the algorithm for computing an approximate John ellipse (Cohen et al., 2019). Then, one can sample e O(n/ε2) hyperedges in e O(n/ε2) time, and reweight them to get a hypergraph sparsifier.

We discover that, with the assistance of a series of classical and quantum techniques, the computation of hyperedge leverage score overestimate can be accelerated. To be more precise, we realize that the computation of hyperedge leverage 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 efficiently constructed (in e O(r mnr) time) by the quantum graph sparification algorithm proposed by Apers & de Wolf (2020). Thus, we obtain a quantum algorithm (Algorithm 1) that allows efficient queries to the hyperedge leverage score overestimate running in sublinear time.

The quantum procedure described above, however, introduces a new challenge for the sampling step: the exact sampling probabilities cannot be directly accessed. To resolve this issue, we utilize the technique of preparing many copies of a quantum state (Hamoudi, 2022) to get e O(n/ε2) samples in e O(r mn/ε) time without explicitly computing the normalization constant for the sampling probability. After sampling hyperedges, we encounter a problem in the reweighting stage due to the unknown normalization constant. We address this issue partially using the quantum sum estimation procedure (Theorem 2.9), while the imprecision introduced during this procedure necessitates a more rigorous analysis. We complete the correctness analysis by employing the novel chaining argument proposed in Lee (2023).

Related Works Quantum algorithms have demonstrated significant potential in graph-theoretic and optimization

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 computation, spectral clustering, and Laplacian system solving, while also providing fundamental lower bounds for quantum graph sparsification. This work catalyzed several breakthrough results for graph problems. Apers & Lee (2021) developed a quantum algorithm for exact minimum cut computation, achieving quantum speedups when the graph 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 accelerated motif clustering computations.

A significant theoretical advancement emerged in Apers & Gribling (2024), which generalized the quantum graph sparsification framework to quantum spectral approximation by combining leverage score sampling with Grover search. This generalization enabled efficient approximation of Hessians and gradients in barrier functions for interior point methods, yielding quantum speedups for linear programming under specific conditions. These spectral approximation 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 approximation, respectively.

2. Preliminaries

2.1. Notation

For clarity, we use [n] to represent the set {1, 2, . . . , n} and [n]0 to represent the set {0, 1, . . . , n 1}. Throughout this paper, we use G = (V, F, c) to denote a graph, where

Quantum Speedup for Hypergraph Sparsification

V is the vertex set, F is the edge set, and c : F R 0 represents the edge weights. For an undirected weighted hypergraph, we denote it as H = (V, E, w), where V is the vertex set, E is the hyperedge set, and w : E R 0 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 e for hyperedges. Given a hyperedge e, we use e 2 to denote the corresponding induced edge set {f e : |f| = 2}.

2.2. Laplacian and Graph Sparsification

For an undirected weighted graph G = (V, F, c), the weighted degree of vertex i is defined by

deg(i) := X

f F :i f cf,

where the sum is taken over all edges f that contain i, and cf represents the weight of edge f.

Definition 2.1 (Laplacian). The Laplacian of a weighted graph G = (V, F, c) is defined as the matrix LG RV V

deg(i) ifi = j, cij if{i, j} F, 0 otherwise.

The Laplacian of graph G is given by LG = DG AG, with AG the weighted adjacency matrix (AG)ij = cij and D the diagonal weighted degree matrix DG = diag (deg (i) : i V ). LG is a positive semidefinite matrix whenever weight function c is nonnegative. The quadratic form of LG can be written as

{i,j} F cij (xi xj)2 (1)

for arbitrary vector x RV . Graph sparsification produces a reweighted graph with fewer edges, known as a graph (spectral) sparsifier. A graph spectral sparsifier of G is a reweighted subgraph that closely approximates the quadratic form of the Laplacian for any vector x RV .

Definition 2.2 (Graph Spectral Sparsifier). Let G = (V, F, c) be a weighted graph. A re-weighted graph e G = (V, e F, ec) is a subgraph of G, where ec : e F R 0 and e F = {f F : ecf > 0}. For any ε > 0, e G is an ε-spectral sparsifier of G if for any vector x RV , the following holds: x L e Gx x LGx ε x LGx.

In the groundbreaking work by Spielman & Srivastava (2011), the authors demonstrated that graphs can be efficiently sparsified by sampling edges with weights roughly

proportional to their effective resistances. This importance sampling approach is foundational to graph sparsification and has also inspired advancements in hypergraph sparsification. Next, we define the effective resistance.

Definition 2.3 (Effective Resistance). Given a graph G = (V, F, c), the effective resistance of a pair of i, j V is defined as

Rij := (δi δj) L+ G(δi δj) = L+/2 G (δi δj) 2,

where L+ G denotes the Moore-Penrose inverse of LG, and δi denotes the vector with all elements equal to 0 except for the i-th being 1.

For further details, including key properties of effective resistance used in this work, we refer the readers to Appendix A.

2.3. Hypergraph Sparsification

Here, we formally define the fundamental concept in hypergraph sparsification, namely the energy.

Definition 2.4 (Energy). Let H = (V, E, w) be a weighted hypergraph. For every vector x RV , we define its associated energy in H as

e E we Qe(x), (2)

where Qe(x) := max{i,j} e (xi xj)2.

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)).

Similar to graph sparsification, the goal of hypergraph sparsification is to produce a hypergraph spectral sparsifier with fewer hyperedges. The hypergraph spectral sparsifier of hypergraph H is a reweighted subgraph of H that approximately preserves the energy for any vector x RV .

Definition 2.5 (Hypergraph Spectral Sparsifier). Let H = (V, E, w) be a weighted hypergraph. A re-weighted hypergraph e H = (V, e E, ew) is a subgraph of H, where ew : e E R 0 and e E = {e E : ewe > 0}. For any ε > 0, e H is an ε-spectral sparsifier of G if for any vector x RV , the following holds: QH(x) Q e H(x) ε QH(x).

The hypergraph cut sparsifier is a weaker notion of sparsification than the spectral sparsifier. Specifically, for a weighted hypergraph H (V, E, w), we restrict x RV to be the characteristics vector 1S {0, 1}V of a vertex subset S V . The energy QH (1S), or simply QH(S), can be expressed as QH(S) = P

e δS we, where δS denotes the

Quantum Speedup for Hypergraph Sparsification

set of hyperedges crossing the cut (S, V \ S). The ε-cut sparsifier e H of the hypergraph H is a subgraph that satisfies the following: QH (S) Q e H (S) ε QH (S) , S V. (3)

2.4. Quantum Computing and Speedup

In quantum mechanics, a d-dimensional quantum state |v = (v0, . . . , vd 1) is a unit vector in a complex Hilbert space Cd, namely, P

i [d]0 |vi|2 = 1. We define the computational basis of the space Cd by {|i }i [d]0, where |i = (0, . . . , 0, 1, 0, . . . , 0) with the i-th entry (0-indexed) being 1 and others being 0. The inner product of quantum states |u , |v Cd is defined by u|v = P

i [d]0 u i vi, where z

denotes the conjugate of z C. The tensor product of quantum states |u Cd1 and |v Cd2 is their Kronecker product, |u |v = (u0v0, u0v1, . . . , ud1 1vd2 1) , which can be abbreviated as |u |v .

A quantum bit, or qubit, is a quantum state |ψ in C2, expressible as |ψ = α |0 + β |1 , where α, β C and |α|2 + |β|2 = 1. Furthermore, an n-qubit state is in the tensor product space of n Hilbert spaces C2, denoted as (C2) n = C2n, with the computational basis {|i }i [2n]0. To extract classical information from an n-qubit state |ψ , we measure it in the computational basis, yielding outcome i with probability p (i) = | ψ|i |2 for i [2n]0. The operations in quantum computing are described by unitary matrices U, satisfying UU = U U = I, where U is the Hermitian conjugate of U, and I is the identity matrix.

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, Ovtx G and Owt G , which are defined as follows for any edge f = {i, j} F:

Ovtx G : |f |0 7 |f |i |j ,

Owt G : |f |0 7 |f |cf ,

where |f Cm, |i , |j Cn, and cf is represented as a floating-point number with |cf Cdacc. Taking dacc = e O(1) allows for achieving arbitrary desired floating-point accuracy. Similarly, we assume access to hyperedge oracle OH for the hypergraph H = (V, E, w), which consists of three unitaries Osize H , Ovtx H and Owt H. These unitaries allow for the following queries for any hyperedge e E:

Osize H : |e |0 7 |e ||e| ,

Ovtx H : |e |0 r 7 |e O

i e |i |0 (r |e|) ,

Owt H : |e |0 7 |e |we .

In many quantum algorithms, information can be stored and retrieved in quantum-read classical-write random access memory (QRAM) (Giovannetti et al. (2008)), which is

employed in numerous time-efficient quantum algorithms. QRAM enables the storage or modification of an array c1, . . . , cn of classical data while allowing quantum query access via a unitary UQRAM : |i |0 7 |i |ci . 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 somewhat speculative.

A quantum (query) algorithm A is a quantum circuit consisting of a sequence of unitaries U1, . . . , UT , where each Ut could be a quantum gate, a quantum oracle, or a QRAM operation. The time complexity of A is determined by the number T of quantum gates, oracles and QRAM operations it contains. The algorithm A operates on n qubits, starting with the initial state |0 n. The unitary operators U1, . . . , UT are then applied sequentially to the quantum state, resulting in the final quantum state |ψ = UT . . . U1 |0 n. Finally, a measurement is performed on |ψ in the computational basis |i for i [2n]0, yielding a classical outcome i with probability | i|ψ |2.

In our paper, we incorporate quantum algorithms from previous research as basic components of our algorithm. One such algorithm is quantum graph sparsification, initially proposed by Apers & de Wolf (2020) using adjacency-list 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.

Theorem 2.6 (Quantum Graph Sparsification, Theorem 1 in Apers & de Wolf (2020)). There exists a quantum algorithm Graph Sparsify(OG, ε) that, given query access OG to a weighted graph G = (V, F, c) with |V | = n, |F| = m, c RF 0 and ε p

n/m, outputs with high probability the explicit description of an ε-spectral sparsifier of G with e O(n/ε2) edges, using e O( mn/ε) queries to OG and in time e O( mn/ε).

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 1 in Hamoudi (2022)). There exists a quantum algorithm that, given oracle access Ow to a vector w Rn 0 (0-indexed) (Ow : |i |0 7 |i |wi , i [n]), and k [n], with high probability, outputs k copies of the state |w , where

i [n]0 wi. The algorithm uses e O(

queries to Ow, and runs in e O(

Quantum Speedup for Hypergraph Sparsification

By performing measurements on each of the generated quantum state copies, a sample sequence is produced, where each element i is selected with a probability proportional to wi. This leads to the following corollary. Corollary 2.8. There exists a quantum algorithm Multi Sample(Ow, k) that, given query access Ow to a vector w Rn 0 and integer k [n], outputs with high probability a sample sequence σ [n]k such that each element i is sampled with probability proportional to wi. The algorithm uses e O(

nk) queries to Ow, and runs in e O(

In addition to the quantum algorithms mentioned above, we also require quantum sum estimation, which provides a quadratic speedup over classical approaches. Theorem 2.9 (Quantum Sum Estimation, Lemma 3.1 in Li et al. (2019)). There exists a quantum algorithm Sum Estimate(Ow, ε) that, given query access Ow to a vector w Rn 0 and ε > 0, outputs with high probability an estimate es for s = P

i [n] wi satisfying |es s| εs, using e O( n/ε) queries to Ow and in e O( n/ε) time.

3. Quantum Algorithm for Leverage Score Overestimates

In this section, we will introduce the notion of hyperedge leverage scores, which is a 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 a quantum algorithm that computes the overestimates given query access to a hypergraph.

To define hyperedge leverage scores, we first introduce the concept of underlying graphs. Definition 3.1 (Underlying Graph). Given an undirected weighted hypergraph H = (V, E, w), an underlying graph of H is defined as a multigraph G = (V, F, c) with edge set F = (e, f) : f e 2 , e E and weights c RF 0, satisfying

f ( e 2) ce,f , e 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 labeled according to the hyperedges they originate from.

With this concept, we define the hyperedge leverage score as follows: Given a hypergraph H and one of its corresponding underlying graphs G, the leverage score of a hyperedge e E, is defined as

ℓe := we Re, (5)

where Re = max{Rf : f e 2 }, and Rf 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 O(n), 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 leverage scores with a specific underlying graph, such that the total sum is bounded by a parameter ν = O(n).

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 z RE 0 is a ν-(bounded hyperedge leverage score) overestimate for H if z 1 ν and there exists a corresponding underlying graph G = (V, F, c), satisfying the constraints Equation (4), such that for all e E, ze ℓe.

To obtain an overestimate, we need to handle the weights of the underlying graph, which contains O(mr2) edges. Nevertheless, it is sufficient to manage only O(mr) edges by replacing each hyperedge with a sparse subgraph (e.g., a star graph with up to r 1 edges) rather than a complete clique (Definition 3.1). We refer to the resulting graph as a sparse underlying graph.

Definition 3.3 (Sparse Underlying Graph). Given an undirected weighted hypergraph H = (V, E, w), a sparse underlying graph of H is defined as G = (V, F, c) with edge set F = {(e, f) : f Se, e E} and weights c RF 0, satisfying

f Se ce,f, e E. (6)

For each e E, we fix an arbitrary vertex ae e and define Se = {f e 2 : ae f}.

Now we present our quantum algorithm of hyperedge leverage score overestimates, which is a key step for our main quantum algorithm for hypergraph sparsification. Our algorithm 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 oracle to the hypergraph, the number of iterations T, the graph sparsification parameter α1, and the effective resistance approximation factor α2. The output of our quantum algorithm is a data structure, which could provide a query access to the hyperedge leverage score overestimates (see Proposition B.6 for a formal description of the output).

Recall that the choice of the underlying graph G determines the hyperedge leverage scores, as well as their overestimates. Our algorithm iteratively adjusts the edge weights

Quantum Speedup for Hypergraph Sparsification

of the underlying graph over roughly log r rounds to construct a suitable G. In each iteration, we use quantum graph sparsification to reduce the graph s size and reassign hyperedge weights to the edges of the underlying graph according to edge leverage scores. To maintain overall efficiency, this process is implemented entirely quantumly through a series of quantum subroutines. The process begins with Weight Initialize, which is employed during the first iteration to establish quantum query access to the weights of the underlying graph via queries to the original hypergraph (Proposition B.1). In each iteration, the system utilizes UGraph Store to provide quantum query access to the stored weights of the sparsifier obtained from Graph Sparsify (Proposition B.4). Subsequently, Effective Resistance enables efficient quantum queries to the approximate effective resistance of a graph (Proposition B.3). For the next iteration, Weight Compute implements quantum query access to the updated weights of the sparse underlying graph (Proposition B.5). The complete algorithm is presented in Algorithm 1.

Algorithm 1 Quantum Hyperedge Leverage Score Overestimates QHLSO(OH, T, α1, α2) Require: Quantum Oracle OH to a hypergraph H = (V, E, w) with |V | = n, |E| = m, rank r; the number of episodes T N; positive real numbers α1, α2 R. Ensure: An instance Z of QOverestimate which stores the vector z being an O(n)-overestimate for H. 1: Let UG(1) = Weight Initialize(OH). 2: for t = 1 to T do 3: e G(t) = (V, e F (t), ec(t)) Graph Sparsify(UG(t), α1).

4: G(t) UGraph Store( e G(t)). 5: R(t) Effective Resistance( e G(t), α2). 6: UG(t+1) = Weight Compute(OH, R(t), G(t)). 7: end for 8: C1 2(1 + α1+α2

1 α1 ) exp (log r/T).

9: Z QOverestimate({G(t) : t [T]}, {R(t) : t [T]}, OH, C1, T).

The algorithm s complexity is described in the following theorem.

Theorem 3.4 (Quantum Hyperedge Leverage Score Overestimates). There exists a quantum algorithm QHLSO(OH, T, α1, α2) that, given integer T = O(log r), positive real numbers α1, α2 < 1 and query access OH to a hypergraph H = (V, E, w) with |E| = m, |V | = n, w RE 0, and rank r, the algorithm runs in time e O(r mnr). Then, with high probability, it provides query access to a ν-overestimate z with ν = O(n), where each query to z requires e O(r) time.

Due to space constraints, the proof of Theorem 3.4 is deferred to Appendix B.

4. Quantum Hypergraph Sparsification

Assuming query access to a ν-overestimate, we aim to implement the sampling scheme in a quantum framework. By leveraging Corollary 2.8, we can sample a sequence σ = (σi : σi E) where each element e is sampled with probability proportional to ze. By combining the information of each sampled e with the normalization factor obtained via Sum Estimate, 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 QHypergraph Sparse(OH, ε) Require: Quantum Oracle OH to a hypergraph H = (V, E, w) with |V | = n, |E| = m, rank r; accuracy ε > 0. Ensure: An ε-spectral sparsifier of H, denoted by e H = (V, e E, ew), | e E| = O(n log n log r/ε2). 1: e E = , ew = 0, M Θ n log n log r/ε2 . 2: Z QHLSO(OH, log(r 1), 0.1, 0.1). 3: σ Multi Sample(Z.Query, M). 4: s Sum Estimate(Z.Query, 0.1). 5: for i = 1 to M do 6: wσi measurement outcome of the second register of Owt H |σi |0 . 7: zσi measurement outcome of the second register of Z.Query |σi |0 . 8: e E e E {σi}, ewσi ewσi + wσi s/(Mzσi). 9: end for

Theorem 4.1 (Quantum Hypergraph Sparsification). There exists a quantum algorithm that, given query access to a hypergraph H = (V, E, w) with |E| = m, |V | = n, w RE 0, rank r, and ε > 0, outputs with high probability the explicit description of an ε-spectral sparsifier of H with O(n log n log r/ε2) hyperedges, in time e O(r mnr + r mn/ε).

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. Remark 4.2. We assume ε p

n/m, as sparsification is beneficial only when the sparsifier contains less m hyperedges. It is also generally the case that m nr, as the objects being sparsified are dense. It s worth noting that the time complexity e O (r mnr + r mn/ε) simplifies to e O (r mn/ε) whenever ε p

n/m and m nr. Remark 4.3. For the hypergraph with constant rank r, the above complexity contrasts with the classical lower bound of Ω(m). This lower bound arises from the fact that, in the case of graphs (r = 2), there exists an Ω(m) classical query lower bound for determining whether a graph is con-

Quantum Speedup for Hypergraph Sparsification

nected, which establishes the same lower bound for both cut sparsifiers and spectral sparsifiers.

5. Applications

As a direct corollary of Theorem 4.1, we can compute a cut sparsifier for a hypergraph in sublinear time.

Corollary 5.1 (Quantum Hypergraph Cut Sparsification). There exists a quantum algorithm that, given query access to a hypergraph H = (V, E, w) with |E| = m, |V | = n, w RE 0, rank r, and ε > 0, outputs with high probability the explicit description of an ε-cut sparsifier of H with O(n log n log r/ε2) hyperedges in time e O(r mnr + r mn/ε).

Similar to the case for graphs, quantum hypergraph cut sparsification facilitates faster approximation algorithms for cut problems. Below, we highlight two such applications.

Mincut Given a hypergraph H = (V, E, w), the hypergraph mincut problem asks for a vertex set S : S V that minimizes the energy QH(S). To the best of our knowledge, the fastest algorithm for computing the mincut in a hypergraph without error runs in e O(mnr) time (Klimmek & Wagner, 1996; Mak & Wong, 2000). By applying Corollary 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 a (1 + ε)- approximate mincut in time e O(r mn/ε + rn2), which is sublinear in the number of hyperedges.

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 RE 0, rank r, and ε > 0, outputs with high probability the (1 + ε)-approximate mincut of H in time e O(r mnr + r mn/ε + rn2).

s-t mincut Given a hypergraph H = (V, E, w) and two vertices s, t V , the s-t mincut problem seeks a vertex set S V with |S {s, t}| = 1(i.e., either s S or t S) that minimizes the energy QH(S). The standard approach for computing an s-t mincut in a hypergraph is computing the s-t maximum flow in an associated digraph with O(n + m) vertices and O(mr) edges (Lawler, 1973). And an s-t maximum flow in such graph can be found in e O(mr m + n) time (Lee & Sidford, 2014). By combining Corollary 5.1 with the aforementioned approach, we can compute a (1 + ε)-approximate s-t mincut in time e O(r mn/ε) whenever m = Ω(n2), which is sublinear in number of hyperedges.

Corollary 5.3 (Quantum Hypergraph s-t Mincut Solver). There exits a quantum algorithm that, given query access to a hypergraph H = (V, E, w) with |E| = m, |V | = n, w

RE 0, rank r, two vertices s, t V , and ε > 0, outputs with high probability the (1 + ε)-approximate s-t mincut of H in time e O(r mnr + r mn/ε + rn3/2).

6. Conclusion and Future works

In this paper, we present a quantum algorithm for hypergraph sparsification with time complexity e O(r mn/ε + r mnr), where m, n, r, ε are the number of hyperedges, the number of vertices, rank of hypergraph and precision of sparsifier, respectively.

Our paper naturally raises several open questions for future work. For instance:

Quantum graph sparsification has directly led to the development of numerous quantum algorithms, including max-cut for graphs (Apers & de Wolf, 2020), graph minimum cut finding (Apers & Lee, 2021), graph minimum s-t cut finding (Apers et al., 2024), motif clustering (Cade et al., 2023). A natural question arises: for more related problems in hypergraphs, such as hypergraph-k-cut, minmax-hypergraph-k-partition, hypergraph spectral diffusion (Ameranis et al., 2023), can we design faster quantum algorithms compared to classical ones?

We conjecture that the runtime of our quantum algorithm is tight up to polylogarithmic factors when ε 1/ r. Can we establish a quantum lower bound of Ω(r mn/ε) for hypergraph sparsification? Alternatively, can we improve the time complexity for quantum hypergraph sparsification, or further enhance the runtime for hypergraph cut sparsification? Furthermore, state-of-the-art hypergraph cut sparsification achieves a size of O(n log n/ε2) (without the log r factor) in e O(mn + n10/ε7) time (Chen et al., 2020) can we design a faster quantum algorithm that matches this size?

Hypergraph sparsification has been extended to various frameworks, including online hypergraph sparsification (Soma et al., 2024; Khanna et al., 2025), directed hypergraph sparsification (Oko et al., 2023), submodular hypergraph sparsification (Kenneth & Krauthgamer, 2024), generalized linear models sparsification (Jambulapati et al., 2024), and quotient sparsification for submodular functions (Quanrud, 2024). A natural question is can we develop specialized quantum algorithms for these settings?

Acknowledgements

The work was supported by National Key Research and Development Program of China (Grant No.

Quantum Speedup for Hypergraph Sparsification

2023YFA1009403), National Natural Science Foundation of China (Grant No. 12347104), Beijing Natural Science Foundation (Grant No. Z220002), and Tsinghua University.

Impact Statement

This paper presents work whose goal is to 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.

Agarwal, A., Khanna, S., Li, H., and Patil, P. Sublinear algorithms for hierarchical clustering. Advances in Neural Information Processing Systems, 35:3417 3430, 2022.

Akbudak, K., Kayaaslan, E., and Aykanat, C. Hypergraph partitioning based models and methods for exploiting cache locality in sparse matrix-vector multiplication. SIAM Journal on Scientific Computing, 35(3): C237 C262, 2013. doi: 10.1137/100813956.

Alpert, C. J. and Kahng, A. B. Recent directions in netlist partitioning: a survey. Integration, 19(1):1 81, 1995. ISSN 0167-9260. doi: https://doi.org/10.1016/ 0167-9260(95)00008-4.

Ameranis, K., Chen, A., De Pavia, A., Orecchia, L., and Tani, E. Hypergraph diffusions and resolvents for norm-based hypergraph laplacians. ar Xiv preprint ar Xiv:2307.11042, 2023.

Apers, S. and de Wolf, R. Quantum speedup for graph sparsification, cut approximation and laplacian solving. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 637 648, 2020. doi: 10.1109/FOCS46700.2020.00065.

Apers, S. and Gribling, S. Quantum speedups for linear programming via interior point methods, 2024. URL https://arxiv.org/abs/2311.03215.

Apers, S. and Lee, T. Quantum complexity of minimum cut. In Proceedings of the 36th Computational Complexity Conference, 2021. doi: 10.4230/LIPIcs.CCC.2021.28.

Apers, S., Auza, A., and Lee, T. A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs, 2024. URL https://arxiv.org/abs/ 2110.15587.

Ballard, G., Druinsky, A., Knight, N., and Schwartz, O. Hypergraph partitioning for sparse matrix-matrix multiplication. ACM Trans. Parallel Comput., 3(3), December 2016. ISSN 2329-4949. doi: 10.1145/3015144.

Bansal, N., Svensson, O., and Trevisan, L. New notions and constructions of sparsification for graphs and hypergraphs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, pp. 910 928, 2019. doi: 10.1109/ FOCS.2019.00059.

Batson, J., Spielman, D. A., and Srivastava, N. Twiceramanujan sparsifiers. SIAM Journal on Computing, 41 (6):1704 1721, 2012. doi: 10.1137/090772873.

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 3557, 2021.

Cade, C., Labib, F., and Niesen, I. Quantum Motif Clustering. Quantum, 7:1046, 2023. ISSN 2521-327X. doi: 10.22331/q-2023-07-03-1046.

Chan, T.-H. H., Louis, A., Tang, Z. G., and Zhang, C. Spectral properties of hypergraph laplacian and approximation algorithms. Journal of the ACM, 65(3), 2018. doi: 10.1145/3178123.

Chekuri, C. and Xu, C. Minimum cuts and sparsification in hypergraphs. SIAM Journal on Computing, 47(6):2118 2156, 2018. doi: 10.1137/18M1163865.

Chen, L., Kyng, R., Liu, Y. P., 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.

Chen, Y., Khanna, S., and Nagda, A. Near-linear size hypergraph cut sparsifiers. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pp. 61 72, 2020. doi: 10.1109/FOCS46700.2020.00015.

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 log1/2 n time. In Proceedings of the fortysixth annual ACM symposium on Theory of computing, pp. 343 352, 2014.

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.

Cohen, M. B., Cousins, B., Lee, Y. T., and Yang, X. A near-optimal algorithm for approximating the John ellipsoid. In Beygelzimer, A. and Hsu, D. (eds.), Proceedings of the Thirty-Second Conference on Learning

Quantum Speedup for Hypergraph Sparsification

Theory, volume 99 of Proceedings of Machine Learning Research, pp. 849 873. PMLR, 25 28 Jun 2019. URL https://proceedings.mlr.press/v99/ cohen19a.html.

Giovannetti, V., Lloyd, S., and Maccone, L. Quantum random access memory. Phys. Rev. Lett., 100:160501, Apr 2008. doi: 10.1103/Phys Rev Lett.100.160501.

Hamoudi, Y. Preparing many copies of a quantum state in the black-box model. Phys. Rev. A, 105:062440, Jun 2022. doi: 10.1103/Phys Rev A.105.062440.

Hein, M., Setzer, S., Jost, L., and Rangapuram, S. S. The total variation on hypergraphs - learning on hypergraphs revisited. In Burges, C., Bottou, L., Welling, M., Ghahramani, Z., and Weinberger, K. (eds.), Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https://proceedings.neurips. cc/paper_files/paper/2013/file/ 8a3363abe792db2d8761d6403605aeb7-Paper. pdf.

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.1145/3564246.3585136.

Jambulapati, A., Lee, J. R., Liu, Y. P., and Sidford, A. Sparsifying generalized linear models. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pp. 1665 1675, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400703836. doi: 10.1145/3618260.3649684.

Kapralov, M., Krauthgamer, R., Tardos, J., and Yoshida, Y. Towards tight bounds for spectral sparsification of hypergraphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 598 611, 2021. doi: 10.1145/3406325.3451061.

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.1109/ FOCS52979.2021.00114.

Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. Multilevel hypergraph partitioning: applications in vlsi domain. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7(1):69 79, 1999. doi: 10.1109/92. 748202.

Kenneth, Y. and Krauthgamer, R. Cut Sparsification and Succinct Representation of Submodular Hypergraphs. In Bringmann, K., Grohe, M., Puppis, G.,

and Svensson, O. (eds.), 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 97:1 97:17, Dagstuhl, Germany, 2024. Schloss Dagstuhl Leibniz-Zentrum f ur Informatik. ISBN 978-3-95977322-5. doi: 10.4230/LIPIcs.ICALP.2024.97. URL https://drops.dagstuhl.de/entities/ document/10.4230/LIPIcs.ICALP.2024.97.

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.

Klimmek, R. and Wagner, F. A simple hypergraph min cut algorithm. Technical Report B, 02, 1996. URL http://edocs.fu-berlin.de/docs/ servlets/MCRFile Node Servlet/FUDOCS_ derivate_000000000297/1996_02.pdf.

Kogan, D. and Krauthgamer, R. Sketching cuts in graphs and hypergraphs. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pp. 367 376, 2015. doi: 10.1145/2688073.2688093.

Laenen, S. and Sun, H. Higher-order spectral clustering of directed graphs. Advances in neural information processing systems, 33:941 951, 2020.

Lawler, E. L. Cutsets and partitions of hypergraphs. Networks, 3(3):275 285, 1973. doi: https://doi.org/10.1002/ net.3230030306.

Lee, J. R. Spectral hypergraph sparsification via chaining. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 207 218, 2023. doi: 10.1145/ 3564246.3585165.

Lee, Y. T. and Sidford, A. Path finding methods for linear programming: Solving linear programs in O(

rank) 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.

Lee, Y. T. and Sun, H. Constructing linear-sized spectral sparsification in almost-linear time. SIAM Journal on Computing, 47(6):2315 2336, 2018. doi: 10.1137/ 16M1061850.

Li, P. and Milenkovic, O. Inhomogeneous hypergraph clustering with applications. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS 17, pp. 2305 2315, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.

Quantum Speedup for Hypergraph Sparsification

Li, P., He, N., and Milenkovic, O. Quadratic decomposable submodular function minimization: Theory and practice. Journal of Machine Learning Research, 21(106):1 49, 2020. URL http://jmlr.org/papers/v21/ 18-790.html.

Li, T., Chakrabarti, S., and Wu, X. Sublinear quantum algorithms for training linear and kernel-based classifiers. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 3815 3824. PMLR, 09 15 Jun 2019. URL https://proceedings.mlr.press/v97/ li19b.html.

Li, X., Song, Z., and Yu, J. Quantum speedups for approximating the John ellipsoid, 2024. URL https: //arxiv.org/abs/2408.14018.

Liu, M., Veldt, N., Song, H., Li, P., and Gleich, D. F. Strongly local hypergraph diffusions for clustering and semi-supervised learning. In Proceedings of the Web Conference 2021, WWW 21, pp. 2092 2103, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383127. doi: 10.1145/3442381.3449887.

Mak, W.-K. and Wong, D. A fast hypergraph min-cut algorithm for circuit partitioning. Integration, 30(1):1 11, 2000. ISSN 0167-9260. doi: 10.1016/S0167-9260(00) 00008-0.

Oko, K., Sakaue, S., and Tanigawa, S.-i. Nearly Tight Spectral Sparsification of Directed Hypergraphs. In 50th International Colloquium on Automata, Languages, and Programming, volume 261, pp. 94:1 94:19, 2023. doi: 10.4230/LIPIcs.ICALP.2023.94.

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 functions. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 5209 5248, 2024. doi: 10.1137/1.9781611977912.187.

Simonovsky, M. and Komodakis, N. Dynamic edgeconditioned filters in convolutional neural networks on graphs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3693 3702, 2017.

Soma, T. and Yoshida, Y. Spectral sparsification of hypergraphs. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2570 2581, 2019. doi: 10.1137/1.9781611975482.159.

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. 405 417, Cham, 2024. Springer Nature Switzerland. ISBN 978-3-031-59835-7.

Song, Z., Yin, J., and Zhang, R. Revisiting quantum algorithms for linear regressions: Quadratic speedups without 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.1137/080734029.

Takai, Y., Miyauchi, A., Ikeda, M., and Yoshida, Y. Hypergraph clustering based on pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1970 1978, 2020. doi: 10.1145/3394486.3403248.

Yadati, N., Nimishakavi, M., Yadav, P., Nitin, V., Louis, A., and Talukdar, P. Hypergcn: A new method for training graph convolutional networks on hypergraphs. In Advances in Neural Information Processing Systems, volume 32, 2019. URL https://proceedings.neurips. cc/paper_files/paper/2019/file/ 1efa39bcaec6f3900149160693694536-Paper. pdf.

Yadati, N., Nitin, V., Nimishakavi, M., Yadav, P., Louis, A., and Talukdar, P. Nhp: Neural hypergraph link prediction. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, CIKM 20, pp. 1705 1714, 2020. doi: 10.1145/3340531.3411870.

Yoshida, Y. Cheeger inequalities for submodular transformations. In Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, pp. 2582 2601, 2019.

Zhang, C., Hu, S., Tang, Z. G., and Chan, T.-H. H. Rerevisiting learning on hypergraphs: Confidence interval, subgradient method, and extension to multiclass. IEEE Transactions on Knowledge and Data Engineering, 32 (3):506 518, 2020. doi: 10.1109/TKDE.2018.2880448.

Zhou, D., Huang, J., and Sch olkopf, B. Learning with hypergraphs: Clustering, classification, and embedding. In Advances in Neural Information Processing Systems, volume 19, 2006. URL https://proceedings.neurips. cc/paper_files/paper/2006/file/ dff8e9c2ac33381546d96deea9922999-Paper. 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 of a graph. Below, we outline several key properties of effective resistance that will be utilized in this work.

Lemma A.1 (Foster). For a weighted graph G = (V, F, c), let Rij represent the effective resistance between vertices i and j. Then, it holds that P

{i,j} F cij Rij n.

Proof. For a edge {i, j}, recall that Rij = (δi δj) L+ G (δi δj), then

{i,j} F cij Rij = X

{i,j} F Tr cij (δi δj) (δi δj) L+ G = Tr LGL+ G n 1

since rank of LG is at most n 1.

Lemma A.2 (Convexity, Lemma 3.4 in Cohen et al. (2019)). For a weighted graph G = (V, F, c), the function log Rf(c) is convex with respect to c.

B. Proof of Theorem 3.4

For a hyperedge e, let Se represent the set {f e 2 : a f}, where a is a fixed vertex in e.

Proposition B.1 (Weight Initialization for Overestimates). Suppose H = (V, E, w) is a hypergraph with vertex set V of size n, edge set E of size m, weight function w : E R 0, and OH is a quantum oracle to H. Then, there exists a quantum algorithm Weight Initialize(OH), that satisfies

Weight Initialize(OH) |e |f |0 = |e |f |c(1) e,f

with c(1) e,f = we/(|e| 1), for e E and f = {i, j} Se, and performs no action if f = {i, j} / Se, using O(1) queries

to OH, in e O(1) time. Here, we represent |f as |i |j for f = {i, j}.

Proof. Consider the following procedure: for any e E and f Se, we have

|e |f |0 |0 |0 Owt H,Osize H 7 |e |f |we ||e| |0

Ufwd 7 |e |f |we ||e| 1 |0

Udiv 7 |e |f |we ||e| 1 |c(1) e,f

U fwd 7 |e |f |we ||e| |c(1) e,f

Osize H ,Owt H 7 |e |f |0 |0 |c(1) e,f ,

where Ufwd satisfies Ufwd |i = |i 1 , Udiv satisfies Udiv |i |j |0 = |i |j |i/j . This procedure uses 4 queries to OH and e O(1) additional arithmetic operations. Therefore, let Weight Initialize(OH) = Owt H Osize H U fwd Udiv Ufwd Osize H Owt H, we know it satisfies the requirement stated in the proposition.

Recall the following classical algorithm for efficiently computing the effective resistances of a graph proposed by Spielman & Srivastava (2011).

Theorem B.2 (Effective Resistance Oracle, Theorem 2 in Spielman & Srivastava (2011)). There exists a (classical) algorithm Classical Effective Resistance(G, ε) such that for any ε > 0 and graph G = (V, F, c) with vertex set V of size n, edge set F of size m, and weights c RF 0, with high probability, returns a matrix ZG of size p n with p = 24 log n/ε2 satisfying (1 ε)Rab ZG(δa δb) 2 (1 + ε)Rab

for every pair of a, b V , where Rab is the effective resistance between a and b, in e O(m/ε2) time.

Quantum Speedup for Hypergraph Sparsification

We require a quantum variant of this effective resistance computation, as outlined below.

Proposition B.3 (Quantum Effective Resistance Oracle, Apers & de Wolf (2020, Claim 7.9)). Let G = (V, F, c) be a graph with a vertex set V of size n, an edge set F of size m, and weights c : RF 0. For ε > 0, there is a quantum data structure Effective Resistance, that supports the following operations:

Initialization: Effective Resistance(G, ε), outputs an instance R, in e O(m/ε2) time.

Query: R.Query, outputs a unitary satisfying

R.Query |a |b |0 = |a |b | e Rab

with (1 ε)Rab e Rab (1 + ε)Rab for every pair of vertices a, b V , and Rab being the effective resistance between vertices a and b, in e O(1/ε2) time.

Proof. First, we use the algorithm Classical Effective Resistance(G, ε) to obtain the matrix ZG and store each entries of matrix in QRAM. This allows us to access the matrix through a unitary UZG such that

UZG |i |j |0 = |i |j |ZG(i, j)

where ZG (i, j) is the entry in the i-th row and j-th column of the matrix ZG, i [n] , j [q] with q = 24 log n/ε2 . The time of computing and storing ZG is e O(m/ε2), and each query of UZG has a time complexity of e O(1). Consider the following procedure:

|i |j |0 |0 |0 U ZG 7 |i |j q O

k=1 |ZG (i, k) q O

k=1 |ZG(j, k) |0

denote = |i |j |Zi G |Zj G |0

Uminus 7 |i |j |Zi G |Zj G |Zi G Zj G

Usquare 7 |i |j |Zi G |Zj G | e Rij

U ZG 7 |i |j |0 |0 | e Rij

where Zi G is the i-th row of the matrix ZG, and U ZG can be implemented using O(q) queries of UZG; Uminus satisfies Uminus |i |j |0 = |i |j |i j , Usquare satisfies Usquare |i |0 = |i i2 . This procedure uses e O(1/ε2) queries to UZG and e O(1) additional arithmetic operations. Therefore, let R.Query = U ZG Usquare Uminus U ZG, we confirm that this satisfies the requirements outlined in the proposition.

The following proposition formalizes the procedure of storing a 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 a hypergraph with vertex set V of size n, edge set E of size m, weights w RE 0. Suppose G = (V, F, c) is a sparse underlying graph G of H. There is a quantum data structure UGraph Store, that supports the following operations:

Initialization: UGraph Store(G), outputs an instance G, in e O(mr) time.

Query: G.Query, outputs a unitary satisfying

G.Query |e |f |0 = |e |f |ce,f

for every edge (e, f) F, where f = {i, j} Se, and performs no action if (e, f) / F, in e O(1) time. Here, we represent |f as |i |j for f = {i, j}.

Proof. For the graph G with edge set F of size at most m(r 1), the initialization step is to store all the weights ce,f for the edges with indices (e, f) F into an array using a QRAM of size e O(mr) and in e O(mr) QRAM classical write operations.

For the query operation, the G.Query is the QRAM quantum query operation to the above array.

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 = (V, E, w) be a hypergraph with vertex set V of size n, edge set E of size m, weights RE 0. Suppose OH is a quantum oracle to H, G and R represent the instances of UGraph Store and Effective Resistance for the sparse underlying graph G = (V, F, c), respectively. Then, there exists a quantum algorithm Weight Compute(OH, G, R), such that

Weight Compute(OH, G, R) |e |f |0 = |e |f |c e,f

c e,f = ce,f Rf P

g Se ce,g Rg we, (7)

and Rf is the query result of R on vertices of f. The algorithm requires O(1) queries to OH, O(r) queries to both R and G, and runs in e O(r) time.

Proof. Consider the following procedure: for any e E and f Se, we have

|e |f |0 OH 7 |e |f |0 ( i e |i ) |0 |we |0

Ustar 7 |e |f |0 ( g Se |g |0 ) |we |0

G.Query 7 |e |f |ce,f |0 ( g Se |g |ce,g |0 ) |we |0

R.Query 7 |e |f |ce,f |Rf |0 ( g Se |g |ce,g |Rg |0 ) |we |0

Umult 7 |e |f |ce,f |Rf |wece,f Rf ( g Se |g |ce,g |Rg |ce,g Rg ) |we |0

O H,G.Query ,R.Query 7 |e |f |wece,f Rf ( g Se |ce,g Rg ) |0

Usum 7 |e |f |wece,f Rf ( g Se |ce,g Rg ) | e |0

Udiv 7 |e |f |wece,f Rf ( g Se |ce,g Rg ) | e c e,f

where e represents the sum P

g Se ce,g Rg, Ustar satisfies Ustar ( i e |i ) |0 = g Se |g |0 , and Umult, Usum, Udiv denote basic arithmetic operations multiplication, addition, and division, respectively, as previously. It s clear that this procedure meets the requirements stated in the proposition, since |Se| = O(r) for e E.

Proposition B.6 (Preparation for Overestimates). Let T N, C R, ε R, and H = (V, E, w) be a hypergraph with rank r. Assume OH is a quantum oracle to H. Suppose {G(t) : t [T]} represents a sequence of instances of UGraph Store for the sparse underlying graphs G(t) = (V, F (t), c(t)) of H, and {R(t) : t [T]} represents a sequence of instances of Effective Resistance for the corresponding underlying graphs G(t) and ε. Then, there is a quantum data structure QOverestimate, that supports the following operations:

Initialization: QOverestimate({G(t) : t [T]}, {R(t) : t [T]}, OH, C, T), outputs an instance Z in e O(P

t [T ] τt) time, where τt denotes the needed time of both UGraph Store(G(t)) and Effective Resistance(G(t), ε).

Query: Z.Query, outputs a unitary such that, for every e E

Z.Query |e |0 = |e |ze

g Se ℓ(t) e,g

where ℓ(t) e,g = c(t) e,g R(t) g , and Rg (t) is the query result of R(t) on vertices of g. This query is executed in e O(r P ιt) time, where ιt represents the time required for querying both UGraph Store and Effective Resistance for G(t).

Quantum Speedup for Hypergraph Sparsification

Proof. The case of initialization operation is straightforward. Aside from initializing for UGraph Store and Effective Resistance, we store C, T in QRAM in e O(1) time, allowing access through a unitary UC,T : |i |0 |i |C/T . For the query operation, we consider the following procedure:

|e |0 OH,Ustar 7 |e T t=1 ( g Se |g |0 ) |0

G(t).Query,R(t).Query 7 |e T t=1 g Se |g |c(t) e,g |R(t) g |0 |0

Umult 7 |e T t=1 g Se |g |c(t) e,g |R(t) g |ℓ(t) e,g |0

Usum 7 |e T t=1 g Se |g |c(t) e,g |R(t) g |ℓ(t) e,g | X

UC,T ,Umult 7 |e T t=1 g Se |g |c(t) e,g |R(t) g |ℓ(t) e,g | X

t (t) e |ze

where (t) e represents the sum P

g Se c(t) e,g R(t) g , and Uclique, Umult, Usum denote basic arithmetic operations of clique generation, multiplication, and addition, respectively, as previously. The procedure can be executed in O(r P

t [T ] ιt) time, since |Se| = O(r) for e E.

Proposition B.7. Let Z be the output of QHLSO(OH, T, α1, α2) (Algorithm 1). Then, the vector z stored in Z is a ν-overestimate for H, where ν = (1 + α2)C1n and C1 is determined by α1, α2, r, T, as defined in line 8 of Algorithm 1.

Proof. In the algorithm, e G(t) is a α1-spectral sparsifier of G(t). Let R( t) f and R(t) f be the effective resistances of e G(t)

and G(t) respectively. Since effective resistances correspond to quadratic forms in the pseudo-inverse of the Laplacian, we have 1 1+α1 R(t) f R( t) f 1 1 α1 R(t) f , f F. According to Proposition B.3, we know that (1 α2) R( t) f e R(t) f

(1 + α2) R( t) f , f F. Combining two inequalities we obtain

1 α2 1 + α1 R(t) f e R(t) f 1 + α2

1 α1 R(t) f , f F.

Let α3 := max 1 1 α2

1+α1 , 1+α2

1 α1 1 = α1+α2

1 α1 , then e R(t) f is an α3-approximate of R(t) f for f F. We define eℓ(t) e,f = ec(t) e,f e R(t) f .

We will show that z is a ν-overestimate with corresponding underlying graph G = (V, F, c), where c = 1 T P

t [T ] ec(t). Specifically, we need to verify the following two conditions:

2. ze we Re for all e E where Re = max{Rf : f e 2 }.

We show the first condition first. As eℓ(t) e,f = ec(t) e,f e R(t) f (1 + α2)ec(t) e,f R( t) f , we have

eℓ(t) e,g = C1 1

C1(1 + α2)n

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 a e. Since effective resistance is a metric on vertices, for any u, v e, it follows that Ruv Rua + Rav.

Consequently, at least one of the two terms on the RHS must be at least Ruv/2. By taking the maximum on both sides, we obtain max u,v e Ruv 2 max u e Rau

Quantum Speedup for Hypergraph Sparsification

Thus, for any e E, we have

log (we Re(c)) log (we 2 max{Rf(c) : f Se})

denote = log(we 2Rf (c))

t [T ] log 2we Rf c(t)

t [T ] log 2we (1 + α3) e R(t) f = 1

t [T ] log 2 (1 + α3) we eℓ(t) e,f /ec(t) e,f

ec(t+1) e,f P

g Se eℓ(t) e,g

+ log(2(1 + α3))

ec(t+1) e,f

+ log(2(1 + α3))

ec(T +1) e,f

+ log(2(1 + α3))

T log r + log

+ log(2(1 + α3))

(e) = log (ze)

where inequality (a) holds since log (Rf(c)) is convex with respect to c (see Lemma A.2), equality (b) follows from definition of Weight Compute (Equation (7)), inequality (c) follows from the concavity of log, and inequality (d) arises from the fact that ec(T +1) e,f

ec(1) e,f we we/(|e| 1) r,

the last equality (e) follows directly from the definition of ze in Proposition B.6, with the parameter C selected as in line 8 of Algorithm 1.

Proof of Theorem 3.4. By taking α1 = α2 = 0.1 as constants and T = log r, z becomes a 4n-overestimate according to Proposition B.7. It remains to analyze the time complexity of the algorithm.

First, we note that the Weight Initialize(OH) procedure runs in e O(1) time, as established in Proposition B.1. In each round t [T], Graph Sparsify(UG(t), α1) is executed in e O(r mnr) time, following Theorem 2.6, where e O(r) accounts for the query cost of UG(t). The resulting graph e G(t) is a α1-spectral sparsifier of G(t), and a crucial fact is that e G(t) is sparse and the number of edges in e G(t) is e O(n). Hence, we can initialize the data structures UGraph Store( e G(t)) and Effective Resistance( e G(t), α2) in e O(n) time, as per Proposition B.3 and Proposition B.4. The procedure Weight Compute(OH, R(t), G(t)) provides UG(t+1), with each query taking e O(r) time according to Proposition B.5. In the final step of the algorithm, Z can be initialized in e O(n) time and each Z.Query can be executed in e O(r) time, following Proposition B.6 with τt = e O(n) and ιt = e O(1).

To summarize, the total preprocessing time is e O(r mnr), and the per-query time is e O(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.

Quantum Speedup for Hypergraph Sparsification

Lemma C.1 (Corollary 2.13 in Lee (2023)). Let A : Rn Rs be a linear map, with a1, . . . , as representing the rows of A. The functions ϕ1, . . . , ϕm : Rs R are in the form of ϕi(x) = maxj Si wi | aj, x | for some Si [s] and w [0, 1]Si. Let D = maxi [m]|Si|. Then, for any T Bn 2 := {x Rn : x 2 1}, the following inequality holds:

j=1 ξjϕj(x)2 C0 A 2 p

log(s + n) log D sup x T

for some universal constant C0. The variables ξ1, . . . , ξm are i.i.d. Bernoulli random variables taking values 1, and A 2 is defined by A 2 := max{ Ax : x Bn 2 }.

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 w RE 0. The rank of the hypergraph is r = maxe E |e|. In the lemma, n and m correspond to the number of vertices and hyperedges, respectively. The functions ϕi capture the maximization over all edges in the clique generated by replacing each hyperedge, corresponding to the energy of the hyperedges. The number s 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.1, we present the following fact. Proposition C.2. Let H = (V, E, w) be a hypergraph with n vertices, and let G = (V, F, c) represent its underlying graph. For any x Rn such that x 1, the inequality QH(L+/2 G x) x 2 holds.

Proof. For any v Rn, we have

e E we max {i,j} e(vi vj)2

{i,j} e ce ij) max {i,j} e(vi vj)2

{i,j} e ce ij (vi vj)2

Taking v = L+/2 G x achieves we desired.

Proof of Theorem 4.1. Utilizing Algorithm 1 we can obtain a query access to ν-overestimate z with ν = 2(1 + α2)C1 n = O (n) in e O(r mnr) time. Each query can be executed in e O(r) time. Combining with quantum sampling algorithm (Corollary 2.8), we can sample a subset e E E of size M = e O(n/ε2) in e O(

Mm r) = e O(r mn/ε) time. The quantum sum estimation (Theorem 2.9) is executed in e O(r m) time, obtaining es as 0.1-approximation of s = z 1. We then move on to demonstrate the correctness of the algorithm, showing that the output e H is indeed an ε-spectral sparsifier of H.

For a hyperegde e E, we introduce the following notations

µe = ze/es,

aij = L+/2 G (δi δj) , {i, j} [n] ,

eswe/ze aij, {i, j} e,

ϕe (x) = max ae ij, x : {i, j} e , x Rn,

ϕ2 e (x) = max n ae ij, x 2 : {i, j} e o , x Rn,

where Re := max{Rf : f e 2 }. Suppose we sample a hyperedge sequence σµ = e(1) µ , . . . , e(M) µ such that each element e is sampled with probability proportional to µe (also proportional to ze). For the new obtained hypergraph Hµ, the weight of sampled hyperedge is

wµ e = # n t [M] : e(t) µ = e o

Quantum Speedup for Hypergraph Sparsification

Recall the definition that Qe(x) = max{u,v} e(xu xv)2, the energy of sampled hypergraph Hµ is given by

we(t) µ µe(t) µ Qe(t) µ (x) .

We want to choose sample time M sufficiently large such that

QH (x) QHµ (x) ε QH (x) , x Rn. (8)

Equivalently, it suffices to show that E Hµ max v:QH(v) 1

QH (v) QHµ (v) ε.

It is worth noting that for x Rn,

µe Qe L+/2x = we

ze es max {i,j} e

D L+/2x, δi δj E2 = max {i,j} e

x, ae ij 2 = ϕ2 e (x) .

Then we have QHµ L+/2x = 1

j [M] ϕ2 j (x) (9)

where ϕj (x) corresponds to the j-th sampled hyperedge using µ. Let H µ be an independent copy of Hµ, and ξt, t [M] be the i.i.d. Bernoulli 1 random variables. Note that EHµ QHµ (x) = es

s QH (x) and es/s [0.9, 1.1]. By convexity of the absolute value function, for any x T := x Rn : QH L+/2x 1 , we have

E Hµ max x T

QH L+/2x QHµ L+/2x

concavity E H µ E Hµ max x T

es QH µ L+/2x QHµ L+/2x

es E H µ E Hµ max x T

QH µ L+/2x QHµ L+/2x + s

es 1 E Hµ max x T

Equation (9) = s es E H µ E Hµ max x T

t [M] ϕ2 e(t) µ (x) ϕ2 e(t) µ (x)

es 1 E Hµ max x T

t [M] ϕ2 e(t) µ (x)

es E ξ E H µ E Hµ max x T

t [M] ξt ϕ2 e(t) µ (x) ϕ2 e(t) µ (x) + s

es 1 E ξ E Hµ max x T

t [M] ξtϕ2 e(t) µ (x)

es E ξ E Hµ max x T

t [M] ξtϕ2 e(t) µ (x)

es 1 E ξ E Hµ max x T

t [M] ξtϕ2 e(t) µ (x)

es 1 E ξ E Hµ max x T

t [M] ξtϕ2 e(t) µ (x)

Note that for any function f, the inequality maxx T |f(x)| max{maxx T f(x), 0} + max{maxx T f(x), 0} holds. Now, let f(x) = 1 M P

t [M] ξtϕ2 e(t) µ (x). The second term 0 in max{ , 0}, can be attained by the first term, since

limv 1 QH(v) = 0, combined with the identity Equation (9). Consequently, we have

E Hµ max x T

QH L+/2x QHµ L+/2x

E ξ E Hµ max x T f(x) + E ξ E Hµ max x T f(x)

es 1 E ξ E Hµ max x T 1 M

t [M] ξtϕ2 e(t) µ (x).

Quantum Speedup for Hypergraph Sparsification

The last equality holds because ξt, t [T] are i.i.d. Bernoulli 1 random variables.

Consider the random process Vx = 1 M P

j [M] ξjϕ2 j (x), where ϕj (x) corresponds to the j-th sampled hyperedge using µ, x T. By applying Lemma C.1 with the linear map A : Rn Rn(n 1)/2 defined as

(Ax)ij := max e E:{i,j} ( e 2) ae ij x, aij/ aij ,

and using Proposition C.2 to ensure that T Bn 2 , as required by Lemma C.1, we obtain:

E ξ sup x T Vx C0 A 2 p

log (n(n 1)/2 + n) log (r(r 1)/2)

j [M] ϕ2 j (x)

2C0 A 2 log n log r

j [M] ϕ2 j (x)

A 2 = max{ Ax : x Bn 2 } = max e E max {i,j} e

= max e E max {i,j} e

es max e E max {i,j} e

Observe that the component in RHS of Equation (11) can be written as

max x T 1 M

j [M] ϕ2 j (x) = max v:QH(v) 1 1 M

j [M] ϕ2 j L+/2v = max v:QH(v) 1 QHµ (v) .

The first equality holds because QH(x) = QH(x ) whenever x x ker(LG). Then we have

τ := E Hµ max v:QH(v) 1

QH (v) QHµ (v) = E Hµ max x T

QH L+/2x QHµ L+/2x

Equation (10) 6s

es 2 E ε E Hµ max x T 1 M

t [M] εtϕ2 e(t) µ (x)

Equation (11) 4 3s

es log n log r/M E Hµ

max v:QH(v) 1 QHµ (v) 1/2

concavity 4 3s

es log n log r/M

E Hµ max v:QH(v) 1 QHµ (v) 1/2

es log n log r/M (1 + τ)1/2

es log n log r/M 1 + 1

es log n log r/M 1 + 1

Therefore, we have τ 20C0 p

es log n log r/M whenever M 100C2 0es log n log r. Choosing M := 400C2 0eslog n log r/ε2 = Θ(n log n log r/ε2) yields

E Hµ max v:QH(v) 1

QH (v) QHµ (v) = τ ε.