Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.05813

Quantum Query Complexity of Persistence Statistics in Graph Zigzags

Cheng Xin

quant-phcs.CGSubmitted Sep 5, 2026• Announced Sep 8, 2026• 0 citations
arXivHTMLPDF

Abstract

We study the query complexity of estimating scalar summaries of zigzag bar lifetimes from snapshot-adjacency bits. For graphs $G_1,\ldots,G_m$ on $n$ labeled vertices, let $\ell_b$ be the snapshot lifetime of a degree-one bar $b$ of the intersection zigzag. For a probability generating function $φ(x)=\mathbb{E}[x^R]$, the statistic $F_φ=\sum_bφ(\ell_b/m)$ includes normalized degree-$r$ total persistence and the mean generalized rank over a uniform time window. An exact identity underlies our algorithm: sample $R$ uniform times; the expected generalized rank between their minimum and maximum equals $F_φ$. For graphs that rank is the circuit rank of an intersection graph, so a nonlinear barcode functional becomes an average of edge and component counts, and no barcode is computed. Without spectral-gap, homology-state, or QRAM assumptions, this gives a quantum estimator with additive error $\varepsilon n$ and $\widetilde O(\sqrt{m(K+n)}/\varepsilon)$ queries when a bound $K\ge F_φ$ is supplied, against $\widetilde O(m\min\{n^2,(K+n)/\varepsilon^2\})$ classically, and an adaptive quantum variant with the same instance dependence. These estimators are optimal in two regimes. For every fixed power weight $x^r$, $r\ge2$, and for the uniform-window mean, the worst-case complexities are $\widetildeΘ(n\sqrt m/\varepsilon)$ quantum and $Θ(n^2m)$ classical. On sparse instances, under an explicit split-leakage promise met by power and binomial weights of logarithmic degree and the promise $F_φ\le K$, they are $\widetildeΘ(\sqrt{mK}/\varepsilon)$ and $\widetildeΘ(m\min\{n^2,K/\varepsilon^2\})$. The classical lower bounds hold against fully adaptive algorithms, and fewer than $m$ such statistics cannot determine the positive-lifetime histogram. All bounds concern snapshot access; with an explicit update stream, near-linear full-barcode algorithms are known.

Comments
22 pages

Related papers

Quantum query complexity of edge connectivity.

Simon Apers, Troy Lee

The edge connectivity of a simple graph is the least number of edges whose removal disconnects the graph. We study the quantum query complexity of computing the edge connectivity of a simple graph with $n$ vertices and $m$ edges in both the adjacency matrix and adjacency array models. For classical randomized algorithms, $\Omega(n^2)$ and $\Omega(m)$ lower bounds are known for these models, respectively, showing that the trivial algorithm is optimal in terms of query complexity for both cases. In contrast, we show upper bounds of $\tilde O(n^{3/2})$ and $\tilde O(\sqrt{mn})$ on the quantum query complexity of computing edge connectivity in the adjacency matrix and adjacency array models, respectively. Our upper bound is tight up to logarithmic factors for the adjacency matrix model, while for the adjacency array model the best quantum query lower bound we know is $\Omega(n)$. Our upper bounds follow by combining a lemma on the structure of near-minimum cuts due to Rubinstein, Schramm and Weinberg (ITCS 2018) with a quantum sparsification algorithm by Apers and de Wolf (FOCS 2020). For a weighted graph, instead of edge connectivity the relevant notion is the weight of a minimum cut, i.e. the minimum total weight of a set of edges whose removal disconnects the graph. For weighted graphs we show that in the worst case $\Omega(n^2)$ queries can be needed to compute the weight of a minimum cut by a quantum algorithm in both the adjacency matrix and adjacency array models, thus no quantum speedup is possible in this case.

•Nov 19, 2020•0 citations

Quantum Approximate Counting with Bernoulli Oracles

Chengshen Gao, Yongzhen Xu, Lvzhou Li

Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given $m$ Bernoulli distributions with unknown biases $p_1,\dots,p_m$ and a gap parameter $Δ$, the goal is to estimate the fraction $ρ$ of \emph{positive} distributions ($p_i\ge1/2+Δ$) to within additive error $ε$. We prove an upper bound of $\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)$ queries, achieving a quadratic speedup over the classical sample complexity. % of $Θ(ρ/Δ^2ε^2)$. Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of $Ω(\sqrtρ/(Δε))$ via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap $Δ=Θ(1)$, which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to $\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)$ and $Ω(\frac{\sqrtρ}ε)$, thereby characterizing the query complexity of quantum counting with bounded-error oracles.

quant-pharXiv:2609.07604•Sep 8, 2026•0 citations

Quantum Query Complexity of Minimum Weight Cycles

Naman Goyal

We study the minimum weight cycle problem (MWC) and the minimum weight triangle problem (MWT) in the quantum query model, for n-vertex graphs with integer edge weights in [M] given by their adjacency matrix. Roditty and Vassilevska Williams showed that the two problems are classically equivalent. We show that an exact minimum weight cycle of an undirected graph can be found with $\tilde{O}(n^{19/12})$ queries, while $\Omega(n^{3/2})$ queries are necessary. The algorithm learns only the $n^{7/6}$ lightest vertex pairs, uses quantum counting to locate weight thresholds above them, applies a strict form of the Moore bound to bound the optimum and the size of each weight class, and searches the classes for the few heavy edges of an optimal cycle with nested quantum walks. A simpler version gives $\tilde{O}(n^{5/3})$ queries, and searching for fewer heavy edges trades queries for approximation, with a 2-approximation in $\tilde{O}(n^{8/5})$ queries and a tight $O(\log n)$-approximation in $\tilde{O}(n^{3/2})$ queries. In contrast, MWT costs $O(n^{9/7}\log M)$ queries, so the classical equivalence becomes a polynomial separation. For cycles of constant length we give explicit exponents, such as $\tilde{O}(n^{125/83})$ for the minimum weight 5-cycle, and we prove that deciding whether a graph has a k-cycle of total weight exactly zero requires $\Omega(n^{2-2/(\lfloor k/2\rfloor+1)})$ queries for every constant $k\ge 4$. Finally, non-adaptive learning graphs cannot beat $n^2$ for cycles of about $\log n$ edges, and we conjecture that exact MWC on directed graphs requires $n^{2-o(1)}$ queries.

•Oct 2, 2026•0 citations

Quantum Query Complexity of Maximum Degree and its Generalizations

Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro +1 more

We study the quantum query complexity of several basic graph problems. 1) We prove a tight $Θ(n^{3/2})$ bound for finding a maximum-out-degree vertex in an $n$-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an $n$-vertex undirected graph requires $Θ(n^{3/2})$ quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum $(k,n-k)$-Cut, which asks for the largest cut with one side of size $k$. For every constant $k\geq 1$, we give an $O(n^{2-1/(k+1)})$-query quantum algorithm. 4) We establish a reduction to Maximum $(k,n-k)$-Cut involving $k$-Graph Collision, which asks whether the marked vertices of a known graph contain a $k$-clique. For $k\geq 3$, this yields unconditional lower bounds with exponents strictly larger than $3/2$, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for $k$-Graph Collision, the reduction yields a lower bound matching our upper bound above.

quant-pharXiv:2610.13906•Oct 12, 2026•2 citations

Quantum query complexity of Hurwitz stability testing

Maxwell Fitzsimmons, Mohamed Serry, Meenu Kumari +1 more

Determining whether every trajectory of the linear system $\dot{x}=Ax$ converges to zero (or, equivalently, whether $A$ is Hurwitz stable) is a fundamental problem in control theory. It arises, for example, in verifying the stability of feedback controllers and state observers, as well as of linearized dynamical models. We study the quantum query complexity of deciding whether a matrix $A\in\mathbb{C}^{n\times n}$ is Hurwitz stable, given an exact normalized block-encoding of $A$. The query complexity is characterized in terms of the system dimension $n$ and a supplied lower bound $0<ν\leq ω_A$ on the imaginary-axis distance $ω_A:=\min_{t\in\mathbb{R}}σ_{\min}(A-\mathrm{i}tI)$, where $σ_{\min}(A)$ is the smallest singular value of $A$. We prove a query-complexity lower bound of $Ω(\sqrt{n}/ν)$, which holds even when $A$ is restricted to be real and diagonal. For general matrices with nonzero $ω_A$, we encode an approximation of the right-half-plane spectral projector $\operatorname{sign}^+(A):=(I+\operatorname{sign}(A))/2$ as a block of a matrix inverse, where $A$ is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a $(β,b,1/(4\sqrt{n}))$-block-encoded projector matrix (like $\operatorname{sign}^+(A)$) is zero or not; for constant success probability, it has complexity $Θ(β\sqrt{n})$. When the zero test is applied to specific approximations of $\operatorname{sign}^+(A)$, this yields an upper bound of $O(\sqrt{n}ν^{-2}\log(\sqrt{n}/ν))$ queries in the general case, and $O(\sqrt{n}ν^{-1}\log n)$ when $A$ is Hermitian or normal. The latter upper bound matches the lower bound up to a logarithmic factor. Thus the dimension dependence of quantum Hurwitz testing is nearly optimal, while the remaining factor in the non-normal case isolates an open conditioning gap.

quant-pharXiv:2610.41180•Nov 2, 2026•0 citations

Quantum complexity of minimum cut

Simon Apers, Troy Lee

The minimum cut problem in an undirected and weighted graph $G$ is to find the minimum total weight of a set of edges whose removal disconnects $G$. We completely characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model. If $G$ has $n$ vertices and edge weights at least $1$ and at most $τ$, we give a quantum algorithm to solve the minimum cut problem using $\tilde O(n^{3/2}\sqrtτ)$ queries and time. Moreover, for every integer $1 \le τ\le n$ we give an example of a graph $G$ with edge weights $1$ and $τ$ such that solving the minimum cut problem on $G$ requires $Ω(n^{3/2}\sqrtτ)$ many queries to the adjacency matrix of $G$. These results contrast with the classical randomized case where $Ω(n^2)$ queries to the adjacency matrix are needed in the worst case even to decide if an unweighted graph is connected or not. In the adjacency array model, when $G$ has $m$ edges the classical randomized complexity of the minimum cut problem is $\tilde Θ(m)$. We show that the quantum query and time complexity are $\tilde O(\sqrt{mnτ})$ and $\tilde O(\sqrt{mnτ} + n^{3/2})$, respectively, where again the edge weights are between $1$ and $τ$. For dense graphs we give lower bounds on the quantum query complexity of $Ω(n^{3/2})$ for $τ> 1$ and $Ω(τn)$ for any $1 \leq τ\leq n$. Our query algorithm uses a quantum algorithm for graph sparsification by Apers and de Wolf (FOCS 2020) and results on the structure of near-minimum cuts by Kawarabayashi and Thorup (STOC 2015) and Rubinstein, Schramm and Weinberg (ITCS 2018). Our time efficient implementation builds on Karger's tree packing technique (STOC 1996).

arXiv:2011.09823•Nov 19, 2020•4 citations
We study the query complexity of estimating scalar summaries of zigzag bar lifetimes from snapshot-adjacency bits.
For graphs G1,…,GmG_1,\ldots,G_mG1​,…,Gm​ on nnn labeled vertices, let ℓb\ell_bℓb​ be the snapshot lifetime of a degree-one bar bbb of the intersection zigzag. For a probability generating function φ(x)=E[xR]φ(x)=\mathbb{E}[x^R]φ(x)=E[xR], the statistic Fφ=∑bφ(ℓb/m)F_φ=\sum_bφ(\ell_b/m)Fφ​=∑b​φ(ℓb​/m) includes normalized degree-rrr total persistence and the mean generalized rank over a uniform time window. An exact identity underlies our algorithm: sample RRR uniform times; the expected generalized rank between their minimum and maximum equals FφF_φFφ​. For graphs that rank is the circuit rank of an intersection graph, so a nonlinear barcode functional becomes an average of edge and component counts, and no barcode is computed.
Without spectral-gap, homology-state, or QRAM assumptions, this gives a quantum estimator with additive error εn\varepsilon nεn and O~(m(K+n)/ε)\widetilde O(\sqrt{m(K+n)}/\varepsilon)O(m(K+n)​/ε) queries when a bound K≥FφK\ge F_φK≥Fφ​ is supplied, against O~(mmin⁡{n2,(K+n)/ε2})\widetilde O(m\min\{n^2,(K+n)/\varepsilon^2\})O(mmin{n2,(K+n)/ε2}) classically, and an adaptive quantum variant with the same instance dependence. These estimators are optimal in two regimes. For every fixed power weight xrx^rxr, r≥2r\ge2r≥2, and for the uniform-window mean, the worst-case complexities are Θ~(nm/ε)\widetildeΘ(n\sqrt m/\varepsilon)Θ(nm​/ε) quantum and Θ(n2m)Θ(n^2m)Θ(n2m) classical. On sparse instances, under an explicit split-leakage promise met by power and binomial weights of logarithmic degree and the promise Fφ≤KF_φ\le KFφ​≤K, they are Θ~(mK/ε)\widetildeΘ(\sqrt{mK}/\varepsilon)Θ(mK​/ε) and Θ~(mmin⁡{n2,K/ε2})\widetildeΘ(m\min\{n^2,K/\varepsilon^2\})Θ(mmin{n2,K/ε2}). The classical lower bounds hold against fully adaptive algorithms, and fewer than mmm such statistics cannot determine the positive-lifetime histogram. All bounds concern snapshot access; with an explicit update stream, near-linear full-barcode algorithms are known.
The edge connectivity of a simple graph is the least number of edges whose removal disconnects the graph. We study the quantum query complexity of computing the edge connectivity of a simple graph with nnn vertices and mmm edges in both the adjacency matrix and adjacency array models. For classical randomized algorithms, Ω(n2)\Omega(n^2)Ω(n2) and Ω(m)\Omega(m)Ω(m) lower bounds are known for these models, respectively, showing that the trivial algorithm is optimal in terms of query complexity for both cases. In contrast, we show upper bounds of O~(n3/2)\tilde O(n^{3/2})O~(n3/2) and O~(mn)\tilde O(\sqrt{mn})O~(mn​) on the quantum query complexity of computing edge connectivity in the adjacency matrix and adjacency array models, respectively. Our upper bound is tight up to logarithmic factors for the adjacency matrix model, while for the adjacency array model the best quantum query lower bound we know is Ω(n)\Omega(n)Ω(n). Our upper bounds follow by combining a lemma on the structure of near-minimum cuts due to Rubinstein, Schramm and Weinberg (ITCS 2018) with a quantum sparsification algorithm by Apers and de Wolf (FOCS 2020). For a weighted graph, instead of edge connectivity the relevant notion is the weight of a minimum cut, i.e. the minimum total weight of a set of edges whose removal disconnects the graph. For weighted graphs we show that in the worst case Ω(n2)\Omega(n^2)Ω(n2) queries can be needed to compute the weight of a minimum cut by a quantum algorithm in both the adjacency matrix and adjacency array models, thus no quantum speedup is possible in this case.
Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given mmm Bernoulli distributions with unknown biases p1,…,pmp_1,\dots,p_mp1​,…,pm​ and a gap parameter ΔΔΔ, the goal is to estimate the fraction ρρρ of \emph{positive} distributions (pi≥1/2+Δp_i\ge1/2+Δpi​≥1/2+Δ) to within additive error εεε. We prove an upper bound of O~ ⁣(ρΔε+1Δε)\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)O~(Δερ​​+Δε​1​) queries, achieving a quadratic speedup over the classical sample complexity. % of Θ(ρ/Δ2ε2)Θ(ρ/Δ^2ε^2)Θ(ρ/Δ2ε2). Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of Ω(ρ/(Δε))Ω(\sqrtρ/(Δε))Ω(ρ​/(Δε)) via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap Δ=Θ(1)Δ=Θ(1)Δ=Θ(1), which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to O~(ρε+1ε)\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)O~(ερ​​+ε​1​) and Ω(ρε)Ω(\frac{\sqrtρ}ε)Ω(ερ​​), thereby characterizing the query complexity of quantum counting with bounded-error oracles.
We study the minimum weight cycle problem (MWC) and the minimum weight triangle problem (MWT) in the quantum query model, for n-vertex graphs with integer edge weights in [M] given by their adjacency matrix. Roditty and Vassilevska Williams showed that the two problems are classically equivalent. We show that an exact minimum weight cycle of an undirected graph can be found with O~(n19/12)\tilde{O}(n^{19/12})O~(n19/12) queries, while Ω(n3/2)\Omega(n^{3/2})Ω(n3/2) queries are necessary. The algorithm learns only the n7/6n^{7/6}n7/6 lightest vertex pairs, uses quantum counting to locate weight thresholds above them, applies a strict form of the Moore bound to bound the optimum and the size of each weight class, and searches the classes for the few heavy edges of an optimal cycle with nested quantum walks. A simpler version gives O~(n5/3)\tilde{O}(n^{5/3})O~(n5/3) queries, and searching for fewer heavy edges trades queries for approximation, with a 2-approximation in O~(n8/5)\tilde{O}(n^{8/5})O~(n8/5) queries and a tight O(log⁡n)O(\log n)O(logn)-approximation in O~(n3/2)\tilde{O}(n^{3/2})O~(n3/2) queries. In contrast, MWT costs O(n9/7log⁡M)O(n^{9/7}\log M)O(n9/7logM) queries, so the classical equivalence becomes a polynomial separation. For cycles of constant length we give explicit exponents, such as O~(n125/83)\tilde{O}(n^{125/83})O~(n125/83) for the minimum weight 5-cycle, and we prove that deciding whether a graph has a k-cycle of total weight exactly zero requires Ω(n2−2/(⌊k/2⌋+1))\Omega(n^{2-2/(\lfloor k/2\rfloor+1)})Ω(n2−2/(⌊k/2⌋+1)) queries for every constant k≥4k\ge 4k≥4. Finally, non-adaptive learning graphs cannot beat n2n^2n2 for cycles of about log⁡n\log nlogn edges, and we conjecture that exact MWC on directed graphs requires n2−o(1)n^{2-o(1)}n2−o(1) queries.
We study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/2)Θ(n^{3/2})Θ(n3/2) bound for finding a maximum-out-degree vertex in an nnn-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an nnn-vertex undirected graph requires Θ(n3/2)Θ(n^{3/2})Θ(n3/2) quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum (k,n−k)(k,n-k)(k,n−k)-Cut, which asks for the largest cut with one side of size kkk. For every constant k≥1k\geq 1k≥1, we give an O(n2−1/(k+1))O(n^{2-1/(k+1)})O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)(k,n-k)(k,n−k)-Cut involving kkk-Graph Collision, which asks whether the marked vertices of a known graph contain a kkk-clique. For k≥3k\geq 3k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/23/23/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for kkk-Graph Collision, the reduction yields a lower bound matching our upper bound above.
Determining whether every trajectory of the linear system x˙=Ax\dot{x}=Axx˙=Ax converges to zero (or, equivalently, whether AAA is Hurwitz stable) is a fundamental problem in control theory. It arises, for example, in verifying the stability of feedback controllers and state observers, as well as of linearized dynamical models. We study the quantum query complexity of deciding whether a matrix A∈Cn×nA\in\mathbb{C}^{n\times n}A∈Cn×n is Hurwitz stable, given an exact normalized block-encoding of AAA. The query complexity is characterized in terms of the system dimension nnn and a supplied lower bound 0<ν≤ωA0<ν\leq ω_A0<ν≤ωA​ on the imaginary-axis distance ωA:=min⁡t∈Rσmin⁡(A−itI)ω_A:=\min_{t\in\mathbb{R}}σ_{\min}(A-\mathrm{i}tI)ωA​:=mint∈R​σmin​(A−itI), where σmin⁡(A)σ_{\min}(A)σmin​(A) is the smallest singular value of AAA. We prove a query-complexity lower bound of Ω(n/ν)Ω(\sqrt{n}/ν)Ω(n​/ν), which holds even when AAA is restricted to be real and diagonal. For general matrices with nonzero ωAω_AωA​, we encode an approximation of the right-half-plane spectral projector sign⁡+(A):=(I+sign⁡(A))/2\operatorname{sign}^+(A):=(I+\operatorname{sign}(A))/2sign+(A):=(I+sign(A))/2 as a block of a matrix inverse, where AAA is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a (β,b,1/(4n))(β,b,1/(4\sqrt{n}))(β,b,1/(4n​))-block-encoded projector matrix (like sign⁡+(A)\operatorname{sign}^+(A)sign+(A)) is zero or not; for constant success probability, it has complexity Θ(βn)Θ(β\sqrt{n})Θ(βn​). When the zero test is applied to specific approximations of sign⁡+(A)\operatorname{sign}^+(A)sign+(A), this yields an upper bound of O(nν−2log⁡(n/ν))O(\sqrt{n}ν^{-2}\log(\sqrt{n}/ν))O(n​ν−2log(n​/ν)) queries in the general case, and O(nν−1log⁡n)O(\sqrt{n}ν^{-1}\log n)O(n​ν−1logn) when AAA is Hermitian or normal. The latter upper bound matches the lower bound up to a logarithmic factor. Thus the dimension dependence of quantum Hurwitz testing is nearly optimal, while the remaining factor in the non-normal case isolates an open conditioning gap.
The minimum cut problem in an undirected and weighted graph GGG is to find the minimum total weight of a set of edges whose removal disconnects GGG. We completely characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model. If GGG has nnn vertices and edge weights at least 111 and at most τττ, we give a quantum algorithm to solve the minimum cut problem using O~(n3/2τ)\tilde O(n^{3/2}\sqrtτ)O~(n3/2τ​) queries and time. Moreover, for every integer 1≤τ≤n1 \le τ\le n1≤τ≤n we give an example of a graph GGG with edge weights 111 and τττ such that solving the minimum cut problem on GGG requires Ω(n3/2τ)Ω(n^{3/2}\sqrtτ)Ω(n3/2τ​) many queries to the adjacency matrix of GGG. These results contrast with the classical randomized case where Ω(n2)Ω(n^2)Ω(n2) queries to the adjacency matrix are needed in the worst case even to decide if an unweighted graph is connected or not. In the adjacency array model, when GGG has mmm edges the classical randomized complexity of the minimum cut problem is Θ~(m)\tilde Θ(m)Θ~(m). We show that the quantum query and time complexity are O~(mnτ)\tilde O(\sqrt{mnτ})O~(mnτ​) and O~(mnτ+n3/2)\tilde O(\sqrt{mnτ} + n^{3/2})O~(mnτ​+n3/2), respectively, where again the edge weights are between 111 and τττ. For dense graphs we give lower bounds on the quantum query complexity of Ω(n3/2)Ω(n^{3/2})Ω(n3/2) for τ>1τ> 1τ>1 and Ω(τn)Ω(τn)Ω(τn) for any 1≤τ≤n1 \leq τ\leq n1≤τ≤n. Our query algorithm uses a quantum algorithm for graph sparsification by Apers and de Wolf (FOCS 2020) and results on the structure of near-minimum cuts by Kawarabayashi and Thorup (STOC 2015) and Rubinstein, Schramm and Weinberg (ITCS 2018). Our time efficient implementation builds on Karger's tree packing technique (STOC 1996).