Freeze and Conquer 🧊

AIQxQIA, 3rd International workshop on AI for Quantum and Quantum for AI

👓 Abstract

In this paper we present a variational algorithm for the Traveling Salesman Problem (TSP) that combines (i) a compact encoding of permutations, which reduces the qubit requirement too, (ii) an optimize-freeze-reuse strategy: where the circuit topology ("Ansatz") is first optimized on a training instance by Simulated Annealing (SA), then "frozen" and re-used on novel instances, limited to a rapid re-optimization of only the circuit parameters. This pipeline eliminates costly structural research in testing, making the procedure immediately implementable on NISQ hardware.

On a set of 40 randomly generated symmetric instances that span 4 - 7 cities, the resulting Ansatz achieves an average optimal trip sampling probability of 100% for 4 city cases, 90% for 5 city cases and 80% for 6 city cases. With 7 cities the success rate drops markedly to an average of $\sim$ 20%, revealing the onset of scalability limitations of the proposed method.

The results show robust generalization ability for moderate problem sizes and indicate how freezing the Ansatz can dramatically reduce time-to-solution without degrading solution quality. The paper also discusses scalability limitations, the impact of "warm-start initialization of parameters, and prospects for extension to more complex problems, such as Vehicle Routing and Job-Shop Scheduling.

🚀 Install and Run

Make a python env and install needed requirements:

python -m venv env
source env/bin/activate
pip install -r requirements.txt

Run the project using 5 city instances as TSP problem and Powell as optimizers (1000 optimizer iterations):

python main.py \
   --max_iterations 10 \
   --cooling_rate 0.9 \
   --eval_file Instances/4_cities/tsp_instance_0.json \
   --test_dir Instances/4_cities/ \
   --qc_params all \
   --optimizers powell \
   --vqa_powell_iter 1000

Here you can find a detailed description of all available cli arguments:

python main.py --help
usage: QLM - Simulated Annealing [-h] [--verbose] [--nomlflow] [--log_system_metrics] [--run_name RUN_NAME] [--uri URI] [--max_iterations MAX_ITERATIONS] [--initial_temp INITIAL_TEMP] [--cooling_rate COOLING_RATE] [--eval_file EVAL_FILE] [--test_dir TEST_DIR] [--qc_params {all,one_per_block}] [--vqa_optimize_once]
                                 [--optimizers {cobyla,powell,bfgs,spsa} [{cobyla,powell,bfgs,spsa} ...]] [--vqa_runs_per_instance VQA_RUNS_PER_INSTANCE] [--vqa_num_tries VQA_NUM_TRIES] [--vqa_spsa_iter VQA_SPSA_ITER] [--vqa_cobyla_iter VQA_COBYLA_ITER] [--vqa_powell_iter VQA_POWELL_ITER]
                                 [--vqa_bfgs_iter VQA_BFGS_ITER]

options:
  -h, --help            show this help message and exit
  --verbose             Be verbose (debug logging)

MLFLOW:
  Mlflow settings

  --nomlflow            Do not log statistics with mlflow
  --log_system_metrics  Log cpu stats while running. E.g.: CPU usage, RAM usage, ...
  --run_name RUN_NAME   Set mlflow run name
  --uri URI             Mlflow server's URI

SA:
  Simulated Annealing Algorithm' settings

  --max_iterations MAX_ITERATIONS
                        Simulated Annealing max iterations
  --initial_temp INITIAL_TEMP
                        Simulated Annealing initial temperature (T) value
  --cooling_rate COOLING_RATE
                        Simulated Annealing cooling rate value
  --eval_file EVAL_FILE
                        TSP instance used to test Ansatz and retrieve fitness values
  --test_dir TEST_DIR   TSP instances' dir used to test pre-optimized Ansatz after SA algorithm.
  --qc_params {all,one_per_block}
                        Set the rotation block parameters:
                                - all           : use one argument per Gate
                                - one_per_block: use just one argument per Rotation block
                                

VQA:
  VQA Algorithm settings

  --vqa_optimize_once   Run the optimization phase just once at the end of Simulated Annealing.
                            This means that every fitness is computed without the optimization phase and when
                            the best ansatz is found, will be optimized (just once) !
                            
  --optimizers {cobyla,powell,bfgs,spsa} [{cobyla,powell,bfgs,spsa} ...]
                        List of optimizers to use while running the QC.
  --vqa_runs_per_instance VQA_RUNS_PER_INSTANCE
                        For each instance run n runs_per_instance independent experiments.
  --vqa_num_tries VQA_NUM_TRIES
                        Number of starting points to be optimized in each run.
  --vqa_spsa_iter VQA_SPSA_ITER
                        Number of iterations for SPA optimizer.
  --vqa_cobyla_iter VQA_COBYLA_ITER
                        Number of iterations for COBYLA optimizer.
  --vqa_powell_iter VQA_POWELL_ITER
                        Number of iterations for Powell optimizer
  --vqa_bfgs_iter VQA_BFGS_ITER
                        Number of iterations for BFGS optimizer

📝 Cite this work

If you use Freeze and Conquer 🧊 in your research, please make sure to cite our paper.

@misc{fagiolovescera2025freezeconquerreusableansatz,
      title={Freeze and Conquer: Reusable Ansatz for Solving the Traveling Salesman Problem}, 
      author={Fabrizio Fagiolo and Nicolò Vescera},
      year={2025},
      eprint={2508.21730},
      archivePrefix={arXiv},
      primaryClass={cs.AI},
      url={https://arxiv.org/abs/2508.21730}, 
}