Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2603.16527

Logarithmic-depth quantum state preparation of polynomials

Baptiste Claudon, Alexis Lucas, Jean-Philip Piquemal, César Feniou, Julien Zylberman

quant-phSubmitted Mar 17, 2026• Announced Mar 18, 2026• 0 citations• Revised Oct 29, 2026 (v5)
v1 · Mar 17, 2026v2 · Mar 18, 2026v3 · Mar 25, 2026v4 · Oct 16, 2026v5 · Oct 29, 2026
arXivHTMLPDF

Abstract

Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree$-d$ polynomial, using circuits with logarithmic depth in the number $n$ of qubits and only $\mathcal O(n)$ ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only $n$ terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state $|1\rangle$. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using $14$ qubits and more than $500$ primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.

Related papers

Efficient circuits for leaf-separable state preparation

Sunil Vittal, Anthony Wilkie, Nika Rastegari +2 more

Efficient state preparation is a challenging and important problem in quantum computing. In this work, we present a recursive state preparation algorithm that combines logarithmic-depth Dicke state circuits with Hamming weight encoders for efficiently preparing ``leaf-separable" quantum states. The algorithm is built on binary partition trees, generalized weight distribution blocks (gWDBs), and leaf-level encoders. We evaluate the performance of the algorithm by numerically simulating it on randomly generated target states with between 4 and 15 qubits. Compared to general state preparation approaches which require $O(2^n)$ CX gates, our algorithm achieves a circuit depth of $O(k\log\frac{n}{k} + 2^k)$ and uses $O(n(k+2^k))$ two-qubit gates, where $k < n$ denotes the subtree size. We also compare implementations of the algorithm with and without the use of ancilla qubits, providing a detailed analysis of the trade-offs in circuit depth and two-qubit gate counts. These results contribute to scalable state preparation for quantum algorithms that require structured inputs such as Dicke or near-Dicke states.

quant-pharXiv:2511.11227•Nov 17, 2025•0 citations

Practical block encodings of matrix polynomials that can also be trivially controlled

Martina Nibbi, Filippo Della Chiara, Yizhi Shen +2 more

Quantum circuits naturally implement unitary operations on input quantum states. However, non-unitary operations can also be implemented through "block encodings", where additional ancilla qubits are introduced and later measured. While block encoding underlies a host of well-established theoretical applications, its implementation in practice has been prohibitively expensive for current quantum hardware. In this paper, we present practical and explicit block encoding circuits implementing matrix polynomial transformations of a target matrix. With standard approaches, block-encoding a degree-d matrix polynomial requires a circuit depth scaling as d times the depth for block-encoding the original matrix alone. By leveraging the recently introduced Fast One-Qubit Controlled Select Linear Combination of Unitaries (FOQCS-LCU) framework, we show that the additional circuit-depth overhead required for encoding matrix polynomials can be reduced to scale linearly in d with no dependence on system size or the cost of block encoding the original matrix. Moreover, we demonstrate that the FOQCS-LCU circuits and their associated matrix polynomial transformations can be controlled with negligible overhead, enabling efficient applications such as Hadamard tests. Finally, we provide explicit hardware-efficient circuits for representative non-unitary operators, namely quantum spin models, together with detailed non-asymptotic gate counts and circuit depths.

quant-pharXiv:2601.18767•Jan 27, 2026•0 citations

Constant-Depth Unitary Preparation of Dicke States

Malvika Raj Joshi, Francisca Vasconcelos

Dicke states serve as a critical resource in quantum metrology, communication, and computation. However, unitary preparation of Dicke states is limited to logarithmic depth in standard circuit models and existing constant-depth protocols require measurement and feed-forward. In this work, we present the first unitary, constant-depth protocols for exact Dicke state preparation. We overcome the logarithmic-depth barrier by moving beyond the standard circuit model and leveraging global interactions (native to architectures such as neutral atoms and trapped ions). Specifically, utilizing unbounded CZ gates (i.e. within the QAC$^0$ circuit class), we offer circuits for exact computation of constant-weight Dicke states, using polynomial ancillae, and approximation of weight-1 Dicke states (i.e. $W$ states), using only constant ancillae. Granted additional access to the quantum FAN-OUT operation (i.e. upgrading to the QAC$_f^0$ circuit class), we also achieve exact and clean preparation of arbitrary-weight Dicke states, with polynomial ancillae. These protocols distinguish the constant-depth capabilities of quantum architectures based on connectivity and offer a novel path toward resolving a long-standing quantum complexity conjecture.

quant-pharXiv:2601.10693•Jan 16, 2026•0 citations

Hermitian Matrix Function Synthesis without Block-Encoding

Anuradha Mahasinghe, Kaushika De Silva, Xavier Cadet +3 more

Implementing polynomial functions of Hermitian matrices on quantum hardware is a foundational task in quantum computing, critical for accurate Hamiltonian simulation, quantum linear system solving, high-fidelity state preparation, machine learning kernels, and other advanced quantum algorithms. Existing state-of-the-art techniques, including Qubitization, Quantum Singular Value Transformation (QSVT), and Quantum Signal Processing (QSP), rely heavily on block-encoding the Hermitian matrix. These methods are often constrained by the complexity of preparing the block-encoded state, the overhead associated with the required ancillary qubits, or the challenging problem of angle synthesis for the polynomial's phase factors, which limits the achievable circuit depth and overall efficiency. In this work, we propose a novel and resource-efficient approach to implement arbitrary polynomials of a Hermitian matrix by leveraging the Generalized Quantum Signal Processing (GQSP) framework. Our method circumvents the need for block-encoding and avoids the compounding post-selection overheads characteristic of LCU-based constructions, achieving a stable, degree-independent success probability. We derive closed-form expressions for symmetric polynomial expansions and demonstrate how linear combinations of GQSP circuits can realize the desired transformation. This approach reduces resource overhead and opens new pathways for quantum algorithm design for functions of Hermitian matrices, particularly in settings where the Hermitian operator arises naturally from symmetric combinations of unitaries.

quant-pharXiv:2512.18249•Dec 23, 2025•0 citations

Efficient quantum amplitude encoding of polynomial functions

Javier Gonzalez-Conde, Thomas W. Watts, Pablo Rodriguez-Grasa +1 more

Loading functions into quantum computers represents an essential step in several quantum algorithms, such as quantum partial differential equation solvers. Therefore, the inefficiency of this process leads to a major bottleneck for the application of these algorithms. Here, we present and compare two efficient methods for the amplitude encoding of real polynomial functions on n qubits. This case holds special relevance, as any continuous function on a closed interval can be uniformly approximated with arbitrary precision by a polynomial function. The first approach relies on the matrix product state representation (MPS). We study and benchmark the approximations of the target state when the bond dimension is assumed to be small. The second algorithm combines two subroutines. Initially we encode the linear function into the quantum registers either via its MPS or with a shallow sequence of multi-controlled gates that loads the linear function's Hadamard-Walsh series, and we explore how truncating the Hadamard-Walsh series of the linear function affects the final fidelity. Applying the inverse discrete Hadamard-Walsh transform converts the state encoding the series coefficients into an amplitude encoding of the linear function. Thus, we use this construction as a building block to achieve an exact block encoding of the amplitudes corresponding to the linear function on k0 qubits and apply the quantum singular value transformation that implements a polynomial transformation to the block encoding of the amplitudes. This unitary together with the Amplitude Amplification algorithm will enable us to prepare the quantum state that encodes the polynomial function on k0 qubits. Finally we pad n−k0 qubits to generate an approximated encoding of the polynomial on n qubits, analyzing the error depending on k0 . In this regard, our methodology proposes a method to improve the state-of-the-art complexity by introducing controllable errors.

arXiv:2307.10917•Quantum•Mar 21, 2024•40 citations

Quantum space-depth tradeoffs for coherent block encodings

Yuxin Zhang, Changpeng Shao

Block encodings are a basic interface between quantum algorithms and linear algebra. Standard LCU constructions achieve optimal circuit depth but typically require logarithmically many ancilla qubits. We ask how much quantum workspace can be reduced without sacrificing circuit depth, and study this tradeoff from both algorithmic and lower-bound perspectives. For a Hermitian decomposition $A=\sum_{j=1}^L α_j H_j$, with $\|H_j\|=1$ and $α=\sum_j|α_j|$, we give two coherent $\varepsilon$-approximate block-encoding constructions. The first uses one ancilla qubit and has depth $\widetilde O(L(α/\varepsilon)^{o(1)})$, while the second uses $O(\log\log(α/\varepsilon))$ ancillas and achieves depth $\widetilde O(L)$. For a broad Suzuki-based coherent simulation architecture, we prove an ancilla-depth tradeoff. In the polynomial-resource regime and for a constant number of coherent rounds, $\log(1/\varepsilon)\le O((\log Q)^2+2^a\log Q)$, where $Q$ is depth normalized by the number of Hamiltonian terms and $a$ is the ancilla count. Thus polylogarithmic dependence on $1/\varepsilon$ requires more than constantly many ancillas within this architecture. In a separate repeated-query LCU model, for balanced coefficients $1/L$ and error $\varepsilon=η/L$ with fixed $0<η<1$, we prove $2^a=Ω_η(L^2/(T+L))$, where $T$ is the number of oracle queries. Hence $a=Ω(\log L)$ when $T=O(L^α)$ for some $α<2$. Moreover, in the exact case, $a\ge \log L$ regardless of $T$. We also extend this tradeoff to arbitrary nonnegative coefficients. Finally, we apply our low-ancilla constructions to normalized trace estimation in DQC1, obtaining an optimal algorithm linear in the approximate degree together with a matching query lower bound. Together, these results establish quantitative space-depth and space-query tradeoffs in two natural circuit models.

quant-pharXiv:2607.01843•Jul 3, 2026•0 citations
Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree−d-d−d polynomial, using circuits with logarithmic depth in the number nnn of qubits and only O(n)\mathcal O(n)O(n) ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only nnn terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state ∣1⟩|1\rangle∣1⟩. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using 141414 qubits and more than 500500500 primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.
Efficient state preparation is a challenging and important problem in quantum computing. In this work, we present a recursive state preparation algorithm that combines logarithmic-depth Dicke state circuits with Hamming weight encoders for efficiently preparing ``leaf-separable" quantum states. The algorithm is built on binary partition trees, generalized weight distribution blocks (gWDBs), and leaf-level encoders. We evaluate the performance of the algorithm by numerically simulating it on randomly generated target states with between 4 and 15 qubits. Compared to general state preparation approaches which require O(2n)O(2^n)O(2n) CX gates, our algorithm achieves a circuit depth of O(klog⁡nk+2k)O(k\log\frac{n}{k} + 2^k)O(klogkn​+2k) and uses O(n(k+2k))O(n(k+2^k))O(n(k+2k)) two-qubit gates, where k<nk < nk<n denotes the subtree size. We also compare implementations of the algorithm with and without the use of ancilla qubits, providing a detailed analysis of the trade-offs in circuit depth and two-qubit gate counts. These results contribute to scalable state preparation for quantum algorithms that require structured inputs such as Dicke or near-Dicke states.
Quantum circuits naturally implement unitary operations on input quantum states. However, non-unitary operations can also be implemented through "block encodings", where additional ancilla qubits are introduced and later measured. While block encoding underlies a host of well-established theoretical applications, its implementation in practice has been prohibitively expensive for current quantum hardware. In this paper, we present practical and explicit block encoding circuits implementing matrix polynomial transformations of a target matrix. With standard approaches, block-encoding a degree-d matrix polynomial requires a circuit depth scaling as d times the depth for block-encoding the original matrix alone. By leveraging the recently introduced Fast One-Qubit Controlled Select Linear Combination of Unitaries (FOQCS-LCU) framework, we show that the additional circuit-depth overhead required for encoding matrix polynomials can be reduced to scale linearly in d with no dependence on system size or the cost of block encoding the original matrix. Moreover, we demonstrate that the FOQCS-LCU circuits and their associated matrix polynomial transformations can be controlled with negligible overhead, enabling efficient applications such as Hadamard tests. Finally, we provide explicit hardware-efficient circuits for representative non-unitary operators, namely quantum spin models, together with detailed non-asymptotic gate counts and circuit depths.
Dicke states serve as a critical resource in quantum metrology, communication, and computation. However, unitary preparation of Dicke states is limited to logarithmic depth in standard circuit models and existing constant-depth protocols require measurement and feed-forward. In this work, we present the first unitary, constant-depth protocols for exact Dicke state preparation. We overcome the logarithmic-depth barrier by moving beyond the standard circuit model and leveraging global interactions (native to architectures such as neutral atoms and trapped ions). Specifically, utilizing unbounded CZ gates (i.e. within the QAC0^00 circuit class), we offer circuits for exact computation of constant-weight Dicke states, using polynomial ancillae, and approximation of weight-1 Dicke states (i.e. WWW states), using only constant ancillae. Granted additional access to the quantum FAN-OUT operation (i.e. upgrading to the QACf0_f^0f0​ circuit class), we also achieve exact and clean preparation of arbitrary-weight Dicke states, with polynomial ancillae. These protocols distinguish the constant-depth capabilities of quantum architectures based on connectivity and offer a novel path toward resolving a long-standing quantum complexity conjecture.
Implementing polynomial functions of Hermitian matrices on quantum hardware is a foundational task in quantum computing, critical for accurate Hamiltonian simulation, quantum linear system solving, high-fidelity state preparation, machine learning kernels, and other advanced quantum algorithms. Existing state-of-the-art techniques, including Qubitization, Quantum Singular Value Transformation (QSVT), and Quantum Signal Processing (QSP), rely heavily on block-encoding the Hermitian matrix. These methods are often constrained by the complexity of preparing the block-encoded state, the overhead associated with the required ancillary qubits, or the challenging problem of angle synthesis for the polynomial's phase factors, which limits the achievable circuit depth and overall efficiency. In this work, we propose a novel and resource-efficient approach to implement arbitrary polynomials of a Hermitian matrix by leveraging the Generalized Quantum Signal Processing (GQSP) framework. Our method circumvents the need for block-encoding and avoids the compounding post-selection overheads characteristic of LCU-based constructions, achieving a stable, degree-independent success probability. We derive closed-form expressions for symmetric polynomial expansions and demonstrate how linear combinations of GQSP circuits can realize the desired transformation. This approach reduces resource overhead and opens new pathways for quantum algorithm design for functions of Hermitian matrices, particularly in settings where the Hermitian operator arises naturally from symmetric combinations of unitaries.
Loading functions into quantum computers represents an essential step in several quantum algorithms, such as quantum partial differential equation solvers. Therefore, the inefficiency of this process leads to a major bottleneck for the application of these algorithms. Here, we present and compare two efficient methods for the amplitude encoding of real polynomial functions on n qubits. This case holds special relevance, as any continuous function on a closed interval can be uniformly approximated with arbitrary precision by a polynomial function. The first approach relies on the matrix product state representation (MPS). We study and benchmark the approximations of the target state when the bond dimension is assumed to be small. The second algorithm combines two subroutines. Initially we encode the linear function into the quantum registers either via its MPS or with a shallow sequence of multi-controlled gates that loads the linear function's Hadamard-Walsh series, and we explore how truncating the Hadamard-Walsh series of the linear function affects the final fidelity. Applying the inverse discrete Hadamard-Walsh transform converts the state encoding the series coefficients into an amplitude encoding of the linear function. Thus, we use this construction as a building block to achieve an exact block encoding of the amplitudes corresponding to the linear function on k0 qubits and apply the quantum singular value transformation that implements a polynomial transformation to the block encoding of the amplitudes. This unitary together with the Amplitude Amplification algorithm will enable us to prepare the quantum state that encodes the polynomial function on k0 qubits. Finally we pad n−k0 qubits to generate an approximated encoding of the polynomial on n qubits, analyzing the error depending on k0 . In this regard, our methodology proposes a method to improve the state-of-the-art complexity by introducing controllable errors.
Block encodings are a basic interface between quantum algorithms and linear algebra. Standard LCU constructions achieve optimal circuit depth but typically require logarithmically many ancilla qubits. We ask how much quantum workspace can be reduced without sacrificing circuit depth, and study this tradeoff from both algorithmic and lower-bound perspectives. For a Hermitian decomposition A=∑j=1LαjHjA=\sum_{j=1}^L α_j H_jA=∑j=1L​αj​Hj​, with ∥Hj∥=1\|H_j\|=1∥Hj​∥=1 and α=∑j∣αj∣α=\sum_j|α_j|α=∑j​∣αj​∣, we give two coherent ε\varepsilonε-approximate block-encoding constructions. The first uses one ancilla qubit and has depth O~(L(α/ε)o(1))\widetilde O(L(α/\varepsilon)^{o(1)})O(L(α/ε)o(1)), while the second uses O(log⁡log⁡(α/ε))O(\log\log(α/\varepsilon))O(loglog(α/ε)) ancillas and achieves depth O~(L)\widetilde O(L)O(L). For a broad Suzuki-based coherent simulation architecture, we prove an ancilla-depth tradeoff. In the polynomial-resource regime and for a constant number of coherent rounds, log⁡(1/ε)≤O((log⁡Q)2+2alog⁡Q)\log(1/\varepsilon)\le O((\log Q)^2+2^a\log Q)log(1/ε)≤O((logQ)2+2alogQ), where QQQ is depth normalized by the number of Hamiltonian terms and aaa is the ancilla count. Thus polylogarithmic dependence on 1/ε1/\varepsilon1/ε requires more than constantly many ancillas within this architecture. In a separate repeated-query LCU model, for balanced coefficients 1/L1/L1/L and error ε=η/L\varepsilon=η/Lε=η/L with fixed 0<η<10<η<10<η<1, we prove 2a=Ωη(L2/(T+L))2^a=Ω_η(L^2/(T+L))2a=Ωη​(L2/(T+L)), where TTT is the number of oracle queries. Hence a=Ω(log⁡L)a=Ω(\log L)a=Ω(logL) when T=O(Lα)T=O(L^α)T=O(Lα) for some α<2α<2α<2. Moreover, in the exact case, a≥log⁡La\ge \log La≥logL regardless of TTT. We also extend this tradeoff to arbitrary nonnegative coefficients. Finally, we apply our low-ancilla constructions to normalized trace estimation in DQC1, obtaining an optimal algorithm linear in the approximate degree together with a matching query lower bound. Together, these results establish quantitative space-depth and space-query tradeoffs in two natural circuit models.