Finite Imaginary-Time Evolution for Polynomial Unconstrained Binary Optimization

This paper introduces Finite Imaginary-Time Evolution (FinITE), a non-unitary quantum algorithm utilizing the linear-combination-of-unitaries framework to solve polynomial unconstrained binary optimization problems with exact ground-state fidelity guarantees and fixed-point amplitude amplification, while avoiding the need for quadratization.

The Gist

Imagine you are trying to find the lowest point in a vast, foggy mountain range. In the world of computer science, this "lowest point" represents the perfect solution to a complex puzzle, like organizing a delivery route or scheduling a factory. This type of puzzle is called Polynomial Unconstrained Binary Optimization (PUBO).

For decades, scientists have wanted to use quantum computers to solve these puzzles faster. A popular theoretical method for finding the lowest point is called Imaginary-Time Evolution (ITE). Think of ITE as a magical filter that slowly washes away all the "high ground" (bad solutions) and leaves only the "valley floor" (the best solution).

However, there is a catch: this magical filter is non-unitary. In the language of quantum mechanics, this means it's like trying to pour water into a bucket that has a hole in the bottom. You can't build a standard quantum circuit to do this directly; the math just doesn't work with the rules of quantum physics.

The Problem with "Infinite" Time

Previous attempts to fix this involved running the filter for a very long time (approaching "infinite" time). The idea was that if you wait long enough, the bad solutions would disappear completely.

The authors of this paper, led by Jaehee Kim and Joonsuk Huh, discovered a major flaw in this "wait forever" approach. They found that for many of these puzzles, if you wait too long, the filter doesn't just keep the best solution; it accidentally filters out everything. The success rate of the quantum computer drops to zero, and you get nothing. It's like trying to find a needle in a haystack by burning the whole haystack down; eventually, the needle is gone too.

The Solution: Finite Imaginary-Time Evolution (FinITE)

The team developed a new method called FinITE (Finite Imaginary-Time Evolution). Instead of waiting forever, they figured out exactly how long to run the filter for a specific puzzle to get a good result without losing everything.

Here is how they did it, using some simple analogies:

1. The "Lego" Approach (LCU)
To build their quantum filter, they used a technique called Linear Combination of Unitaries (LCU). Imagine you have a complex machine that needs to be built from many small, simple Lego blocks. Each block represents a part of the puzzle.

• Because the parts of their specific puzzles (called PUBO) don't fight with each other (they "commute"), the team could snap these Lego blocks together perfectly without any gaps or errors.
• This allowed them to build the filter exactly, without needing to simplify the puzzle first (a process called "quadratization" that usually adds unnecessary complexity).

2. The Trade-Off (The See-Saw)
The paper discovered a perfect mathematical balance, or a "see-saw," between two things:

• Fidelity: How close the result is to the perfect solution.
• Success Probability: How likely the quantum computer is to actually finish the job without crashing (the "hole in the bucket" getting bigger).

They proved a precise formula: As you push the filter harder to get a better solution (higher fidelity), the chance of the computer succeeding drops. But, they calculated the exact point where this trade-off is manageable.

3. The "Booster" (Amplitude Amplification)
Since the success rate drops as the filter gets stronger, the team added a "booster" called Fixed-Point Amplitude Amplification (FPAA).

• Imagine you are trying to hear a whisper in a noisy room. The whisper gets quieter as you try to tune it out, but you have a special pair of headphones (FPAA) that can amplify that specific whisper back up to a normal volume.
• This booster allows the computer to succeed even when the natural success rate is low, as long as you know the minimum chance of success.

The "Sweet Spot" (The Threshold)

The most important result of the paper is a formula for the "Sweet Spot."
Instead of guessing how long to run the simulation, the authors provide a clear rule. If you know a little bit about the puzzle (how many solutions are good, and how far apart the best solution is from the next best), you can plug those numbers into their formula.

• The formula tells you the exact amount of time (called $\beta$) to run the filter.
• Run it for less time, and the answer isn't good enough.
• Run it for more time, and the computer will likely fail to give you an answer at all.
• Run it for this specific time, and you get the best possible answer with a guaranteed chance of success.

Real-World Testing

The team tested this on two types of puzzles:

1. MaxCut (QUBO): A classic problem of dividing a group of people into two teams so that the most arguments happen between the teams. They tested this on a small group of 5 people.
2. HUBO: A more complex version involving three-way interactions (like a group of three friends where the dynamic changes if one person leaves). They tested this on 8 "qubits" (quantum bits).

In both cases, their computer simulations confirmed that their math was perfect. The "see-saw" balance they predicted happened exactly as the formula said, even down to the tiny decimal points.

Summary

In short, this paper solves a "Goldilocks" problem for quantum optimization. It stops us from waiting too long (which breaks the machine) or not waiting long enough (which gives a bad answer). By using a precise mathematical formula and a "booster" technique, FinITE gives us a reliable, step-by-step recipe to find the best solutions to complex binary puzzles using quantum computers, without needing to simplify the puzzles first.

Technical Summary

1. Problem Statement

Polynomial Unconstrained Binary Optimization (PUBO) is a fundamental class of combinatorial optimization problems (including QUBO and HUBO) where a polynomial objective function of binary variables is minimized. These problems map naturally to diagonal Pauli-Z cost Hamiltonians ($\hat{H}$), where the ground state encodes the optimal solution.

Imaginary-Time Evolution (ITE) is a standard theoretical primitive for preparing ground states, as the operator $e^{-\beta \hat{H}}$ exponentially suppresses excited-state components. However, ITE is non-unitary, making it impossible to implement directly on quantum hardware.

Existing quantum approaches face significant limitations:

• Variational methods (VITE/QITE): Rely on classical optimization loops and suffer from approximation errors or local-unitary fitting issues.
• Probabilistic methods (PITE/LCU): Recent Linear Combination of Unitaries (LCU) approaches operate at finite $\beta$ but lack a closed-form analytical relationship between the LCU success probability and the ground-subspace fidelity.
• The $\beta \to \infty$ Limit: Taking the imaginary time $\beta$ to infinity causes the success probability of standard LCU constructions to vanish for most problems (especially non-bipartite graphs), rendering the method impractical without a specific strategy for finite $\beta$.
• Quadratization: Higher-order terms (HUBO) are often reduced to quadratic terms (QUBO) via auxiliary variables, which expands the search space and alters the cost structure.

2. Methodology: Finite Imaginary-Time Evolution (FinITE)

The authors propose FinITE, a finite-$\beta$ construction specifically designed for diagonal Pauli-Z Hamiltonians arising from PUBO instances. The methodology consists of three core components:

A. Termwise-LCU Block-Encoding

Instead of approximating the full evolution or reducing higher-order terms, FinITE utilizes the Linear Combination of Unitaries (LCU) framework.

• Factorization: Since the Pauli-Z terms in PUBO Hamiltonians commute, the operator $e^{-\beta \hat{H}}$ factorizes exactly into a product of termwise exponentials: $e^{-\beta \hat{H}} = \prod_\mu e^{-\beta x_\mu \sigma_\mu}$.
• Implementation: Each term is block-encoded individually using an ancilla qubit. Because the terms commute, these blocks compose without Trotter (product-formula) error.
• Handling Higher Orders: The method handles higher-order Pauli-Z terms (cubic, quartic, etc.) directly, eliminating the need for quadratization (introducing auxiliary variables).

B. The Exact Finite-$\beta$ Identity

The paper derives a rigorous, closed-form identity linking the LCU success probability ($P_{LCU}$) and the ground-subspace fidelity ($F_g$) for any finite $\beta$:
$$P_{LCU}(\beta) \cdot F_g(\beta) = \gamma_0 e^{-2\beta(W + E_0)}$$
Where:

• $\gamma_0$: Initial overlap with the ground subspace.
• $W$: The $\ell_1$-norm of the non-identity Pauli coefficients ($W = \sum |x_\mu|$).
• $E_0$: The ground-state energy.

This identity reveals a strict trade-off: as $\beta$ increases, fidelity $F_g$ approaches 1, but the success probability $P_{LCU}$ decays exponentially.

C. Fixed-Point Amplitude Amplification (FPAA)

To counteract the vanishing success probability at the required finite $\beta$, FinITE integrates Fixed-Point Amplitude Amplification.

• Unlike standard amplitude amplification, FPAA does not require precise knowledge of the initial success probability to avoid "overshooting."
• It uses a known lower bound on the success probability (derived from the identity above) to boost the success rate to a target level with a provable query complexity bound.

3. Key Contributions

1. Closed-Form Analytical Framework: The paper provides the first exact identity relating LCU success probability and ground-state fidelity for commuting Hamiltonians. This replaces heuristic bounds with a precise mathematical relationship.
2. Closed-Form Threshold Rule ($\beta^\star$): Using the identity and a gap-based fidelity lower bound, the authors derive a sufficient imaginary time $\beta^\star$ required to achieve a target fidelity $\bar{F}$:
   $$\beta^\star(\bar{F}) = \max\left(0, \frac{1}{2\Delta} \log \frac{\bar{F}(1-\gamma_0)}{\gamma_0(1-\bar{F})}\right)$$
   where $\Delta$ is the spectral gap. This allows for the analytical selection of $\beta$ based on estimated spectral properties.
3. Direct HUBO Handling: The method processes higher-order interactions (HUBO) natively without quadratization, preserving the original problem structure and avoiding the overhead of auxiliary variables.
4. Resource Complexity Analysis: The paper provides an explicit query complexity bound for the FPAA stage, showing that the cost scales as $O\left(\frac{\log(2/\delta)}{\sqrt{\gamma_0}} e^{\beta^\star(W+E_0)}\right)$.

4. Results and Verification

The authors validated FinITE using statevector and shot-based simulations on two distinct instances:

• 5-Vertex MaxCut (QUBO):

  • A non-bipartite graph where the $\beta \to \infty$ limit would yield zero success probability.
  • Verification: Statevector simulations confirmed the identity $P_{LCU} F_g = \frac{3}{16} e^{-4\beta}$ with machine precision (relative error $\sim 10^{-14}$).
  • FPAA Performance: Shot-based simulations demonstrated that FPAA could maintain high ground-subspace preparation probability even as $\beta$ increased, provided the query complexity $L$ was sufficient.

• 8-Qubit Cubic HUBO:

  • A native higher-order problem with mixed cubic and quadratic terms.
  • Verification: The identity held across three different initial-state regimes (uniform, weak warm-start, strong warm-start).
  • Warm-Start Impact: The simulations confirmed that increasing the initial overlap $\gamma_0$ (via warm-starting) linearly scales the success probability envelope, significantly reducing the required $\beta$ to reach a target fidelity.

5. Significance and Implications

• Practical Quantum Optimization: FinITE offers a concrete, non-variational algorithm for solving PUBO problems on near-term and fault-tolerant quantum hardware, avoiding the barren plateau issues common in variational algorithms.
• Theoretical Clarity: By establishing the exact trade-off between success probability and fidelity, the work provides a clear "rulebook" for selecting algorithm parameters ($\beta$) rather than relying on trial-and-error.
• Scalability: The ability to handle higher-order terms directly makes FinITE particularly valuable for problems where quadratization would exponentially increase the qubit count.
• Future Directions: The paper suggests that while the method requires estimates of the spectral gap and initial overlap, these can be obtained via classical preprocessing or heuristic warm-starts, making the approach viable for practical deployment.

In summary, FinITE transforms imaginary-time evolution from a theoretical concept into a finite-resource, analytically tractable quantum algorithm for combinatorial optimization, bridging the gap between non-unitary theory and unitary quantum implementation.