LLM-Driven Algorithm Design for Quantum Circuit Synthesis based on Binary Decision Diagrams

Yoonju Sim; Federico Berto; Chuanbo Hua; Jinkyoo Park; Changhyun Kwon

cs.AISep 4, 2026

LLM-Driven Algorithm Design for Quantum Circuit Synthesis based on Binary Decision Diagrams

Authors: Yoonju Sim, Federico Berto, Chuanbo Hua, Jinkyoo Park, Changhyun Kwon

Organizations: Department of Industrial and Systems Engineering, KAIST, Daejeon, 34141, Republic of Korea · Radical Numerics, California, USA · Omelet, Inc., Daejeon, 34051, Republic of Korea

Abstract

Quantum circuits are central to implementing quantum algorithms on quantum devices, where quantum gates must be reversible. Many quantum algorithms rely on Boolean functions, which must therefore be implemented reversibly within quantum circuits. Reversible circuit synthesis provides a way to translate such Boolean functions into reversible circuits. Binary decision diagrams (BDDs) offer a scalable approach to this task, but the resulting BDDs and circuits depend heavily on variable ordering. Existing ordering heuristics commonly minimize BDD size because it is closely tied to the circuit size. However, BDD size is an imperfect proxy for the quantum cost of the synthesized circuit (QCC). We propose QuantumEvo, an evolutionary framework that uses an LLM as a heuristic generator for QCC-aware BDD variable ordering. Instead of predicting orderings directly, QuantumEvo searches over ordering heuristics initialized from multiple heuristic families. Candidate heuristics directly manipulate variable orderings using standard BDD operations and are selected by downstream QCC. The discovered heuristic, HGA-QE, modifies the sifting step inside a genetic algorithm so that the procedure is better aligned with QCC. Across the benchmark set, HGA-QE achieves a 70.9% tie-or-win rate against the per-function best baseline and is strictly best on 13.5% of the functions. The results demonstrate broadly competitive QCC performance, with HGA-QE showing a clearer relative advantage in strict wins on the two benchmark suites drawn from sources different from the data used for heuristic discovery.

Figures & tables

Panel of Figure 1 — Figure 1: Impact of variable ordering on QCC for the function sf_232 . Solid/dashed edges denote 1/0-branches. BDD size is 8 for both orderings, whereas QCC is 43 for $\pi_{1}$ and 36 for $\pi_{2}$ . Here, $y=x_{2}\oplus x_{3}\oplus x_{4}\oplus x_{1}\cdot(x_{2}\oplus x_{3}\oplus x_{2}x_{3}\oplus x_{2}x_{4})$

Figure 2: Overview of the QuantumEvo framework. Each individual heuristic reorders the initial variable order of BDD, and the resulting circuit is evaluated using QCC.

Figure 3: Fitness of the best individual over iterations, showing the family transition at iteration 8. Lower values indicate better fitness.

Panel of Figure 4 — Algorithm 1 HGA-QE : Hybrid GA discovered by QuantumEvo . Subroutines PartialSift and MiniSift are defined in Section D.1 .

	QCC		BDD
Method	Mean Gap ( $\downarrow$ )	W/T/L	Mean Gap ( $\downarrow$ )	W/T/L	Total Time (s)
GA with sifting	2.096%	-	$-$ 0.211%	-	23.24
GA with MiniSift	0.532%	34/53/13	$-$ 0.350%	4/94/2	21.95
GA with MiniSift + local refinement	0.527%	34/53/13	$-$ 0.354%	4/94/2	22.01

Table 1: Comparison of GA variants on the search set using best-of-3 seeds. The mean gaps are signed percentage differences relative to the best known value per instance. The win/tie/loss counts are relative to GA with sifting.

Suite	Method	Best	Strict	Mean Best QCC	Mean Avg QCC	Mean Worst QCC
RevLib (96)	HGA-QE	70	6	1416.04	1434.31	1450.76
	SA	68	5	1416.25	1437.27	1463.44
	BDD2Seq	65	13	1456.03	–	–
	GA	58	1	1445.28	1457.55	1468.35
	SIFT	42	0	1767.24	–	–
	SYMM SIFT	41	0	1757.90	–	–

Table 2: Per-suite benchmark performance. Best includes ties for the lowest Best QCC; Strict is counted only when the method is the unique best (5 random seeds for stochastic methods).

Panel of Figure 5 — Figure 5: (a) Performance profile over the whole benchmark set, using the ratio between each method’s QCC and the best QCC achieved on the same function. (b) Quality–runtime Pareto curve over all 148 benchmark circuits. The $x$ -axis reports the geometric mean runtime ratio relative to the per-circuit fastest result, and the $y$ -axis reports the geometric mean relative QCC gap. Connected points correspond to cumulative run budgets for stochastic methods, whereas deterministic methods and BDD2Seq variants are shown as single points. Lower-left is better.

Circuit	I	O	QuantumEvo			GA			SA
			Best	Avg	Avg Time	Best	Avg	Avg Time	Best	Avg	Avg Time
apex5_104 R	117	88	9184	9812.40	0.97	9551	10041.40	1.24	9397	9809.00	1.97
apex6_orig L	135	99	3736	3787.20	0.65	4159	4368.40	0.64	4392	4551.40	1.08
apex7_orig L	49	37	1431	1440.60	0.28	1441	1443.40	0.58	1703	1759.20	0.44
b9_orig L	41	21	713	719.40	0.17	715	719.00	0.27	804	804.00	0.19
c432 I	36	7	10494	11053.20	245.19	11141	11170.60	6.20	11101	11148.60	1.46

Table 3: Compact comparison for functions where QuantumEvo is strictly best.

Panel of Figure 6 — Figure 6: Validation-set distributions over ten independent runs per setting. The star marks the run selected by the lowest validation QCC fitness; the corresponding win-or-tie rate is reported for the same run.

Initialization	Fitness	Guidance	Best/Total (%)	Strictly Best/Total (%)	Mean Best QCC	Mean Avg QCC	Mean Worst QCC
Sifting, GA, SA	QCC	LLM	70.9	13.5	1923.83	1979.76	2033.46
Sifting, GA, SA	QCC	Non-LLM	66.9	5.4	2075.15	2220.27	2432.07
GA	QCC	LLM	63.5	3.4	2061.84	2172.50	2264.26
SA	QCC	LLM	66.2	0.7	1949.11	2004.30	2084.68
Sifting	QCC	LLM	55.4	4.1	2203.34	2435.04	2670.19
Sifting, GA, SA	BDD size	LLM	61.5	5.4	1944.65	2003.03	2099.68

Table 4: Benchmark evaluation of the best-validation individual from each setting on the full benchmark set with five random seeds. Starting from the full QuantumEvo setting (bold), each block varies one factor: Guidance, Initialization, or Fitness.

Appendix figures & tables26 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 7 — Figure 7: A 3-bit reversible function and its synthesized NCT circuit.

Panel of Figure 8 — Figure 8: Impact of variable ordering on QCC for the function 4mod5_8 . Solid/dashed edges denote 1/0-branches. The BDD sizes are 9 under $\pi_{1}$ and 6 under $\pi_{2}$ , whereas the corresponding QCC values are 52 and 24. Here, $y=\overline{(x_{1}\oplus x_{3})}\cdot\overline{(x_{2}\oplus x_{4})}$

Hyperparameter	Value	Hyperparameter	Value
Max. function evaluations	200	Per-iteration timeout	40 s
Population size	10	Evaluation seeds per instance	3
Initial population size	30	Search instances	100
Mutation rate	0.5	Validation instances	50

Appendix

Table 5: Hyperparameters used for all runs.

Panel of Figure 9 — Figure 9: Structural comparison of the search set (100 functions) and the benchmark set (148 functions)

Family	Search dimension	Available choices or range
Top level	Heuristic family	Sifting / SA / GA. The initial population is divided evenly across the three families.
Sifting	Search direction	Bidirectional / top-down only / bottom-up only.
Sifting	Search range	Full variable range / sliding window with width $w\in\{2,\ldots,10\}$ / random subset containing $p\in[0.3,0.9]$ of the variables in each pass.
Simulated annealing	Neighborhood operators	Seed exchange–jump mixture / exchange only / jump only / adjacent swap only / all four move types.
	Move probabilities	Exchange probability $p_{\mathrm{exc}}\in[0.2,0.6]$ ; upward-jump share $p_{\mathrm{up}}\in[0.2,0.8]$ .
	Cooling schedule	Multiplicative cooling factor $\alpha\in[0.80,0.95]$ ; secondary temperature-scaling parameter $\beta\in[0.3,0.8]$ .

Appendix

Table 6: Search dimensions available to each heuristic family in the non-LLM evolutionary search.

Panel of Figure 10 — Figure 10: Validation comparison between the two LLM choices over ten independent runs. The star marks the run selected by the lowest validation QCC fitness.

Figure 11: Evolution of the Best Discovered Ordering Heuristic for the choice of gpt-5.4-mini

	Benchmark					Family Type
LLM choice	Best/Total (%)	Strictly Best/Total (%)	Mean Best QCC	Mean Avg QCC	Mean Worst QCC	GA	SA	Sifting
gpt-oss-120b	70.9	13.5	1923.83	1979.76	2033.46	1	9	0
gpt-5.4-mini	66.9	6.1	2080.71	2147.33	2211.11	2	3	5

Appendix

Table 7: Benchmark comparison of LLM choices. Family counts summarize the best individual selected in each of ten independent runs per model.

Panel of Figure 12 — Figure 12: Code-level family composition of valid individuals across iterations

Figure 13: Validation-set fitness of the top 5 and top 10 candidates ranked by search-set performance after pooling candidates across the 10 runs for each setting. Dashed lines separate the guidance, initialization, and fitness comparisons.

Analysis	Initialization	Fitness	Guidance	Rate
Search set	Multi-seed	QCC	gpt-oss-120b	5/10
Validation set	Multi-seed	QCC	gpt-oss-120b	9/10
			gpt-5.4-mini	2/10
			Non-LLM	1/10
	GA only	QCC	gpt-oss-120b	8/10
	SA only	QCC	gpt-oss-120b	Identical heuristic

Appendix

Table 8: Sensitivity over the original and nine alternate sets. Rates denote top ranking of HGA-QE among 30 candidates or reselection of the original validation finalist.

Budget fraction	Budget (s)	Failure rate
1.0 $\times$	40.0	8.3%
0.9 $\times$	36.0	9.0%
0.8 $\times$	32.0	9.8%
0.7 $\times$	28.0	11.6%
0.6 $\times$	24.0	14.1%
0.5 $\times$	20.0	17.7%

Appendix

Table 9: Candidate-evaluation failure rates under shorter timeout limits, based on the recorded wall times of evaluations from the 10 production runs.

Pseudocode	CUDD function	Source file	Type	Notes
Sift	cuddSifting	cuddReorder.c	W	—
SwapAdjacent	cuddSwapInPlace	cuddReorder.c	W	—
PMX	PMX	cuddGenetic.c	W	—
RouletteSelect	roulette	cuddGenetic.c	A	Spin range unified to popsize for both parent selections
PartialSift	build_dd	cuddGenetic.c	A	Replaces full cuddSifting with MiniSift over marked starting levels
RestoreOrder	restoreOrder	cuddAnneal.c	A	Reimplemented locally; based on annealing restore logic (cf. ddShuffle in cuddReorder.c )

Appendix

Table 10: Correspondence between pseudocode functions and CUDD source. W = wrapped (unmodified API call), A = adapted, N = new.

Statistic	Sifting	MiniSift	Change (%)	Wilcoxon $p$
Unique fraction	0.553	0.615	$+11.2\%$	$4.35{\times}10^{-11}$
Hamming fraction	0.507	0.537	$+5.9\%$	$1.04{\times}10^{-4}$
Child-node line preservation cases	999	983	$-1.6\%$	0.0100
Toffoli gates	3847	3797	$-1.3\%$	$4.70{\times}10^{-5}$
Total controls	10591	10479	$-1.1\%$	$4.98{\times}10^{-6}$
Total QCC	22550	22274	$-1.2\%$	$1.12{\times}10^{-6}$

Appendix

Table 11: Diagnostic comparison between the standard sifting and MiniSift . Diversity rows use all search-set functions and three seeds; the remaining rows use cases in which both methods produce the same BDD size but MiniSift lowers QCC. The change is relative to the standard sifting.

Panel of Figure 14 — Figure 14: A representative same-BDD-size example under sifting and MiniSift . Gray nodes are referenced by at least two parents and indicate candidate sites for child-node line preservation. MiniSift preserves the BDD size while eliminating one preservation case in the synthesis trace, reducing QCC.

Suite	Baseline	Mean $\Delta$ QCC	$p$ (raw)	$p$ (Holm)
RevLib (96)	SA	-0.21	0.571	0.571
	BDD2Seq	-39.99	0.008	0.025
	GA	-29.24	0.069	0.139
	SIFT	-351.20	$8.1\times 10^{-8}$	$\bm{3.2\times 10^{-7}}$
	SYMM_SIFT	-341.85	$5.0\times 10^{-8}$	$\bm{2.5\times 10^{-7}}$
	GROUP_SIFT	-272.52	$6.9\times 10^{-9}$	$\bm{4.1\times 10^{-8}}$

Appendix

Table 12: Paired Wilcoxon signed-rank tests comparing the per-circuit best QCC of HGA-QE with each baseline. The six comparisons within each suite are corrected using the Holm–Bonferroni procedure. Mean

\Delta

QCC is computed as HGA-QE minus the baseline, so negative values favor HGA-QE. Bold Holm-adjusted

p

-values indicate significance at

\alpha=0.05

Table 13: Comparison and breakdown of non-best cases.

Method	Stage	Success	Best	Strict	Mean Best	Mean Avg	Mean Worst	Geo-mean Runtime (s)
HGA-QE	Net. Size	49/52	47/49	5/49	217.39	222.12	227.86	0.066
HGA-QE	# LUT	49/52	30/48	3/48	83.46	87.45	91.73	3.036
SA	Net. Size	52/52	36/49	1/49	215.47	222.06	235.41	0.092
SA	# LUT	52/52	35/48	6/48	85.04	90.52	98.50	3.041
GA	Net. Size	52/52	42/49	1/49	274.24	1575.83	2564.90	0.080
GA	# LUT	50/52	30/48	4/48	83.38	87.24	90.35	3.060

Appendix

Table 14: Mux-network size and LUT-mapping results under a uniform 300s-per-seed budget for each stage. The Net. Size and # LUT rows use 49 and 48 complete-case circuits, respectively, for which all methods completed their required runs. Success reports each method’s full completion count over all 52 circuits. Best includes ties, whereas Strictly Best denotes a unique best result. Mean quality and geometric mean runtime values are computed over the same complete-case set within each stage.

LLM Calls	Input Tokens	Output Tokens	Wall-clock	Hardware
291.6	3.11M	1.04M	108.5 min	1 $\times$ NVIDIA RTX PRO 6000

Appendix

Table 15: Average offline search requirements of one QuantumEvo production run.

Figure 15: Distribution of per-candidate evaluation times for completed evaluations in the production setting. The dashed line indicates the 40 s timeout threshold.

Function	I	O	QuantumEvo			GA			SA
			Best	Avg $\pm$ Std	Time	Best	Avg $\pm$ Std	Time	Best	Avg $\pm$ Std	Time
4gt10_22	4	1	17	17.00 $\pm$ 0	0.04	17	17.00 $\pm$ 0	0.06	17	17.00 $\pm$ 0	0.05
4gt11_23	4	1	5	5.00 $\pm$ 0	0.06	5	5.00 $\pm$ 0	0.06	5	5.00 $\pm$ 0	0.05
4gt12_24	4	1	17	17.00 $\pm$ 0	0.06	17	17.00 $\pm$ 0	0.06	17	17.00 $\pm$ 0	0.06
4gt13_25	4	1	10	10.00 $\pm$ 0	0.06	10	10.00 $\pm$ 0	0.06	10	10.00 $\pm$ 0	0.05
4gt4_20	4	1	19	19.00 $\pm$ 0	0.06	19	19.00 $\pm$ 0	0.06	19	19.00 $\pm$ 0	0.06

Appendix

Table 16: Full benchmark results, RevLib functions, stochastic methods, part 1 of 2. Best and average QCC compared among QuantumEvo, GA, and SA; lowest values bold. Small values under Avg are

\pm

one standard deviation of QCC across that function’s 5 seeds.

Function	I	O	QuantumEvo			GA			SA
			Best	Avg $\pm$ Std	Time	Best	Avg $\pm$ Std	Time	Best	Avg $\pm$ Std	Time
ex3_152	5	1	38	40.00 $\pm$ 4	0.06	38	44.00 $\pm$ 4.90	0.06	38	45.00 $\pm$ 4	0.06
ex5p_154	8	63	1843	1843.00 $\pm$ 0	0.11	1843	1843.00 $\pm$ 0	0.11	1843	1843.00 $\pm$ 0	0.14
example2_156	10	6	1266	1276.80 $\pm$ 8.82	0.08	1269	1287.00 $\pm$ 11.22	0.09	1266	1278.80 $\pm$ 9.62	0.11
f2_158	4	4	108	111.00 $\pm$ 2.45	0.05	108	108.00 $\pm$ 0	0.05	113	113.00 $\pm$ 0	0.05
f51m_159	14	8	2422	2429.20 $\pm$ 4.21	0.14	2427	2429.40 $\pm$ 2.94	0.20	2422	2430.60 $\pm$ 4.32	0.25

Appendix

Table 17: Full benchmark results, RevLib functions, stochastic methods, part 2 of 2.

Function	I	O	QuantumEvo			GA			SA
			Best	Avg $\pm$ Std	Time	Best	Avg $\pm$ Std	Time	Best	Avg $\pm$ Std	Time
apex6_orig L	135	99	3736	3787.20 $\pm$ 36.31	0.65	4159	4368.40 $\pm$ 169.77	0.64	4392	4551.40 $\pm$ 148.45	1.08
apex7_orig L	49	37	1431	1440.60 $\pm$ 7.45	0.28	1441	1443.40 $\pm$ 2.94	0.58	1703	1759.20 $\pm$ 46.63	0.44
b1_orig L	3	4	22	23.00 $\pm$ 2	0.06	22	22.00 $\pm$ 0	0.05	22	22.00 $\pm$ 0	0.06
b9_orig L	41	21	713	719.40 $\pm$ 6.59	0.17	715	719.00 $\pm$ 3.58	0.27	804	804.00 $\pm$ 0	0.19
c17 I	5	2	37	37.00 $\pm$ 0	0.06	37	37.00 $\pm$ 0	0.06	37	37.00 $\pm$ 0	0.06

Appendix

Table 18: Full benchmark results, ISCAS85/89 and LGSynth91 functions, stochastic methods.

Function	QuantumEvo		BDD2Seq(B*)		BDD2Seq(E*)		SIFT		SYMM_SIFT		GROUP_SIFT
	Best	Time	Best	Time	Best	Time	Best	Time	Best	Time	Best	Time
4gt10_22	17	0.04	17	1.49	17	2.13	17	0.02	23	0.01	23	0.02
4gt11_23	5	0.06	5	0.05	5	0.01	5	0.01	5	0.01	5	0.03
4gt12_24	17	0.06	17	0.04	17	0.01	17	0.01	16	0.01	16	0.03
4gt13_25	10	0.06	10	0.05	10	0.01	10	0.01	10	0.01	10	0.03
4gt4_20	19	0.06	19	0.04	25	0.01	19	0.03	23	0.01	23	0.03

Appendix

Table 19: Full benchmark results, RevLib functions, prior baselines, part 1 of 2. Best QCC compared among QuantumEvo, BDD2Seq, and deterministic CUDD baselines; lowest values bold. BDD2Seq(B*) Time is hardware-adjusted to our platform; BDD2Seq(E*) Time is as originally reported.

Function	QuantumEvo		BDD2Seq(B*)		BDD2Seq(E*)		SIFT		SYMM_SIFT		GROUP_SIFT
	Best	Time	Best	Time	Best	Time	Best	Time	Best	Time	Best	Time
ex3_152	38	0.06	38	0.08	38	0.02	61	0.03	61	0.03	43	0.03
ex5p_154	1843	0.11	1837	0.17	1871	0.06	1843	0.04	1843	0.05	1843	0.05
example2_156	1266	0.08	1218	0.18	1415	0.03	1436	0.03	1436	0.03	1366	0.02
f2_158	108	0.05	108	0.05	113	0.01	113	0.03	113	0.03	113	0.02
f51m_159	2422	0.14	2427	0.46	2517	0.14	5392	0.05	5392	0.05	4603	0.05

Appendix

Table 20: Full benchmark results, RevLib functions, prior baselines, part 2 of 2.

Function	QuantumEvo		BDD2Seq(B*)		BDD2Seq(E*)		SIFT		SYMM_SIFT		GROUP_SIFT
	Best	Time	Best	Time	Best	Time	Best	Time	Best	Time	Best	Time
apex6_orig L	3736	0.65	3895	16.72	4021	0.16	4822	0.05	4810	0.03	4269	0.03
apex7_orig L	1431	0.28	1455	2.40	1456	0.07	2653	0.04	2653	0.04	2377	0.04
b1_orig L	22	0.06	22	0.04	22	0.01	22	0.03	22	0.03	22	0.03
b9_orig L	713	0.17	737	1.71	737	0.05	804	0.03	810	0.03	836	0.03
c17 I	37	0.06	37	0.06	49	0.01	49	0.03	49	0.03	37	0.03

Appendix

Table 21: Full benchmark results, ISCAS85/89 and LGSynth91 functions, prior baselines.

Quantum Circuit Compilation

Quantum circuit compilation translates quantum algorithms into hardware-compatible circuits while reducing resource costs and preserving their behavior.

See all 21 papers

Discovering state-of-the-art quantum circuits with large language models
Oct 15, 2026Andi Gu, Alek H. Kemeny, Susanne F. Yelin +1Large Language Model-Guided Optimization
Harvard Quantum Initiative for Science and Engineering, Cambridge, MA 02138, USA · Department of Physics, Harvard University, Cambridge, MA 02138, USA · Anthropic STEM Fellows Program +2
Evolutionary Discovery of Bivariate Bicycle Codes with LLM-Guided Search
Jun 1, 2026Juan Cruz-Benito, Andrew W. Cross, David Kremer +1Automated Algorithm Discovery Quantum Error Correction
IBM Research, IBM T. J. Watson Research Center, NY, USA
Beyond Reinforcement Learning: Fast and Scalable Quantum Circuit Synthesis
Feb 16, 2026Lukas Theißinger, Thore Gerlach, David Berghaus +1Quantum Circuit Compilation
University of Bonn · European Space Agency, Advanced Concepts Team · Fraunhofer IAIS

Oct 15, 2026J/K move · Enter open · S save

Discovering state-of-the-art quantum circuits with large language models

Andi Gu, Alek H. Kemeny, Susanne F. Yelin, Mikhail D. Lukin

Harvard Quantum Initiative for Science and Engineering, Cambridge, MA 02138, USA · Department of Physics, Harvard University, Cambridge, MA 02138, USA · Anthropic STEM Fellows Program+2

Large Language Model-Guided Optimization

Open paper AskPDF arXiv

Significant efforts are currently being directed toward the implementation of large-scale quantum information processors, but realizing useful quantum advantage also requires the development of efficient quantum algorithms. While for many practical problems the dominant resource costs are associated with a small set of computational primitives, optimizing them in the quantum setting presents unique challenges, including a reversibility constraint absent from ordinary classical computation. Here we introduce an evolutionary framework in which large language models (LLMs) propose circuit designs and an independent evaluator verifies and scores them. We apply this framework to tasks spanning numerical computation, chemistry, optimization, quantum simulation, and number theory. In seven of the eight tasks, the discovered circuits significantly reduce both Toffoli and qubit counts relative to the state of the art. In the eighth, the search discovers a new reversible architecture for prime-field modular inversion. By handling reversibility differently, the architecture makes divsteps -- a classical algorithm previously impractical for reversible integer arithmetic -- viable and substantially improves the Toffoli-qubit trade-off for modular inversion. These results open the door for evaluator-guided LLM co-design of new algorithmic structures for quantum computation.

Abstract

Quantum Circuit Compilation

Explore similar work

Discovering state-of-the-art quantum circuits with large language models

Evolutionary Discovery of Bivariate Bicycle Codes with LLM-Guided Search

Beyond Reinforcement Learning: Fast and Scalable Quantum Circuit Synthesis