Quantum circuit built fast from weighted d-DNNF state descriptions
Quantum state preparation for weighted d-DNNF
Data Structures and Algorithms
Summary
Making a quantum computer perform a certain task often starts with preparing a specific quantum state. This paper shows that when a quantum state can be described using a special kind of mathematical structure called weighted d-DNNF, it’s possible to create the quantum instructions needed very quickly. The authors prove this process can be done in time proportional to the size of that description, making it more efficient than some previous methods. This helps simplify part of building quantum algorithms for states described this way.
What this means in practice
- •For quantum software developers: Generate quantum circuits efficiently for states described by weighted d-DNNF to speed up algorithm implementation.
- •For optimization algorithm engineers: Use the linear-time state preparation for weighted d-DNNF to design faster quantum heuristics in combinatorial optimization.
A theory result. No direct application yet.
Authors
Steef Hegeman, Joon Hyung Lee, Alfons Laarman
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.