{"id":"c601cd8c-a4bf-4677-aba1-7f265a04bb14","arxiv_id":"1908.07943","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A quantum min/max search that uses exact Grover-Long search instead of probabilistic Grover search, with oracle circuit simplifications and small IBM Q demonstrations.","lead":"The authors present QUMMSA, a quantum minimum and maximum search algorithm that replaces the probabilistic Grover search inside the Dürr-Høyer algorithm with the exact Grover-Long search, and they give circuit simplifications for the oracle. The method reaches near-100% success only when the fraction of marked items is known or accurately estimated, which is the main limitation of the claimed improvement.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Near-100% success depends on an accurate M/N estimate, but the implemented estimator M̃=d0+1, Ñ=2^n is unjustified for sparse databases and the sampling refinement is not integrated or proven.","rationale":"The central claim of the paper is that QUMMSA improves DHA by replacing QESA with Grover-Long search and thereby achieves near-100% success. Grover-Long is exact only when its phase parameter is derived from the true marked fraction M/N. The paper's concrete way of obtaining that fraction, used in both the 2-qubit experiment and the 6-qubit Titanic simulation, is the uniform-code-space assumption M̃=d0+1, Ñ=2^n. This assumption is explicitly at odds with the paper's own hypothesis (6), which permits empty basis states, and with the Titanic data itself: only 36 of 64 code words are occupied. The paper acknowledges in Section 5.1 that the failure rate increases when M̃/Ñ differs from M/N, but the proposed remedy, sampling the empirical distribution, is not integrated into Algorithm 1 and lacks any proof that the estimated cumulative distribution yields a Grover-Long failure rate within a claimed bound. This is the load-bearing weakness because the near-100% success guarantee, the lower failure rate in Fig. 12, and the complexity advantage in Fig. 15 all depend on it. The reader's weakest_assumption identifies the same issue, so no verdict change is needed; CONDITIONAL remains appropriate. A further sign of trouble is the contradictory success criterion in Section 4.2, where the minimum search is reported as successful when d1 ≥ d0; using the wrong event undermines the experimental validation and should be corrected in any revision.","tokens_in":14522,"tokens_out":5663,"duration_ms":52391,"concrete_test":"Using the Appendix B Titanic data and the paper's own Eq. (C7), compute the Grover-Long failure probability for each possible threshold d0 with the default estimator (M̃=d0+1, Ñ=2^6=64) and with true N=36, M=number of stored ages ≤ d0; count a search as successful only when the measured d1 < d0. If the default estimator yields a failure probability above a few percent for any d0, or if the success condition in Section 4.2 is inverted, the near-100% claim is unsupported. A second check is to repeat the same computation using the Section 5.1 sampling estimator with h from Eq. (14) and verify whether the resulting failure rate is actually bounded by the claimed level.","verdict_should_be":"UNCHANGED","load_bearing_attack":"QUMMSA's advertised 'successful probability close to 100%' (abstract and Section 2) is obtained only when the Grover-Long parameters are set from the true marked fraction M/N. The implemented algorithm, however, sets M̃=d0+1 and Ñ=2^n (Section 4.2, before Fig. 11). This is correct only when the database occupies every code state in [0,2^n−1] and is close to uniform. Hypothesis (6) explicitly allows unoccupied basis states, and the Titanic excerpt stores only 36 distinct values in a 64-state code space, so M̃ can systematically exceed the true number of marked data values. Section 5.1 concedes that the failure rate grows as M̃/Ñ moves away from M/N (Fig. 13) and proposes a sampling-based estimate of the distribution, but that estimator is not inserted into Algorithm 1 and no proof or bound connects the sample size h in Eq. (14) to a guarantee on the resulting Grover-Long failure rate. Formula (21) and Fig. 15 then inherit this unvalidated success assumption in the complexity comparison. Additionally, Section 4.2 defines success for the minimum search as d1 ≥ d0 even though the oracle marks values ≤ d0, so the reported 6-qubit validation may have counted the wrong outcome.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes QUMMSA, a variant of Dürr–Høyer quantum minimum/maximum search. QUMMSA replaces the probabilistic quantum exponential searching subroutine with the Grover–Long exact search algorithm, sets the Grover–Long phase and iteration parameters from estimates M̃ and Ñ of the number of marked items and database size, terminates the outer loop after a constant c repetitions instead of DHA's threshold, and gives explicit circuit constructions for the phase operator I0 and oracles together with three simplification rules. The authors report a two-qubit experiment on IBMQ Yorktown comparing Grover–Long with QESA, a six-qubit numerical simulation for a 36-item excerpt of Titanic passenger ages, a failure-rate analysis for both subroutines, and a complexity comparison with DHA. The central advertised advantage is that the success probability can approach 100% when the ratio M/N is known accurately, while the circuit costs are lower than DHA for large databases.","tokens_in":14785,"tokens_out":7918,"duration_ms":76575,"significance":"Conditional on its assumptions, the paper's central idea is sound: replacing QESA with Grover–Long is a natural way to make the inner search deterministic, and the reported circuit constructions, simplification rules, and hardware demonstration are useful and transparent. The paper includes detailed circuit diagrams for I0 and oracles, three simplification principles, and full data tables for the Titanic example, which facilitate reproduction. I found no sign of circular reasoning or outcome-dependent parameter fitting. However, the strongest advertised claims—near-100% success and complexity advantage—currently rest on an estimator whose accuracy is not proved, and the 6-qubit validation is compromised by a wrong success condition. These are fixable, but they need to be corrected before the claims can be accepted.","major_comments":[{"comment":"The success condition for the minimum-search simulation is stated as \"If d1 ≥ d0, the algorithm is thought to operate successfully\", but the oracle constructed for minimum search marks all values ≤ d0. A correct minimum-search success condition is d1 ≤ d0. As written, the 6-qubit validation may count measurements above d0 as successes, so the reported comparison with QESA in Section 4.2 does not support the claimed advantage for minimum search.","section":"Section 4.2, text before Fig. 11"},{"comment":"The near-100% success claim depends on M̃/Ñ closely approximating M/N, but the implemented estimator M̃ = d0 + 1, Ñ = 2^n (Section 4.2) is exact only when all code states in [0, 2^n − 1] hold data values and the data are uniform. Hypothesis (6) explicitly permits zero-amplitude basis states, and the Titanic excerpt stores only 36 values in a 64-state 6-qubit code space, so M̃ can systematically exceed the true number of marked items. The paper gives no quantitative bound on the Grover-Long failure rate as a function of the estimation error, and the sampling estimator in Eq. (14) is not inserted into Algorithm 1; hence the abstract's \"close to 100%\" claim and the complexity comparison in Eq. (21) are not established.","section":"Section 5.1, Eq. (14) and Fig. 13"},{"comment":"The total failure probability ε enters the final complexity formula, but it is never derived from the outer-loop parameter c and the Grover-Long parameter error; Fig. 15 fixes ε = 0.1 without justification. The two failure contributions in Section 5.1 are analyzed separately, so the paper does not prove the overall QUMMSA failure probability or the claimed complexity advantage over DHA for large databases.","section":"Section 5.2, Eq. (21) and Fig. 15"},{"comment":"For the general case N < 2^n admitted by Hypothesis (6), the preparation operator W that creates the uniform superposition over the N occupied basis states is not constructed and no circuit for it is given, despite Hypothesis (5) assigning it cost log2(N). Without such a construction, the claim in Section 3 of a general design method for QUMMSA circuits and the complexity accounting in Section 5.2 are incomplete.","section":"Section 3.1, Eq. (1)"}],"minor_comments":[{"comment":"The sentence \"Therefore, we assume that each orthonormal basis state stores a data value\" appears twice verbatim in the paragraph before Eq. (13); the duplicate should be removed.","section":"Section 5.1"},{"comment":"The text refers to \"Fig 10(a)\" when discussing the theoretical failure rate of Grover-Long algorithm, but the relevant panels appear in Fig. 12; the figure cross-references should be renumbered.","section":"Section 4.2"},{"comment":"References [25] and [26] are identical entries for Vandersypen et al.; one should be removed or replaced with a distinct citation.","section":"References"},{"comment":"The column header \"Name Age After Encoding\" repeats inside the table, and the column alignment is inconsistent; the table should be reformatted so each data column has a single clear header.","section":"Appendix B, Table 2"},{"comment":"There are several typographical errors: \"donates\" in the Fig. 14 caption should be \"denotes\", \"combing\" in Section 6 should be \"combining\", and \"Durr, Hoyer's\" should be \"Dürr–Høyer's\".","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"I see no evidence of circular reasoning or outcome-dependent parameter fitting; the main risk is overclaiming the accuracy of the M̃ estimator. The manuscript is within scope for a quantum-information journal, but the validation and proof gaps need to be addressed before I can recommend acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper takes a known idea—replacing Dürr–Høyer’s QESA inner search with Grover–Long—and wraps it in concrete circuit design and a small hardware test. That is a reasonable engineering contribution. The three simplification rules for oracles are practical, the 2-qubit IBM experiment is real, and Appendix C’s recurrence equations give a useful way to compute failure rates without building large unitary matrices.\n\nThe soft spots are real but not fatal. The 'close to 100%' success claim only holds when the Grover–Long parameters are set from the true marked fraction M/N. The implemented default, M̃ = d0+1 and Ñ = 2^n, assumes the code space is densely and uniformly occupied. The paper’s own Fig. 13 shows the failure rate climbing as M̃/Ñ moves off the diagonal, and the Titanic dataset—36 values in 64 states—is exactly the sparse case where that default is unreliable. Section 5.1 proposes a sampling-based fix, but it is not inserted into Algorithm 1 and no bound connects the sample size h to a resulting failure-rate guarantee. The conclusion’s near-100% language should be conditional on that missing piece.\n\nThere is a concrete internal error: Section 4.2 defines success in the minimum-search simulation as d1 ≥ d0, which is backwards for an oracle marking values ≤ d0. If read literally, that means the reported 6-qubit validation may have counted the wrong measurement outcomes. That needs to be fixed and re-run or explained. The complexity formula (21) is also asserted without derivation and relies on unstated assumptions (M_k geometric, M0 ≈ N/2). The novelty is modest: the paper does not compare with the earlier min-search algorithm cited as [23], so the improvement over that line is unclear.\n\nWho gets value? Circuit designers and experimentalists who need a concrete min/max subroutine on small hardware. It is not a paper to cite for a new asymptotic result. I would send it to peer review, but with a clear request for major revision: correct the success condition, integrate the sampling estimator into Algorithm 1 with a proof or a bound, and rewrite the complexity claims with stated assumptions. If those land, it becomes a solid application note.","headline":"Useful engineering on top of a known combination, but the near-100% success claim needs the estimator and the success condition fixed before it is published as-is.","tokens_in":15315,"tokens_out":4484,"would_cite":false,"duration_ms":43018,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":["03.67.Ac","03.67.Lx"],"model":"deepseek-v4-flash","headline":"Optimized quantum min–max search replaces its probabilistic inner search with Grover–Long exact search, pushing success probability near 100 percent when the solution ratio is known.","keywords":["quantum search","maximum and minimum finding","Grover-Long algorithm","amplitude amplification","quantum circuits","oracle construction","failure rate","database search"],"falsifier":"Run QUMMSA on a database whose values occupy only a small fraction of the $2^n$ code space (e.g., 6 qubits with 10 distinct values spanning the range) and count how often the Grover–Long measurement returns a value above the current threshold; the paper's own contour map predicts an elevated failure rate in that regime, which would contradict the near-100% success claim if the method is used without the sampling refinement.","tokens_in":14275,"feed_emoji":"⚛️","tokens_out":7579,"duration_ms":68562,"temperature":0.7,"pith_summary":"This paper claims that the known quantum algorithm for finding a maximum or minimum can be strengthened by replacing its probabilistic inner search step with the Grover–Long exact search, provided the fraction of marked database items can be estimated. The authors give a concrete algorithm, QUMMSA, along with general circuits for the oracle and phase-shift operators, and three equivalent simplifications that reduce gate counts. When the estimated ratio $\\tilde{M}/\\tilde{N}$ is accurate, the success probability approaches 100 percent; for large databases the paper also claims an advantage in total complexity because it prepares far fewer initial states than the earlier method. The key step is demonstrated on a two-qubit superconducting processor, and a six-qubit simulation on a real dataset shows lower failure rates than the earlier approach.","feed_headline":"Near-certain quantum min-max search replaces probabilistic core","feed_subtitle":"Estimated search parameters push success toward 100 percent and cut circuit complexity for large databases.","key_machinery":"The load-bearing object is the Grover–Long operator: a single Grover iteration in which the conditional phase shifts in the oracle and the $I_0$ operator are replaced by rotations through an adjustable angle $\\phi = 2\\arcsin(\\sin(\\pi/(4J+2))/\\sin\\beta)$, with $\\sin\\beta = \\sqrt{M/N}$. When $J$ satisfies the lower bound from the paper, measuring the register yields one of the marked states with zero theoretical failure. The paper derives $J$ and $\\phi$ from estimated values $\\tilde{M}$ and $\\tilde{N}$, constructs the diagonal phase-shift operator $I_0 = \\mathrm{diag}[e^{i\\phi},1,\\ldots,1]$, builds oracles that mark individual or threshold-marked basis states, and then applies three simplification principles to lower the cost of controlled-phase gates. This machinery is what turns a probabilistic amplitude-amplification subroutine into a deterministic one while preserving the quadratic speedup.","core_discovery":"The paper's central claim is that the earlier quantum min–max search DHA can be rebuilt on the Grover–Long operator, a version of Grover's iteration in which the usual phase inversion is replaced by an adjustable rotation through an angle determined by the estimated ratio of marked values to database size. With an iteration count $J$ satisfying $J \\geq \\lfloor (\\pi/2 - \\beta)/\\beta \\rfloor + 1$, where $\\sin\\beta = \\sqrt{M/N}$, the search returns a marked value with zero theoretical failure rate. The paper then computes these parameters from estimates $\\tilde{M} = d_0 + 1$ and $\\tilde{N} = 2^n$, provides explicit quantum circuits for the phase-shift operator and for oracles marking one or many values, and gives three simplification rules that reduce the number of multi-qubit controlled gates. Compared with the repetition-based inner search of DHA, the QUMMSA has a deterministic iteration count and a worst-case success probability in the main loop of $1 - (1/2)^c$ for a constant $c$, which approaches 1 as $c$ grows.","pith_inferences":["The real bottleneck of the method is estimation, not search: if a user supplies a good rank estimate for the current threshold from a small sample, the same Grover–Long circuit becomes near-deterministic; the paper's own sampling formula suggests such a pre-processing step, though it is not integrated into the pseudocode.","Because the estimated fraction $\\tilde{M}/\\tilde{N}$ is derived from a uniform filling of the code space, the method's success on sparse real-world tables will depend strongly on how well the empirical cumulative distribution matches that assumption; the paper's contour map shows the failure rate climbing away from the diagonal.","The three circuit simplifications are not specific to min/max finding and could be reused for any oracle that marks values below or above a threshold, such as range queries or top-$k$ selection.","A fully practical version of the algorithm would need a certified procedure that estimates $M/N$ with bounded error before running the quantum search; the paper leaves this as a separate step, so a combined classical-sampling-plus-quantum-search pipeline is the natural next development."],"forward_implications":["If the ratio $\\tilde{M}/\\tilde{N}$ is close to the true ratio, the inner Grover–Long search succeeds with probability close to 1, so the full min–max algorithm inherits a near-deterministic success behavior.","Replacing the random stopping rule of DHA with a fixed constant $c$ gives an exponential improvement in the worst-case failure rate of the outer loop, $1/2^c$.","The simplified oracle circuits reduce the number of two-qubit controlled gates for marking $2^m$ consecutive states from $2^{n+m-1}$ to $2^{n-m-1}$, which directly lowers the gate load for threshold oracles used in min/max search.","The complexity analysis implies that QUMMSA prepares about $\\log_2 N$ initial states instead of $\\log_2^2 N$, so the advantage over DHA grows as the database size increases."],"supporting_citations":[{"why":"Provides the Grover–Long exact search algorithm with zero theoretical failure rate, the core subroutine QUMMSA replaces QESA with.","marker":"[16]"},{"why":"Introduces the DHA minimum-finding algorithm that this paper optimizes and whose complexity is the comparison baseline.","marker":"[22]"},{"why":"Defines the quantum exponential searching algorithm (QESA) and its tight bounds, the probabilistic inner search being replaced.","marker":"[17]"},{"why":"Supplies the elementary-gate decomposition for controlled-phase gates used in the oracle simplifications.","marker":"[33]"},{"why":"Gives the minimum sample-size formula used in the proposed estimation refinement for the ratio M/N.","marker":"[37]"},{"why":"Original fast quantum search algorithm that underlies the iteration structure of both Grover and Grover–Long searches.","marker":"[6]"},{"why":"Standard quantum-circuit algebra used for the third equivalent simplification principle.","marker":"[36]"}],"fun_headline_variants":["Quantum min-max search hits near-certain success","Optimized quantum maxima search cuts circuit complexity","Quantum min-max algorithm boosts success to near 100%","Deterministic iteration quantum search for max/min","Quantum min-max search: near-certain and simpler gates"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central assumption is that the estimated ratio of marked values to database size, taken from a uniform filling of the code space, is close to the true ratio; if the database is sparse or non-uniform, the Grover–Long parameters are wrong and the near-100% success claim relies on sampling refinements that are not part of the main algorithm.","fun_headline_variants_meta":{"raw":{"variants":["Quantum min-max search hits near-certain success","Optimized quantum maxima search cuts circuit complexity","Quantum min-max algorithm boosts success to near 100%","Deterministic iteration quantum search for max/min","Quantum min-max search: near-certain and simpler gates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000364,"raw_usage":{"total_tokens":1986,"prompt_tokens":995,"completion_tokens":991,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":611,"completion_tokens_details":{"reasoning_tokens":917}},"tokens_in":611,"tokens_out":991,"duration_ms":7614,"temperature":1.0,"reasoning_tokens":917,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:53:45.010608+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run QUMMSA on a database whose values occupy only a small fraction of the $2^n$ code space (e.g., 6 qubits with 10 distinct values spanning the range) and count how often the Grover–Long measurement returns a value above the current threshold; the paper's own contour map predicts an elevated failure rate in that regime, which would contradict the near-100% success claim if the method is used without the sampling refinement.","supporting_citations":[{"cited_title":"A fast quantum mechanical algorithm for database search[C]// Proc","cited_arxiv_id":null,"evidence_quote":"Provides the Grover–Long exact search algorithm with zero theoretical failure rate, the core subroutine QUMMSA replaces QESA with."},{"cited_title":"Arbitrary phases in quantum amplitude amplification[J]","cited_arxiv_id":null,"evidence_quote":"Introduces the DHA minimum-finding algorithm that this paper optimizes and whose complexity is the comparison baseline."},{"cited_title":"Quantum mechanics helps in searching for a needle in a haystack[J]","cited_arxiv_id":null,"evidence_quote":"Defines the quantum exponential searching algorithm (QESA) and its tight bounds, the probabilistic inner search being replaced."},{"cited_title":"A new quantum algorithm for solving the minimum searching problem[J]","cited_arxiv_id":null,"evidence_quote":"Supplies the elementary-gate decomposition for controlled-phase gates used in the oracle simplifications."},{"cited_title":"Demonstration of two -qubit algorithms with a superconducting quantum processor[J]","cited_arxiv_id":null,"evidence_quote":"Gives the minimum sample-size formula used in the proposed estimation refinement for the ratio M/N."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Original fast quantum search algorithm that underlies the iteration structure of both Grover and Grover–Long searches."},{"cited_title":"Implementation of a three -quantum-bit search algorithm[J]","cited_arxiv_id":null,"evidence_quote":"Standard quantum-circuit algebra used for the third equivalent simplification principle."}],"review_version":1}