CS Paper Radar

Quantum state preparation for weighted d-DNNF

Steef Hegeman, Joon Hyung Lee, Alfons Laarman

cs.DS quant-ph ·submitted 2026-10-01 17:24 UTC · v1

Abstract

The quantum state preparation problem is to, given a description of a quantum state, efficiently generate a quantum circuit computing the state. We show that for quantum states described by weighted d-DNNF (deterministic, decomposable pseudo-Boolean circuits) a quantum circuit computing the state can be obtained in linear time up to complex arithmetic.

Closest papers

Nearest neighbours by meaning across the whole index.

Toward Quantum Advantage in Learning Parities with Structured Noise via Lower Bound Optimization of the Condition Number

cs.CR ·2026-08-19 ·Yusen Han, Xuelian Li, Juntao Gao, Bo Song
theory similarity 0.63
Abstract · 21 pages, 9 figures

Learning Parities with Structured Noise (LPSN) can be reduced to solving nonlinear Boolean systems. In quantum computing, such systems are typically transformed into Macaulay linear systems and solved via quantum linear system algorithms, a process severely limited by the condition number. To address this, we propose a novel reduction method for Macaulay linear systems. Under the assumptions of Ding et al., we derive a condition number lower bound incorporating a scaling factor. This reduction not only guarantees efficient quantum state preparation but also exhibits a distinct advantage regarding the condition number interval relative to the reduced right-hand side vector, thereby reducing the lower bound of the condition number and ultimately optimizing the upper bound on the time complexity of the quantum algorithm for solving Boolean systems. Furthermore, applying this improved quantum algorithm to LPSN significantly reduces sample complexity by exploiting the Macaulay system's solution structure. We further provide a concrete logical-level quantum resource estimate, demonstrating that the optimized condition number translates directly into a reduction in circuit width, depth, and gate count. Finally, we establish an algorithm selection strategy by systematically comparing quantum and classical approaches across noise pattern adaptability, sample complexity, and time complexity. Results demonstrate that our quantum algorithm exhibits the potential to outperform classical counterparts under specific parameter regimes.

0.22

Computational Power of Clifford and Ising Quantum Computers

cs.CC quant-phmath.QA ·2026-11-09 ·Sawyer Dobson, Zhenghan Wang
theory similarity 0.61
Abstract · 52 pages, 26 figures

We extend the efficient classical simulation of Ising quantum computers from braidings to measurements. We investigate several different definitions of efficient Clifford quantum computation by varying the power of the circuit generator. In case the circuit generator can see the entire input, we give a detailed proof that efficient simulation of classical computation would imply the separation of complexity classes $\mathbf{P}$ and $\mathbf{PSPACE}$. If the circuit generator sees only the input length, we prove that Clifford quantum computers decide what we call affine languages.

0.30

A Dichotomy for Exact Quantum Circuit Amplitudes

cs.CC ·2026-11-17 ·Chenghua Liu, Boning Meng
similarity 0.61
Abstract

We classify the complexity of exactly computing computational-basis amplitudes for circuits over any fixed finite library of unitary qubit gates, with each gate allowed to act on any ordered tuple of distinct wires. Exact evaluation is polynomial-time computable if all gates permute the computational basis up to phases, all preserve product states, or all become Clifford under a common diagonal one-qubit unitary change of basis on every wire. For every other library, the problem is $\#\mathrm P$-hard under polynomial-time Turing reductions. Our proof connects circuit amplitudes to the Boolean Holant classification of tensor contractions on arbitrary graphs. For an algebraic library containing a nonmonomial gate and an entangling gate, we show how to simulate the joint use of a symmetric maximally entangled state and its adjoint at polynomial cost, using only amplitude queries over the original library. This lets us evaluate unrestricted contractions of the resulting gate and boundary tensors. Unitarity and the computational-basis boundaries then restrict the tractable cases to the three forms above. Algebraic specialization extends the dichotomy to arbitrary fixed complex gate entries under a symbolic exact-output convention.

0.31

Simulating Quantum Computation Using Probabilistic Programming

cs.PL ·2026-11-16 ·Yafei Yang, Chung-chieh Shan
theory similarity 0.60
Abstract · 33 pages, 8 figures

Developing quantum programs requires not only running them on quantum hardware but also simulating them on classical hardware. Because the meaning of a quantum program can be defined in terms of state vectors, it can be viewed as a form of weighted nondeterminism and simulated using any implementation of probabilistic programming that supports complex or at least negative weights. In this study, we compile a high-level quantum programming language to one such implementation of probabilistic programming, a solver for factor graph grammars. We also extend the solver with an optimization that commutes the tensor operations $\mathsf{einsum}$ and $\mathsf{expand}$. We prove that the compiler and the optimization preserve the denotational semantics of the source language. We perform benchmarks that show our straightforward implementation, by repurposing existing infrastructure for probabilistic programming, attains simulation performance in the ballpark of several other quantum simulators.

0.18

Staged Hybrid Quantum-Classical Programming

cs.PL cs.LO ·2026-09-06 ·Chuta Sano, Peng Fu, Ryan Kavanagh, Jennifer Paykin, Brigitte Pientka
theory similarity 0.60
Abstract

Hybrid quantum-classical computing systems consist of a classical control system that sends quantum circuits and receives measurement results from a quantum co-processor. Such systems allow us to model algorithms that require the classical control system to generate quantum circuits on the fly, potentially based on prior measurement results. This is challenging, as the classical control system must generate quantum circuits that manipulate live quantum states. In this setting, the classical control system is generating further quantum circuits while the quantum co-processor is internally maintaining the state of the live qubits; this is not ideal, since this not only is costly but also introduces additional sources of noise to the live qubits. Thus, we want to minimize the latency between receiving measurement results and sending the next quantum circuit to be executed by pre-computing quantum circuits. We introduce HyQ (pronounced haiku), a multi-modal language based on adjoint logic that pre-generates quantum circuits before executing a hybrid quantum-classical program. We achieve this by separating our semantics into two distinct stages: 1) compile-time generation of quantum circuits and classical runtime code and 2) execution of the classical runtime code that instruments the quantum co-processor. This separation between stages allows us to formally guarantee that all circuit-generation logic occurs before the instrumentation logic, i.e., the actual runtime, and minimizes the idling of the quantum co-processor at runtime. We give a type system, a circuit-normalization semantics for the compile-time stage, which eagerly performs all circuit-generation logic, and a runtime semantics for HyQ that corresponds to the second stage. We prove type preservation and progress for both semantics.

0.18

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

cs.AI cs.AR ·2026-09-04 ·Yoonju Sim, Federico Berto, Chuanbo Hua, Jinkyoo Park, Changhyun Kwon
publishedbenchmark similarity 0.60
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 \texttt{QuantumEvo}, an evolutionary framework that uses an LLM as a heuristic generator for QCC-aware BDD variable ordering. Instead of predicting orderings directly, \texttt{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.

0.40

Distributing Quantum Circuits Using Pre-Distributed Entanglement Pairs over Quantum Networks

cs.ET quant-ph ·2026-10-19 ·Yukun Yang, Ranjani G. Sundaram, Himanshu Gupta
publishedbenchmark similarity 0.60
Abstract · 9 pages, 4 figures. Full author version revised after acceptance; includes the cost-aware entanglement consumption section omitted from the …

Distributing quantum circuits across a network of quantum devices is a recent approach to improve the scalability of quantum computation. Entangled pairs of qubits distributed across network nodes are used as a communication resource for executing inter-node (remote) gates. However, establishing these entanglement pairs incurs significant latency, and doing so during the circuit's execution may lead to the decoherence of logical qubits. Instead, it may be beneficial to distribute certain entanglement pairs before the circuit is executed. Thus, we consider the problem of distributing a quantum circuit across a quantum network containing some pre-distributed entanglement pairs and seek to minimize the execution time of the circuit. We address this problem in three steps. First, given the quantum network and (optionally) a probability distribution over training circuits, we determine a set of pre-distributed entanglement pairs under a specified budget. Second, we compute a qubit-to-memory allocation that minimizes the expected execution time given these pre-distributed resources. Finally, we identify any additional entanglement pairs required during execution, generate them concurrently, and execute the circuit gates. We evaluate our methods on a broad range of benchmark circuits.

0.46

Factorized Boolean representations for efficient quantum synthesis

cs.LO quant-ph ·2026-08-27 ·Mehul Shah, Robert Fiszer, Marek Perkowski
code/data similarity 0.59
Abstract · 20 pages, 4 figures. Code and data: https://github.com/mehulshah225/Research_Project

Quantum algorithms promise advantages beyond classical reach, but running them on error-corrected hardware requires translating Boolean specifications into reversible circuits, and the resources that translation demands determine what is executable. Established methods minimize a Boolean expression and map it to a circuit, assuming the minimized form is best. Here we show that minimized expressions retain algebraic structure minimization cannot reach, arising from containment and complementary-polarity relationships among their terms, and that extracting it yields circuits cheaper to execute despite having more operations. The decisive quantity is not a circuit's operation count but the control count of its widest operation, a superlinear cost; extracting shared factors trades a few wide operations for many narrow ones and reduces qubit count. Across benchmarks and oracles from quantum search and factoring algorithms, at the representation level the transformation never increases either cost measure, a guarantee from its construction. Translation to an executable circuit returns part of that advantage, since auxiliary lines must be uncomputed, yet the factorized circuit still left a leading circuit-level optimizer reaching lower final counts, and faster, than unaided. The representation of a computation is therefore itself a resource, optimizable before compilation and distinct from both logic minimization and circuit-level optimization.

0.25