Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking

Peian Chen; Shiqi Zheng; Wenmin Han; Yukun Wang

REVIEW 4 major objections 4 minor 59 references

Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking

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

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

Pith's one-line read A Grover-oracle redesign with a size-tracking register finds a maximum clique in O(sqrt(2^n)) iterations and O(1) measurements.

desk verdict The Turán-bounds encoding idea is worth a look, but the claimed speedup is an accounting artifact—the QPDE stage is a brute-force clique counter whose exponential cost is excluded from the headline. read the letter →

arxiv 2509.01261 v1 pith:IRCT2IRJ submitted 2025-09-01 quant-ph

Wenmin Han , Shiqi Zheng , Peian Chen , Yukun Wang This is my paper · ORCID

classification quant-ph MSC 68Q1281P68

keywords maximumcliqueproblemGrover'salgorithmquantumsearchoracledesignTurán'stheoremNP-hardcombinatorialoptimizationcircuitglobalvariableencoding

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes a quantum circuit that solves the maximum clique problem—finding the largest subgraph in which every pair of vertices is connected—using Grover search in O(sqrt(2^n)) iterations and O(1) measurements. Existing Grover-based solvers treat the clique size as a fixed parameter k: they run a full search for each k, measure, and increment k until the maximum is found, costing O(n sqrt(2^n)) iterations and O(n) measurements. The proposed fix is a preprocessing stage that derives the clique-size range from the graph's edge count, then uses a quantum counter to detect the exact maximum size and store it in an auxiliary register before search begins. The Grover oracle then checks both cliquehood and size match in one circuit, so amplitude amplification targets only maximum cliques. If the construction scales as claimed, this removes the main bottleneck that has kept Grover-based maximum-clique solvers at O(n) measurement rounds.

What carries the argument

The load-bearing object is the |info> register produced by the Quantum Pre-Detection and Encoding stage: it holds the largest clique size r in unary and plays the role of a dynamic global variable inside the oracle. The oracle itself is a three-part circuit: a Cliques Detector that evaluates the n(n-1)/2 pairwise-edge clauses of the clique definition with controlled gates; an MCP Detector that duplicates the candidate vertex string, sorts it with Fredkin gates, and compares the sorted string to |info> via XNOR gates; and the phase-inversion target that is flipped only when both cliquehood and the size match. The claim that one measurement suffices rests on this size comparison being made coh

What would settle it

Run the full circuit on a five-vertex graph with a single triangle and C(5,3)=10 candidate triples: if the pre-detection counter cannot handle the non-power-of-two carry structure, the |info> register will not encode size 3; alternatively, check on a graph with two maximum cliques whether both marked states are returned with one measurement. Either experiment would settle whether the O(1)-measurement claim survives beyond the four-vertex example.

Watch

Extended reading notes

Core claim

The paper's central claim is that maximum clique can be solved with O(sqrt(2^n)) Grover iterations and O(1) measurements by making the clique size a global variable inside the quantum circuit rather than an external parameter. A Quantum Pre-Detection and Encoding stage uses the contrapositive of Turán's theorem to get a lower bound on the maximum clique size and the complete-graph edge count to get an upper bound, narrowing the candidate range; a reversible counter circuit then checks, for each size r in that range, whether any r-vertex subset forms a clique, and writes the largest such r into an |info> register. In the main Grover iteration, a Cliques Detector marks vertex subsets that are

Load-bearing premise

The load-bearing premise is that the preprocessing counter can determine the exact maximum clique size for arbitrary n without measurement and that the sorted vertex string aligns with the encoded size string for XNOR comparison; the paper demonstrates only a four-input counter and a four-vertex example.

Editorial extensions

If this is right

If correct, maximum-clique search on an n-vertex graph needs about (pi/4) sqrt(2^n/M) Grover iterations and one final measurement, independent of the clique-size guessing loop.
The static parameter k used by prior Grover-based maximum-clique solvers is replaced by a size register computed once, so the same oracle can be reused without re-engineering per k.
The per-iteration oracle gate count stays O(n^2), and the total circuit width is O(n^2); the one-time preprocessing contributes O(n^{3/2} 2^n) gates to the total, which the paper counts separately.
Success probability remains at the usual Grover level: the four-vertex simulation reports roughly 96% success, comparable to earlier schemes, while using fewer iterations and measurements.
For graphs whose maximum clique size is far from both the Turán lower bound and the complete-graph upper bound, preprocessing probes fewer sizes r, reducing the one-time preprocessing gate cost.

Reading between the lines

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

The claimed O(1) measurement count presumes the number of marked states M is known or well estimated for choosing the Grover iteration count; if M is unknown, a quantum counting subroutine would have to be added, which the paper does not include.
The same 'encode a global size bound into an auxiliary register' pattern could be applied to other subset-search NP-hard problems (maximum independent set, densest k-subgraph) whenever a theorem supplies a size interval.
A fair end-to-end cost comparison should include the classical work of computing the edge count e used to set the Turán bounds; the paper treats this as free input, which is reasonable for static graphs but not for black-box oracles.
The four-vertex demonstration does not exercise the counter's carry logic for values of C(n,r) that are not powers of two; a five-vertex triangle-only graph would put the generalization to the test.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know the headline result—O(sqrt(2^n)) Grover iterations and O(1) measurements for maximum clique—doesn't survive contact with the paper's own equations. The Quantum Pre-Detection and Encoding (QPDE) stage, which the abstract omits from the complexity, is a deterministic enumeration of all n-choose-r vertex subsets for every r in the Turán-derived range, with each subset checked by an MCT gate on the edge qubits. Since the edge register is in a basis state, this is just classical brute force, and the paper's own Eq. (9) gives O(n^3 2^n) gates for it. That term dwarfs the Grover-stage cost and already solves the problem before the search starts. The claimed n-fold improvement over prior Grover MCP methods is obtained by not counting this work.

That said, the paper isn't empty. The idea of using Turán's theorem to bound the clique-size range, and encoding that size in a global register to avoid iterating over k, is a legitimate extension of prior work. The oracle design is described in detail, with a full 4-vertex circuit and a Qiskit simulation, and the authors honestly list the QPDE cost in their total-gate column. So the pieces are there, but the central claim doesn't hold.

The soft spots beyond the accounting: there's an internal contradiction in the sorting step. Section 3.1.3 says sorting |101> gives |110> (1s to the MSB), then Section 3.2 says the 1s are shifted to the most significant positions, but the XNOR comparison with the one-hot info register only makes sense if the 1s are sorted to the LSB. As written, the oracle won't mark the right states. The generalized quantum counter is only demonstrated for four inputs; scaling to C(n,r) is plausible but unproven. And the Grover iteration count assumes a known number of solutions M, which the algorithm never estimates; running a fixed sqrt(2^n) iterations is not a correct procedure for unknown M.

Overall: this is a paper with a sensible fragment and a fatal complexity flaw. It's worth a serious referee to carefully confirm the QPDE cost and the oracle inconsistency, but I wouldn't cite it as a working algorithm. For a reading group, it's a nice case study in how to read a complexity claim.

My recommendation: send to peer review if you want the record to show the flaw; otherwise desk reject. If it's reviewed, the authors need major revisions or a rewrite.

Referee Report

4 major / 4 minor

Summary. The paper proposes a Grover-based algorithm for the maximum clique problem (MCP). It adds a "Quantum Pre-Detection and Encoding" (QPDE) stage that determines the size of the maximum clique and encodes it into an ancilla register; a Grover oracle then marks vertex subsets that are cliques of that size. The authors claim that the method finds all maximum cliques with O(sqrt(2^n)) Grover iterations and O(1) measurements, an n-fold improvement over previous Grover-based MCP solvers. A four-vertex example and Qiskit simulation are presented, along with asymptotic resource comparisons in Table 1.

Significance. If the central claim were correct, the algorithm would be a significant advance for Grover-based exact MCP solving, reducing both iteration count and measurement count by a factor of n. The paper is also transparent in reporting the QPDE gate count and in providing a concrete circuit and Qiskit demonstration. However, the transparency exposes the central problem: the QPDE stage, by the paper's own Eq. (9), costs O(n^3 2^n) gates and already performs a brute-force enumeration of all vertex subsets to determine the maximum clique size. Excluding this cost from the headline complexity makes the claimed improvement an accounting artifact. In addition, the oracle design has an unresolved ordering inconsistency between the sorting stage and the info-register encoding, and the generalized quantum counter is only supported by a 4-input example. Because these issues affect the correctness and the validity of the complexity comparison, the paper does not establish its main claims.

major comments (4)

[Section 3.1.1(b), Algorithm 1 lines 1-14; Eq. (9); Section 5] The QPDE stage is a deterministic reversible enumeration of every C(n,i) vertex subset for each i in the Turán-derived range, checking cliquehood with MCT gates and counting with a quantum counter. This is a brute-force solution of MCP before Grover begins. The paper's own Eq. (9) gives Np = O(n^3 2^n), and Section 5 admits this is significant. This term dominates the O(n^2 sqrt(2^n)) Grover stage and makes the total gate complexity O(n^2 2^{n/2} + n^3 2^n), as Table 1 itself reports. Therefore the abstract's claim of "O(sqrt(2^n)) Grover iterations and O(1) measurements" and the claimed n-fold improvement over prior methods are obtained only by moving the hard work into excluded preprocessing. This is a load-bearing accounting issue, not a presentation issue.
[Section 3.1.3 and Section 3.2] The sorting operation and the info-register encoding are mutually inconsistent. Section 3.1.3 says sorting moves all |1> qubits 'to the end' and gives the example |101> -> |110>, which actually moves the 1s to the most significant positions. Section 3.2 states that after sorting, 'the |1> states are shifted to the most significant positions.' If that convention is used, the maximum clique state |1011> for the four-vertex example becomes |1110>, which does not XNOR-match the info state |0111> used to mark the maximum clique. If instead the intended convention moves 1s to the least significant positions, then the example |101> -> |110> is wrong. Either way, the oracle's marking condition is not well-defined, and the correctness of the simulation in Fig. 10 does not resolve the ambiguity.
[Section 3.1.1(b), Fig. 5] The quantum counter is load-bearing for QPDE: it must tally up to C(n,r) cliques and set the info-register bit exactly when the count is nonzero. The paper shows only a four-input example and asserts generalization to arbitrary n and r. No construction, proof, or uncompute specification is given for the general counter with ceil(log2 C(n,r)) + 1 counting qubits. Without this generalization, the QPDE stage cannot be assumed to determine the exact maximum clique size, and every downstream claim about the info register fails.
[Sections 2.2.4 and 4.2; Algorithm 1] The paper fixes the number of Grover iterations at O(sqrt(2^n)) without accounting for the number M of marked states (maximum cliques). Standard Grover requires approximately (pi/4) sqrt(N/M) iterations; if M is large, a fixed O(sqrt(2^n)) run over-rotates and reduces success probability. The paper does not estimate M or use quantum counting/adaptive methods. Additionally, the abstract's promise to 'deterministically retrieve all maximum cliques' is inconsistent with the algorithm's own description in Section 2.2.4, where a single measurement collapses to one target state. These issues affect the claimed O(1) measurements and the generality of the result.

minor comments (4)

[Abstract] The notation O(sqrt(2^n)) is ambiguous; it should be written O(2^{n/2}) to avoid confusion with O((sqrt(2))^n) or O(sqrt(2^n)).
[Section 3.1.1(a)] The info-register encoding is unclear: the text says each qubit |x_i> corresponds to a clique size i+1, but the example state |01111> for max clique size 4 in a five-vertex graph is not a one-hot encoding and is not explained. The distinction between 'number of ones' and 'position of the highest one' should be stated precisely.
[Eq. (5) and surrounding text] The gate-count derivations contain missing parentheses and inconsistent approximation signs (e.g., the line '2 * sum 2(i(i-1)/2 -1) * C(n,i)'). This makes Eqs. (5)-(9) difficult to verify. Please rewrite with clear asymptotic bounds and explicit definitions.
[Section 3.2] The text 'the quantum state |x3x2x1x0> is initialized as |0a11>' appears to contain a typo; presumably |0011> or |0?11> was intended. The subsequent evolution to |0111> should be explained step by step.

Circularity Check

1 steps flagged · score 6.0 of 10

The claimed O(√2^n)-iteration, O(1)-measurement speedup is an accounting artifact: the maximum clique size is precomputed by exhaustive enumeration in QPDE and then used as the Grover oracle's target condition.

fitted input called prediction [Section 3.1.1(b) 'Quantum MCP Size Detection'; Algorithm 1 lines 1-14; Eq. (9); Section 5]
"Finally, if the counter is non-zero, it indicates the presence of an r-clique in graph G. In this case, the qubit |x_{r-1}> is set to |1> ... the complexity of the number of quantum gates required in the Quantum Pre-Detection and Encoding stage is determined to be O(n^3/2 2^n)."

The |x> (info) register that the MCP Detector compares against is not an external or cheaply obtained global variable; it is computed by the QPDE stage, which enumerates all C(n,i) i-vertex subsets for every i in the Turán range, checks each with MCT gates over edge qubits, and counts cliques. This is a brute-force solution of the maximum-clique decision problem before Grover starts. The subsequent oracle marks a vertex set only if its sorted string XNOR-matches this precomputed size, so the 'maximum clique' target is defined in terms of the already-computed answer. The advertised O(√2^n) iterations/O(1) measurements count only the Grover loop and exclude Eq. (9)'s O(n^3/2 2^n) QPDE gate count; the n-fold improvement therefore follows by moving the exponential work out of the measured metr

full rationale

The only genuine circularity is in the complexity accounting: Algorithm 1's first stage (QPDE) solves the hard part—determining the exact maximum clique size—by exhaustive quantum counter circuits over all subsets, and then the Grover oracle is constructed to accept exactly cliques of that precomputed size. The paper's own Eq. (9) and Section 5 concede the QPDE stage has O(n^3/2 2^n) gate complexity and 'contributes significantly to the total complexity,' yet the abstract and conclusion present O(√2^n) Grover iterations and O(1) measurements as 'the entire process.' This is a partial reduction by construction: the target of the search is defined by the output of the preprocessing. The Grover iteration bound itself is standard and not circular; there is no self-citation or imported uniqueness theorem. The remaining issues (generalization of the counter beyond 4 inputs, the sorting/info alignment inconsistency, unknown M in Grover iteration count) are correctness/complexity concerns rather than circularity and do not change this verdict.

Assumptions & free parameters 1 free parameters · 7 assumptions · 0 invented entities

The algorithm relies on Turan's theorem and the edge-count bound for complete graphs to set the probe range (Section 3.1.1(a)), and on the standard Grover amplitude-amplification framework. The paper also implicitly assumes that a reversible counter can be built for arbitrary C(n,r) subsets and that the sorted vertex string matches the info-register encoding; these assumptions are not established by the provided 4-input example and inconsistent ordering statements. No free parameters are fitted to data, but the Grover iteration count is chosen as pi/4 sqrt(2^n) without accounting for the unknown number of solutions M.

free parameters (1)

Number of Grover iterations t = pi/4 * sqrt(2^n), assuming M=1
The optimal iteration count for Grover search depends on the unknown number M of maximum cliques. The paper fixes t = pi/4 sqrt(2^n), which is only correct for M=1. For graphs with multiple maximum cliques, this choice overshoots and lowers success probability, so the O(1) measurement claim fails without additional handling.

assumptions (7)

standard math Turan's theorem: a graph with n vertices and e edges avoiding K_{r+1} satisfies e <= (r-1)/r * n^2/2
Used in Section 3.1.1(a) to derive the lower bound l1 on the maximum clique size. The theorem itself is standard and accepted.
standard math Complete graph edge bound: a clique of size r must have r(r-1)/2 edges
Used in Section 3.1.1(a) to derive the upper bound l2. This is an elementary combinatorial fact.
standard math Grover's algorithm with an oracle that marks exactly the maximum cliques yields an O(sqrt(2^n)) iteration search when k is known
The paper's central complexity claim relies on the standard amplitude amplification bound. This is accepted, but the paper does not justify the iteration count when the number of solutions M is unknown.
ad hoc to paper A quantum counter circuit can be generalized from the 4-input example to count existence of r-cliques for arbitrary n and r
Section 3.1.1(b) and Fig.5 illustrate a counter for C(n,r)=4; the paper provides no construction or proof for arbitrary combinatorial numbers, yet the QPDE stage depends on it.
ad hoc to paper The sorted vertex string and the info register use compatible bit ordering for XNOR comparison
Section 3.1.3 requires comparing the sorted clique state with |x0...x_{n-1}>; the paper's two descriptions of sorting direction ('|101> to |110>' vs 'shifted to the most significant positions') are inconsistent, so this alignment is an unproven assumption.
domain assumption The QPDE stage can be executed coherently and its result loaded into the ancillary registers without destroying the vertex superposition
The algorithm requires the maximum clique size register to be available during Grover iteration. The paper does not specify how uncomputation and register reuse work without measurement, which is essential for a coherent Grover search.
ad hoc to paper The number of maximum cliques M is such that pi/4 sqrt(2^n) iterations gives high success probability
The iteration count is chosen as if M=1; no fixed-point or counting method is used, so the claimed single-measurement success requires an unstated assumption on M.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking." pith.science (2026). https://pith.science/paper/IRCT2IRJ

@misc{pith2026250901261,
  author       = {Pith},
  title        = {Pith review of: Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IRCT2IRJ}},
  note         = {Machine review of arXiv:2509.01261}
}

abstract

The maximum clique problem (MCP) is to find the largest complete subgraph in an undirected graph, that is, the subgraph in which there are edges between every two different vertices. It is an NP-Hard problem with wide applications, including bioinformatics, social networks, data mining, and other fields. This paper proposes an improved algorithm that dynamically tracks the maximum clique size by encoding prior constraints on the vertex count-derived from Tur\'an's theorem and complete graph properties-into global variables through quantum circuit pre-detection. The algorithm further synergizes with Grover's search to optimize the solution space. Our auxiliary-qubit encoding scheme dynamically tracks clique sizes during quantum search, eliminating iterative measurements, achieving MCP solution with $O\left(\sqrt{2^n}\right)$ Grover iterations and $O(1)$ measurements. This represents an $\boldsymbol{n}$-fold improvement over state-of-the-art Grover-based methods, which require $O(n\sqrt{2^n})$ iterations and $O(n)$ measurements for $n$-vertex graphs. We validate algorithmic correctness through simulations on IBM's Qiskit platform and benchmark qubit/gate efficiency against existing Grover-based MCP solvers.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 53 canonical work pages

[1]

Karp, R. M. Reducibility among combinatorial problems , 219–241. Series in Applied Mathematical Sciences (Springer, 2009)

work page 2009
[2]

Pardalos, P. M. & Xue, J. The maximum clique problem. Journal of global Optimization 4, 301–328 (1994)

work page 1994
[3]

M., Budinich, M., Pardalos, P

Bomze, I. M., Budinich, M., Pardalos, P. M. & Pelillo, M. The maximum clique problem, 1–74 (Springer, 1999)

work page 1999
[4]

D., Phillips, C

Eblen, J. D., Phillips, C. A., Rogers, G. L. & Langston, M. A. The maxi- mum clique enumeration problem: algorithms, applications, and implementations. BMC bioinformatics 13, S5 (2012)

work page 2012
[5]

Adraoui, M., Retbi, A., Idrissi, M. K. & Bennani, S. Maximal cliques based method for detecting and evaluating learning communities in social networks. Future Generation Computer Systems 126, 1–14 (2022)

work page 2022
[6]

& Matsunaga, T

Tomita, E., Akutsu, T. & Matsunaga, T. Efficient algorithms for finding maximum and maximal cliques: Effective tools for bioinformatics (IntechOpen, 2011)

work page 2011
[7]

& Yip, J

Wang, L., Zhou, L., Lu, J. & Yip, J. An order-clique-based approach for mining maximal co-locations. Information Sciences 179, 3370–3382 (2009)

work page 2009
[8]

Douik, A., Dahrouj, H., Al-Naffouri, T. Y. & Alouini, M.-S. A tutorial on clique problems in communications and signal processing. Proceedings of the IEEE 108, 583–608 (2020)

work page 2020

Show all 59 references

[9]

& Pardalos, P

Carraghan, R. & Pardalos, P. M. An exact algorithm for the maximum clique problem. Operations Research Letters 9, 375–382 (1990)

1990
[10]

& Yin, M

Wang, Y., Cai, S. & Yin, M. AAAI Press (ed.) Two efficient local search algo- rithms for maximum weight clique problem . (ed.AAAI Press) Proceedings of the AAAI Conference on Artificial Intelligence , 805–811 (AAAI Press, Phoenix, AZ, USA, 2016)

2016
[11]

& Hao, J.-K

Wu, Q. & Hao, J.-K. A review on algorithms for maximum clique problems. European Journal of Operational Research 242, 693–709 (2015)

2015
[12]

& Loukas, A

Karalias, N. & Loukas, A. Erdos goes neural: an unsupervised learning frame- work for combinatorial optimization on graphs. Advances in Neural Information Processing Systems 33, 6659–6672 (2020)

2020
[13]

& Zavalnij, B

Marino, R., Buffoni, L. & Zavalnij, B. A short review on novel approaches for maximum clique problem: from classical algorithms to graph neural networks and quantum algorithms. arXiv preprint arXiv:2403.09742 (2024). 25

2024 arXiv
[14]

Rahman, M

Tomita, E. Rahman, M. S. & Nakano, S.-i. (eds) Efficient algorithms for find- ing maximum and maximal cliques and their applications . (eds Rahman, M. S. & Nakano, S.-i.) International Workshop on Algorithms and Computation , Vol. 10167 of Lecture Notes in Computer Science , 3...

2017
[15]

Clique is hard to approximate within n1

Johan, H. Clique is hard to approximate within n1. Acta Mathematica 182, 105–142 (1999)

1999
[16]

Nielsen, M. A. & Chuang, I. L. Quantum computation and quantum information (Cambridge university press, 2010)

2010
[17]

& Lidar, D

Albash, T. & Lidar, D. A. Adiabatic quantum computation. Reviews of Modern Physics 90, 015002 (2018)

2018
[18]

Review on quantum communication and quantum computation

Chen, J. Review on quantum communication and quantum computation. Journal of Physics: Conference Series 1865, 022008 (2021)

2021
[19]

M., Farhi, E., Goldstone, J

Childs, A. M., Farhi, E., Goldstone, J. & Gutmann, S. Finding cliques by quantum adiabatic evolution. arXiv preprint quant-ph/0012104 (2000)

2000 arXiv
[20]

& Djidjev, H

Pelofske, E., Hahn, G. & Djidjev, H. Feld, S. & Linnhoff-Popien, C. (eds) Solving large maximum clique problems on a quantum annealer . (eds Feld, S. & Linnhoff- Popien, C.) Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Proceedings 1, V...

2019
[21]

Ha, H. P. N., Nguyen, V. H. & Ta, A. S. Nguyen, S., Osman, I. H., Ernst, A. & Guedria, W. (eds) Solving edge-weighted maximum clique problem with dca warm- start quantum approximate optimization algorithm. (eds Nguyen, S., Osman, I. H., Ernst, A. & Guedria, W.) Metaheuristics ...

2024
[22]

& Kumar, N

Jain, N., Coyle, B., Kashefi, E. & Kumar, N. Graph neural network initialisation of quantum approximate optimisation. Quantum 6, 861 (2022)

2022
[23]

Li, L. et al. An efficient quantum proactive incremental learning algorithm. Science China Physics, Mechanics & Astronomy 68, 210313 (2025)

2025
[24]

Chang, W.-L. et al. Quantum speedup in solving the maximal-clique problem. Physical Review A 97, 032344 (2018)

2018
[25]

& Wang, Y

Zhang, H., Wang, S., Liu, X., Shen, Y. & Wang, Y. Quantum algorithm for minimum dominating set problem with circuit design. Chinese Physics B 33, 020310 (2024). 26

2024
[26]

A grover search-based algorithm for the list coloring problem

Mukherjee, S. A grover search-based algorithm for the list coloring problem. IEEE Transactions on Quantum Engineering 3, 1–8 (2022)

2022
[27]

& Perkowski, M

Wang, Y. & Perkowski, M. Kameyama, M. & Eklund, P. (eds) Improved complexity of quantum oracles for ternary grover algorithm for graph coloring . (eds Kameyama, M. & Eklund, P.) 2011 41st IEEE International Symposium on Multiple-Valued Logic , ISMVL 2011 Proceedings, 294–301 (...

2011
[28]

Saha, A., Chongder, A., Mandal, S. B. & Chakrabarti, A. Lamar, S. K., Yadav, V. P. & Mishra, S. (eds) Synthesis of vertex coloring problem using grover’s algorithm. (eds Lamar, S. K., Yadav, V. P. & Mishra, S.) 2015 IEEE Inter- national Symposium on Nanoelectronic and Informat...

2015
[29]

& Shivakumar, M

Vidya Raj, C. & Shivakumar, M. Shi, Z. & Shimazu, A. (eds) Applying quan- tum algorithm to speed up the solution of hamiltonian cycle problems . (eds Shi, Z. & Shimazu, A.) International Conference on Intelligent Information Process- ing, IFIP International Federation for Info...

2006
[30]

Kristofor Gibson, C.-Y

Jiang, J.-R. Kristofor Gibson, C.-Y. C. (ed.) Quantum circuit based on grover algorithm to solve hamiltonian cycle problem . (ed.Kristofor Gibson, C.-Y. C.) 2022 IEEE 4th Eurasia Conference on IOT, Communication and Engineering (ECICE), ECICE Proceedings, 364–367 (IEEE, Yunlin...

2022
[31]

& Kao, T.-H

Jiang, J.-R. & Kao, T.-H. Kristofor Gibson, C.-Y. C. (ed.) Solving hamilto- nian cycle problem with grover’s algorithm using novel quantum circuit designs . (ed.Kristofor Gibson, C.-Y. C.) 2023 IEEE 5th Eurasia Conference on IOT, Communication and Engineering (ECICE), ECICE Pr...

2023
[32]

Diasa, M. G. & Zateskoa, L. M. Douglas Wildgrube Bertol, M. R., Andr’e Luiz Brun (ed.) Grover’s quantum algorithm and the maximum clique problem . (ed.Douglas Wildgrube Bertol, M. R., Andr’e Luiz Brun) Proceedings of the 2021 Workshop de Pesquisa em Computa¸ c˜ ao dos Campos G...

2021
[33]

Quantum algorithm for finding a maximum clique in an undirected graph

Boji´ c, A. Quantum algorithm for finding a maximum clique in an undirected graph. Journal of information and organizational sciences 36, 91–98 (2012)

2012
[34]

& Chakrabarti, A

Sanyal, A., Saha, A., Saha, B. & Chakrabarti, A. Circuit synthesis of maximum clique problem using combinatorial approach of classical-quantum hybrid model. arXiv preprint arXiv:2004.10596 (2020)

2004 arXiv
[35]

& L´ opez, S

Haverly, A. & L´ opez, S. Bah´ ar, R. I., Henkel, J. & Zhang, W. (eds)Implementa- tion of grover’s algorithm to solve the maximum clique problem . (eds Bah´ ar, R. I., 27 Henkel, J. & Zhang, W.) 2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI) , ISVLSI Proceedings,...

2021
[36]

Dias, M. G. Algoritmos quˆ anticos e o problema da clique m´ axima em grafos . Master’s thesis, Universidade Tecnol´ ogica Federal do Paran´ a (2022)

2022
[37]

Grover, L. K. Miller, G. L. (ed.) A fast quantum mechanical algorithm for database search. (ed.Miller, G. L.) Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , STOC ’96, 212–219 (ACM, Philadelphia, PA, USA, 1996)

1996
[38]

& Hoyer, P

Durr, C. & Hoyer, P. A quantum algorithm for finding the minimum. arXiv preprint quant-ph/9607014 (1996)

1996 arXiv
[39]

& Tapp, A

Brassard, G., Høyer, P. & Tapp, A. Larsen, K. G., Skyum, S. & Winskel, G. (eds) Quantum counting. (eds Larsen, K. G., Skyum, S. & Winskel, G.) Interna- tional Colloquium on Automata, Languages, and Programming , Lecture Notes in Computer Science, 820–831 (Springer, Aalborg, De...

1998
[40]

Simpler quantum counting

Wie, C.-R. Simpler quantum counting. arXiv preprint arXiv:1907.08119 (2019)

1907 arXiv
[41]

& Rall, P

Aaronson, S. & Rall, P. Fineman, J. T. & Mitzenmacher, M. (eds) Quantum approximate counting, simplified. (eds Fineman, J. T. & Mitzenmacher, M.) Sym- posium on simplicity in algorithms , Proceedings of the Symposium on Simplicity in Algorithms, 24–32 (SIAM, Salt Lake City, UT...

2020
[42]

& Konno, N

Inui, N., Konishi, Y. & Konno, N. Localization of two-dimensional quantum walks. Physical Review A 69, 052323 (2004)

2004
[43]

Giri, P. R. Quantum walk search by grover search on coin space. The European Physical Journal D 77, 175 (2023)

2023
[44]

& Steinwandt, R

Grassl, M., Langenberg, B., Roetteler, M. & Steinwandt, R. Takagi, T. (ed.) Applying grover’s algorithm to aes: quantum resource estimates . (ed.Takagi, T.) International Workshop on Post-Quantum Cryptography , Lecture Notes in Computer Science, 29–43 (Springer, Fukuoka, Japan, 2016)

2016
[45]

Quantum secret-sharing protocol based on grover’s algorithm

Hsu, L.-Y. Quantum secret-sharing protocol based on grover’s algorithm. Physical Review A 68, 022306 (2003)

2003
[46]

Y., Chaari, W

Cherif, M. Y., Chaari, W. L. & Driss, O. B. Atri, M., Chaari, L. & Loseri, V. (eds) A quantum machine learning approach using an optimized application of grover’s algorithm. (eds Atri, M., Chaari, L. & Loseri, V.) 2023 IEEE Afro-Mediterranean Conference on Artificial Intellige...

2023
[47]

& Singh, V

Chakrabarty, I., Khan, S. & Singh, V. Dynamic grover search: Applications in recommendation systems and optimization problems. Quantum Information Processing 16, 153 (2017)

2017
[48]

& Lidar, D

Biham, E., Biham, O., Biron, D., Grassl, M. & Lidar, D. A. Grover’s quantum search algorithm for an arbitrary initial amplitude distribution. Physical Review A 60, 2742 (1999)

1999
[49]

& Kenigsberg, D

Biham, E. & Kenigsberg, D. Grover’s quantum search algorithm for an arbitrary initial mixed state. Physical Review A 66, 062301 (2002)

2002
[50]

Grover algorithm with zero theoretical failure rate

Long, G.-L. Grover algorithm with zero theoretical failure rate. Physical Review A 64, 022307 (2001)

2001
[51]

& Tapp, A

Brassard, G., Hoyer, P., Mosca, M. & Tapp, A. Quantum amplitude amplification and estimation. arXiv preprint quant-ph/0005055 (2000)

2000 arXiv
[52]

Arbitrary phases in quantum amplitude amplification

Høyer, P. Arbitrary phases in quantum amplitude amplification. Physical Review A 62, 052304 (2000)

2000
[53]

& Tessler, L

Byrnes, T., Forster, G. & Tessler, L. Generalized grover’s algorithm for multiple phase inversion states. Physical review letters 120, 060501 (2018)

2018
[54]

Mehri-Dehnavi, H. et al. A modified quantum search algorithm. International Journal of Theoretical Physics 57, 3668–3681 (2018)

2018
[55]

& Tapp, A

Boyer, M., Brassard, G., Høyer, P. & Tapp, A. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics 46, 493–505 (1998)

1998
[56]

Grover, L. K. Fixed-point quantum search. Physical Review Letters 95, 150501 (2005)

2005
[57]

Graph Theory and Additive Combinatorics: Exploring Structure and Randomness (Cambridge University Press, 2023)

Zhao, Y. Graph Theory and Additive Combinatorics: Exploring Structure and Randomness (Cambridge University Press, 2023)

2023
[58]

Weisstein, E. W. Complete graph. https://mathworld.wolfram.com/ (2001)

2001
[59]

Smolin, J. A. & DiVincenzo, D. P. Five two-bit quantum gates are sufficient to implement the quantum fredkin gate. Physical Review A 53, 2855 (1996). 29

1996

Pith tools

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

[1] [1]

Karp, R. M. Reducibility among combinatorial problems , 219–241. Series in Applied Mathematical Sciences (Springer, 2009)

work page 2009

[2] [2]

Pardalos, P. M. & Xue, J. The maximum clique problem. Journal of global Optimization 4, 301–328 (1994)

work page 1994

[3] [3]

M., Budinich, M., Pardalos, P

Bomze, I. M., Budinich, M., Pardalos, P. M. & Pelillo, M. The maximum clique problem, 1–74 (Springer, 1999)

work page 1999

[4] [4]

D., Phillips, C

Eblen, J. D., Phillips, C. A., Rogers, G. L. & Langston, M. A. The maxi- mum clique enumeration problem: algorithms, applications, and implementations. BMC bioinformatics 13, S5 (2012)

work page 2012

[5] [5]

Adraoui, M., Retbi, A., Idrissi, M. K. & Bennani, S. Maximal cliques based method for detecting and evaluating learning communities in social networks. Future Generation Computer Systems 126, 1–14 (2022)

work page 2022

[6] [6]

& Matsunaga, T

Tomita, E., Akutsu, T. & Matsunaga, T. Efficient algorithms for finding maximum and maximal cliques: Effective tools for bioinformatics (IntechOpen, 2011)

work page 2011

[7] [7]

& Yip, J

Wang, L., Zhou, L., Lu, J. & Yip, J. An order-clique-based approach for mining maximal co-locations. Information Sciences 179, 3370–3382 (2009)

work page 2009

[8] [8]

Douik, A., Dahrouj, H., Al-Naffouri, T. Y. & Alouini, M.-S. A tutorial on clique problems in communications and signal processing. Proceedings of the IEEE 108, 583–608 (2020)

work page 2020