{"id":"8d16487f-a935-4a78-a9ab-065ce47076e9","arxiv_id":"2505.22924","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"ITEMC iteratively mimics imaginary time evolution to solve QUBO instances, achieving high CVaR-based approximation ratios in simulation and finding the best known solution on IBM hardware for up to 80 qubits.","lead":"This paper introduces a hybrid quantum-classical algorithm that prepares low-energy solutions to QUBO optimization problems by mimicking imaginary time evolution with a shallow circuit of one- and two-qubit gates. The authors report approximation ratios above 0.99 in simulations up to 150 qubits, and they run the algorithm on IBM hardware for 40, 60, and 80 qubits.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Large-scale approximation ratios rely on simulated-annealing reference energies without error bars, biasing the headline claim.","rationale":"The paper's central contribution is a resource-efficient QUBO solver with a quantitative performance guarantee ('above 0.99 up to 150 qubits'). That number is the hook of the abstract and the basis for the claimed scalability. The evaluation pipeline for N>22 uses simulated annealing as a stand-in for the optimum, and the paper gives no estimate of the SA optimality gap, no schedule details, and no comparison with exact results beyond 22 qubits. Because the approximation ratio is defined with E_SA in the denominator, any suboptimality of SA directly and favorably biases the headline metric. This is not merely a concern about interpreting the CVaR tail (a separate but secondary issue); it is a potential artifact in the very quantity the paper advertises. A straightforward recomputation with certified or much stronger references would settle it. I therefore agree with the reader's weakest-assumption analysis and see no reason to change the conditional verdict.","tokens_in":15802,"tokens_out":10593,"duration_ms":108627,"concrete_test":"Recompute the approximation ratios for the 30–150 qubit 3-regular instances (or a representative subset at N=30, 50, 100, 150) using a certified optimal solver such as exact branch-and-bound or Gurobi with an optimality certificate, instead of simulated annealing. If exact solution is infeasible for N=150, run at least 100 independent simulated-annealing runs with a schedule 100× longer and take the best energy, and additionally check on N≤22 that SA reproduces brute-force optima to quantify the gap. If the recomputed ratios fall below 0.99, the headline claim is inflated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline claim ('classical simulations achieve approximation ratios above 0.99 up to 150 qubits', abstract and §IV) is evaluated against reference energies E_opt obtained from simulated annealing for N>22, with no error bars or optimality gap reported. Since any SA solution is a feasible configuration, its energy is an upper bound on the true ground-state energy: E_SA ≥ E_true. The reported ratio CVaR_α/E_SA therefore has a systematic upward bias relative to CVaR_α/E_true, and the bias can be substantial if SA terminates far from the optimum. Neither the SA schedule, the number of restarts, nor the observed gap to exact optima for N≤22 is provided, so the reader cannot tell whether the 0.99+ values are genuine or an artifact of a weak denominator. The same SA reference is used to define 'fidelity' in the hardware runs (Table II), so the hardware claims inherit the bias. This is the single most load-bearing weakness: if the SA reference is off by even a few percent, the central quantitative claim fails.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes ITEMC, a hybrid quantum-classical algorithm for QUBO optimization that constructs a parameterized circuit whose gates are chosen to mimic imaginary time evolution. The circuit parameters are obtained from local one- and two-qubit expectation values rather than from a full energy evaluation, and an iterative feedback loop updates the initial product state using CVaR-tail expectations from the previous iteration. An adaptive pre-sorting step selects among five gate orderings. The authors report classical simulations with approximation ratios above 0.99 up to 150 qubits (for 3-regular graphs), linear entanglement-entropy scaling for dense graphs, and hardware demonstrations on IBM devices for 40, 60, and 80 qubits. The central claim is that ITEMC achieves high-quality QUBO solutions with substantially lower measurement overhead than VQE.","tokens_in":15902,"tokens_out":10266,"duration_ms":106395,"significance":"The core idea is interesting and potentially useful: replacing full Hamiltonian measurements in the variational loop with local expectation values, combined with an iterative warm-start and a heuristic gate-ordering selection, is a concrete and well-motivated design. The small-system benchmarks are extensive (400 instances per size up to 22 qubits, exact ground state, finite-shot simulations), and the paper explicitly gives resource estimates and compares them with VQE. If the large-scale claims were properly supported, this could be a practical resource-efficient alternative for near-term quantum optimization. However, the headline 150-qubit claim currently rests on simulated-annealing reference energies without error bars, and the hardware results are single-instance demonstrations, so the significance is conditional on fixing those benchmarks.","major_comments":[{"comment":"The headline approximation ratios above 0.99 for N>22 are computed with E_opt taken from simulated annealing, and the manuscript does not report the SA schedule, the number of restarts, or any optimality gap. Since SA returns feasible spin configurations, its energy is an upper bound on the true ground-state energy; for the negative energies typical of these spin-glass instances, the ratio CVaR/E_SA is systematically larger than CVaR/E_true and can even exceed 1 if CVaR > E_SA. This affects the central quantitative claim directly. Please provide a comparison of SA with exact optima for N<=22 (e.g., the fraction of instances where SA reaches the exact ground state and the distribution of SA-energy gaps), and for N>22 report a sensitivity analysis or an independent lower bound on E_opt. The MPS truncation error (max bond dimension 100) should also be quantified, since the large-scale simulation results inherit it.","section":"IV.B, Fig. 8, and Abstract"},{"comment":"The hardware experiments consist of one instance per size (40, 60, and 80 qubits) with no repeated runs or error bars. The 'fidelity' for 40 and 60 qubits is 1 only relative to the SA-found best solution, not to a known ground state, and for 80 qubits the fidelity is 2e-5. The conclusion that the hardware results are 'compatible with simulated annealing' is therefore too weak to support the abstract's hardware claim. Please report multiple instances, shot-noise error bars, and exact or independently validated reference energies, or explicitly temper the claim to a single-instance demonstration.","section":"V, Table II"},{"comment":"The claim that ITEMC circuits are classically hard to simulate is not supported by the data shown. Fig. 7 extends only to N=22, and the footnote itself states that the data points are insufficient to distinguish sublinear from low-slope linear scaling for 3-regular graphs. The large-scale MPS simulations are restricted to 3-regular graphs, precisely the regime where the entropy scaling is mild, while the linear-entropy regime (densities >= 0.5) is demonstrated only at small sizes where exact simulation is possible. Thus the 'hard-to-simulate' and 'high-performance at large N' regimes do not overlap in the presented evidence. Please provide entropy data for larger N in the dense regime or explicitly state that the hardness extrapolation is speculative.","section":"IV.B, Fig. 7, and footnote [45]"}],"minor_comments":[{"comment":"The text says 400 random instances are generated for each problem size and density, but the caption of Fig. 2 says the results are averaged over 100 instances; please reconcile these numbers.","section":"IV.A"},{"comment":"The column labels for Table II are ambiguous: the first row reads '40 1 0.759' and the text says the 80-qubit fidelity is 2e-5, but the table row seems to place 0.974 and 2e-5 in the ar and fidelity columns. Please label all columns explicitly and make the order (qubits, ar, fidelity, shots per iteration, iterations, total shots) unambiguous.","section":"Table II"},{"comment":"There are several typos that should be fixed: 'gate ording' in Section III.C, 'simulated annealning' in Section VI, and 'classic numerical results' in the Introduction.","section":"III.C and VI"},{"comment":"In Eq. (14), E_k are described as 'energy eigenvalues', but in the measurement setting they are sampled bitstring energies; please use a term such as 'sampled energies' to avoid confusion.","section":"Eq. (14)"},{"comment":"The sentence 'The hardware runs are demonstrated on IBM's quantum devices for 40, 60, and 80 qubits,' is incomplete as it appears before Section V; either remove it or complete it as a lead-in to Section V.","section":"IV (intro)"}],"recommendation":"major_revision","confidential_remarks":"The SA-reference issue is the main correctness risk. If the authors can show that SA is effectively optimal on the small instances and provide an independent-bound or error-bar analysis for large instances, the central claim may become defensible. The paper would also benefit from stating data/code availability, as none is currently provided."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is a plausible incremental advance in quantum optimization, but its headline numbers are more fragile than they look. The iterative feedback and adaptive gate ordering are genuinely new combinations on top of Ref [15], and the local-overlap parameter optimization is a real resource saving. Small-system statevector tests over 400 instances per density are solid, and convergence in about five iterations is a useful empirical result. The authors are also honest about some limits, e.g., the footnote on not being able to distinguish sublinear vs low-slope entropy scaling.\n\nThe main soft spots are three. First, for N>22 the 'optimal' energy E_opt is a simulated-annealing estimate with no error bars. Any SA result is an upper bound on the true ground state, so the ratio CVaR/E_SA is systematically optimistic. The paper gives no SA schedule, restarts, or gap to exact optima for N≤22, so the 0.99+ values are not yet a reliable quantitative claim. Second, the metric is CVaR with alpha=0.01, i.e., the average of the best 1% of samples. That can be much higher than the mean energy and is not comparable to standard VQE/QAOA reporting. The authors should report mean energies or at least a few quantiles. Third, the 150-qubit MPS results are only on 3-regular graphs, which the authors themselves say remain classically simulable by MPS. The regime where entanglement grows linearly (density >= 0.5) is only demonstrated up to 22 qubits. So the 'scalability' claim is real but limited to classically easy instances. The hardware runs are a single instance per size with no error bars; the 80-qubit fidelity of 2e-5 means the best solution appeared twice in 100,000 samples. Honest reporting, but weak evidence.\n\nOverall, this is a worthwhile submission, not a breakthrough. The algorithm is plausible, the resource analysis is useful, and the paper is reasonably self-aware. I would send it to peer review, but I'd ask for: mean-energy metrics, a comparison with CVaR-QAOA and a classical solver like Gurobi on the same instances, a calibration of the SA reference against exact optima for small sizes, and code/data release. With those, the contribution would be solid.","headline":"Solid incremental algorithm with honest small-scale tests, but the 150-qubit approximation ratios rest on a simulated-annealing denominator and a CVaR tail metric, so the headline performance is unproven.","tokens_in":16514,"tokens_out":2205,"would_cite":false,"duration_ms":22142,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proposes ITEMC, a hybrid quantum-classical optimizer that mimics imaginary time evolution to solve QUBO problems, reporting approximation ratios above 0.99 up to 150 qubits.","keywords":["QUBO","imaginary time evolution","hybrid quantum-classical algorithm","CVaR","combinatorial optimization","gate ordering","approximation ratio","near-term quantum computing"],"falsifier":"Run ITEMC on the same 3-regular random instances at 60 to 150 qubits, but replace the simulated-annealing reference energies with certified lower bounds from an exact or branch-and-bound QUBO solver; if the ratio of ITEMC's CVaR to those certified values drops below 0.99, the paper's central scalability claim is falsified.","tokens_in":15474,"feed_emoji":"⚛️","tokens_out":9734,"duration_ms":110194,"temperature":0.7,"pith_summary":"The paper proposes a hybrid quantum-classical algorithm, ITEMC, for Quadratic Unconstrained Binary Optimization (QUBO), built from single-qubit rotations and two-qubit gates whose parameters are tuned to mimic imaginary time evolution. The key cost saving is that parameter selection uses only one- and two-qubit Pauli expectation values, measured once per iteration, instead of the repeated full-Hamiltonian energy evaluations that variational methods such as VQE require. An iterative feedback loop re-initializes the qubits from the lowest-energy tail of the previous measurements, and an adaptive gate-ordering step selects the best arrangement of two-qubit gates. On random instances—complete and intermediate-density graphs up to 22 qubits, and 3-regular graphs up to 150 qubits—the authors report approximation ratios above 0.99 in classical simulation, convergence in about six iterations, and hardware demonstrations at 40, 60, and 80 qubits whose solutions are compatible with simulated annealing. If these results hold, the method is a low-measurement-cost route to approximate QUBO solutions on near-term quantum hardware.","feed_headline":"Imaginary-time circuit hits 99% on QUBO up to 150 qubits","feed_subtitle":"The hybrid algorithm avoids VQE's costly full-energy loop by tuning gates from local Pauli measurements alone.","key_machinery":"The ITEMC is a parameterized circuit whose building blocks are single-qubit $R_y$ rotations and two-qubit unitaries $U_{ij}(\\theta)=\\exp(-i(\\theta_{ij,1}\\sigma_i^z\\sigma_j^y+\\theta_{ij,0}\\sigma_i^y\\sigma_j^z)/2)$. Each unitary is chosen to maximize the overlap with the exact imaginary-time evolved state, and because the QUBO Hamiltonian is diagonal in the computational basis, the overlap cost factorizes into a small set of Pauli expectation values that are measured once and then processed classically. The iterative part uses CVaR, averaging over the lowest $\\alpha$ fraction of sampled energies, both to select low-energy bitstrings and to compute the $\\sigma^z$ expectations that set the initial $R_y$ angles in the next iteration. The adaptive sorting step tests five gate orderings in the first iteration and fixes the one with the lowest CVaR energy for all later iterations.","core_discovery":"The central claim is that a fixed-structure circuit can be made to act like imaginary time evolution for QUBO without variational full-energy optimization. Each non-unitary imaginary-time factor $e^{-\\tau J_{ij}\\sigma_i^z\\sigma_j^z}$ is approximated by a two-qubit unitary chosen to maximize its overlap with the exact evolved state, while each single-qubit field term is approximated by an $R_y$ rotation; the overlap cost depends only on a small set of one- and two-qubit Pauli expectation values, which are measured once per iteration and then optimized classically. After each pass, the lowest-energy tail of the sampled bitstrings (CVaR with $\\alpha=0.01$) provides both the cost and the qubit $\\sigma^z$ expectations that set the initial rotations of the next pass, so the state improves without deepening the circuit. The paper further shows that ordering the two-qubit gates by sorted QUBO coefficients matters, and it uses an adaptive sort that tries five orderings and keeps the best. The headline numerical result is that this procedure reaches approximation ratios above 0.99 for random QUBO instances up to 150 qubits (3-regular graphs in the large-size simulations), and that dense instances are hard for tensor-network simulation because the entanglement entropy grows linearly with system size.","pith_inferences":["Because the large-scale approximation ratios are referenced to simulated-annealing optima without error bars, an editorial test would be to compare ITEMC against certified optima for moderate sizes (for example, 24 to 40 qubits) before extrapolating the 0.99 figure.","The algorithm uses only the fact that the Hamiltonian is diagonal in the computational basis, so the same ansatz and feedback loop should transfer directly to MaxCut and other Ising-type problems beyond QUBO.","The adaptive sorting step multiplies the first-iteration shot count by five; a learned or heuristic gate-ordering rule could remove this overhead if stable patterns exist in the optimal orderings.","The claimed advantage over VQE depends on the iteration count staying small; the paper demonstrates this on random instances, but adversarial or worst-case QUBO families remain an open test."],"forward_implications":["Per-iteration measurement cost is $O(M/\\epsilon^2)$ with $M$ the number of Hamiltonian terms, because the gate parameters are fixed by local Pauli expectations rather than by repeated full-energy evaluations.","In classical simulation, a 150-qubit 3-regular instance needs only about eleven circuit executions: five to select the gate ordering and roughly six iterative steps, compared with the much larger evaluation counts typical of VQE-style optimization.","For graph densities at or above 0.5, the entanglement entropy of the ITEMC state grows linearly with system size, making matrix-product-state simulation expensive and marking dense QUBO instances as the regime where a quantum processor could offer an advantage.","On current superconducting hardware, solutions at 40, 60, and 80 qubits match simulated-annealing solutions, with the ground state found at high fidelity for 40 and 60 qubits."],"supporting_citations":[{"why":"Establishes that Ising spin-glass (equivalently QUBO) optimization is NP-hard, motivating approximate hybrid approaches.","marker":"[2]"},{"why":"Defines VQE, the variational baseline whose full-energy measurement cost ITEMC is compared against.","marker":"[4]"},{"why":"Introduces QAOA, the other main variational algorithm benchmarked in the paper's framing.","marker":"[6]"},{"why":"Supplies the two-qubit ansatz and the overlap cost functions that ITEMC optimizes to mimic imaginary time evolution.","marker":"[15]"},{"why":"Previous quantum imaginary time evolution method, presented as more resource-intensive than the ITEMC construction.","marker":"[30]"},{"why":"Supplies the mapping from QUBO binary variables to Pauli-Z spin Hamiltonians that the ITEMC construction assumes.","marker":"[39]"},{"why":"Defines CVaR, the tail-averaged cost function used for energy evaluation and state-update expectations.","marker":"[43]"},{"why":"Simulated-annealing sampler used to estimate reference optimal energies for systems above 22 qubits.","marker":"[46]"}],"fun_headline_variants":["QUBO solved by mimicking imaginary time, 99% up to 150 qubits","Imaginary time mimicry solves QUBO at 99% for 150 qubits","Avoid full energy loops: QUBO via imaginary time mimicry","QUBO circuits that imitate imaginary time hit 99% accuracy","Local Pauli reads mimic imaginary time for QUBO, 99% on 150"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reported approximation ratios for systems larger than 22 qubits are computed relative to simulated-annealing estimates of the optimal energy that carry no error bars, so a biased reference could make the method look better than it is.","fun_headline_variants_meta":{"raw":{"variants":["QUBO solved by mimicking imaginary time, 99% up to 150 qubits","Imaginary time mimicry solves QUBO at 99% for 150 qubits","Avoid full energy loops: QUBO via imaginary time mimicry","QUBO circuits that imitate imaginary time hit 99% accuracy","Local Pauli reads mimic imaginary time for QUBO, 99% on 150"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000277,"raw_usage":{"total_tokens":1666,"prompt_tokens":979,"completion_tokens":687,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":595,"completion_tokens_details":{"reasoning_tokens":580}},"tokens_in":595,"tokens_out":687,"duration_ms":7288,"temperature":1.0,"reasoning_tokens":580,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:57:50.249500+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run ITEMC on the same 3-regular random instances at 60 to 150 qubits, but replace the simulated-annealing reference energies with certified lower bounds from an exact or branch-and-bound QUBO solver; if the ratio of ITEMC's CVaR to those certified values drops below 0.99, the paper's central scalability claim is falsified.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that Ising spin-glass (equivalently QUBO) optimization is NP-hard, motivating approximate hybrid approaches."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines VQE, the variational baseline whose full-energy measurement cost ITEMC is compared against."},{"cited_title":"Kochenberger, J.-K","cited_arxiv_id":null,"evidence_quote":"Introduces QAOA, the other main variational algorithm benchmarked in the paper's framing."},{"cited_title":"Digitized-counterdiabatic quantum approximate optimization algorithm","cited_arxiv_id":"2107.02789","evidence_quote":"Previous quantum imaginary time evolution method, presented as more resource-intensive than the ITEMC construction."},{"cited_title":"Jain, Solving the traveling salesman problem on the d- wave quantum computer, Frontiers in Physics9, 760783 (2021)","cited_arxiv_id":null,"evidence_quote":"Defines CVaR, the tail-averaged cost function used for energy evaluation and state-update expectations."}],"review_version":1}