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

Reflection-symmetric diagonal synthesis: resolving a conjecture of Huang, Kosugi, Nishi and Matsushita

Haobo Ma, Wenlin Zhang

Published Nov 2, 2026• 0 citations
Publisher

Abstract

Combined with the upper bound of Huang, Kosugi, Nishi and Matsushita [J. Phys. Soc. Jpn. 93, 054002 (2024); arXiv:2310.06676v2], this resolves their Section 6 conjecture that 2^(2n-1)+2n-2 CNOTs are optimal in the worst case for exact ancilla-free CNOT/R_z synthesis of reflection-symmetric diagonal unitaries on 2n qubits. The explicit hard instance has phase pi/2 at the all-zero and all-one strings. Multiplicative characters force every nonzero even parity; birth-span dimension and return conservation give the linear term. The same substitution gives the unrestricted 2dn-wire count, but not depth optimality or radial-potential optimality.

DOI
10.5281/zenodo.23885960

Related papers

Ancilla-Free Parity Network Synthesis is NP-complete

Long Do Duc, An Duc

A parity network is a CNOT circuit in which every parity from a prescribed set S appears on some wire; such networks are the CNOT skeletons of phase-polynomial circuits. Amy, Azimzadeh and Mosca (Quantum Science and Technology, 2018) left open the ancilla-free problem with arbitrary output. We prove that deciding whether S admits such a network with at most K CNOTs is NP-complete, even if every CNOT must produce a new parity, all parities share a variable and have weight at most five, and connectivity is a star. Hence CNOT minimization of phase polynomials is NP-hard even with a free linear part. The reduction is from Hamiltonian cycle in grid graphs: networks meeting the trivial lower bound are path covers with at most one path per wire, and chaining many copies of the instance makes a missing Hamiltonian path cost more paths than there are wires. We also show that unrestricted networks can be shorter than fixed-target ones by a factor linear in the number of qubits. This is a preprint; it has not been peer reviewed.

•Oct 4, 2026•0 citations

Asymptotically optimal circuits for arbitrary n-qubit diagonal computations

Stephen S. Bullock, Igor L. Markov

A unitary operator $U=\sum_{j,k} u_{j,k} \ket{k} \bra{j}$ is called \emph{diagonal} when $u_{j,k}=0$ unless $j=k$. The definition extends to quantum computations, where $j$ and $k$ vary over the $2^n$ binary expressions for integers $0,1 \cdots ,2^n-1$, given $n$ qubits. Such operators do not affect outcomes of the projective measurement $\{ \ket{j}\bra{j} \; ; \; 0 \leq j \leq 2^n-1\}$ but rather create arbitrary relative phases among the computational basis states $\{ \ket{j} \; ; \; 0 \leq j \leq 2^n-1\}.

Quantum Information and Computation•Jan 1, 2004•74 citations

Mid-circuit measurements and feedforward implement every unitary exactly in constant depth

Chenfeng Cao

Mid-circuit measurements with feedforward reduce the optimal worst-case quantum depth for exact $n$-qubit unitary synthesis from $Θ(n)$ to $O(1)$, using arbitrary one- and two-qubit gates and unrestricted ancillary space. Measurements and resets without feedforward remain subject to the circuit causal-cone bound. Our deterministic construction uses single-qubit measurements, $O(1)$ rounds of parity feedforward, and $O(n4^n\log(n+2))$ total qubits, with all ancillas starting and ending in $|0\rangle$. Classical processing is not counted in quantum depth. We teleport only the matrix error of an approximation by Nehoran and Yuen. An exactly prepared ancillary state encodes this error, whose action is added back by coherent interference. At operator-norm error $2^{-n}$, one step of amplitude amplification suffices. Coherent fanout circuits achieve the same constant-depth bound, while circuits using only one- and two-qubit gates attain depth $Θ(n)$ with $O(4^n\log^2(n+2))$ gates. Generic targets require $Ω(4^n/(h+1))$ qubits at depth $h$, even under unrestricted classical control. Our depth-width trade-offs meet this bound within a factor $O(n^2)$ for $1\le h\le2^n$.

quant-pharXiv:2610.06551•Oct 6, 2026•1 citation

Symmetry-Adapted Synthesis of the 24-Cell Quantum Reader

Masanori Watabe, Claude Opus 4.8 Kurado

Prior work by the authors [1] showed that the 24 vertices of the 24-cell, as unit quaternions, form the binarytetrahedral group 2T, that a controlled probe lifts the phase-blind projective group 2T/{±1} to all 24 gates, and thatthe optimal single-shot measurement discriminating them compiles, gate by gate, to an explicit RY/RZ/X/CNOTcircuit. That compilation was symmetry-blind: a textbook Givens synthesis of a generic 32×32 unitary, emitting25,210 CNOTs. Here we ask what the group structure of the input buys back. We report four findings. (A) The 24controlled-probe states span only a rank-3 subspace, so a reader need be correct only there; restricting thesynthesis to that support cuts the emitted CNOT count from 25,210 to 5,980 (4.2×) with the same single-shotarchitecture and the identical optimum. (B) The optimal POVM is exactly 2T-covariant: its 24 elements are onegroup orbit of a single seed, and the analysis map is a genuine tight-frame isometry that intertwines the supportrepresentation with the regular representation of 2T. (C) Consequently the reader factors as a data-independent2T group-Fourier transform followed by a placement whose data-dependent part is tiny (72 CNOT); the rank-3signal occupies just 5 of the 24 Fourier lines, which is the structural reason (A) works. (D, honest negative) Acheap synthesis of that group-Fourier transform is not achieved: the naive tensor product of the C3 and Q8transforms fails to block-diagonalize because 2T = Q8 : C3 is a crossed product, and the missing twiddle absorbsall the cost. We make no quantum-advantage claim; every number is a real emitted gate count or a verified matrixidentity from exact, numpy-only statevector simulation. ※ The license for codes is AGPL3.0-or-later

•Aug 27, 2026•2 citations

Optimal T-Count for Block Encodings of Fermionic and Spin Hamiltonians

Jiaxin Ma, Kevin J. Joven, Yuan Liu

We determine the non-Clifford $T$-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford$+T$ model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an $n$-qubit operator with $a$ clean ancillas and at most $s$ $T$ gates can be compressed to use at most $\min\{a,n+2s\}$ ancillas, without increasing the absolute error or $T$-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error $ε$, a volume-covering argument combined with circuit counting gives the worst-case lower bound $Ω(n^2\sqrt{\log(n^4/ε)})$, matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on $n$ spins, we obtain independent lower bounds $Ω(n)$ from stabilizer nullity and $Ω(\log(1/ε))$ from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling $Θ(n+\log(1/ε))$. As an application, we evaluate the $T$-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation $T$-count scales as the query count times the optimal $T$-count per query.

quant-pharXiv:2609.11153•Sep 11, 2026•1 citation

An optimal lower bound for the low density Fermi gas

Emanuela L. Giacomelli

We consider a dilute Fermi gas in three dimensions interacting through a positive, radially symmetric, compactly supported, and integrable potential in the thermodynamic limit. We establish a second-order lower bound for the ground-state energy density, with an error term that is optimal in the sense that it matches the order of the next correction term conjectured by Huang and Yang [Phys. Rev. 105, 767–775 (1957)]. Although a first rigorous derivation of the Huang–Yang formula has recently been obtained in the combined papers [Giacomelli et al. CPAM, e70040 (2026), Giacomelli et al.arXiv:2505.22340], the present work takes a different approach, inspired by the construction of suitable trial states introduced in Giacomelli et al. [CPAM, e70040 (2026)]. In particular, we provide a simple proof that is effective enough to yield the optimal error bound, by adapting the argument originally used to establish the upper bound on the energy density in Giacomelli et al. [CPAM, e70040 (2026)].

arXiv:2410.08904•Journal of Mathematical Physics•Apr 1, 2026•12 citations
Combined with the upper bound of Huang, Kosugi, Nishi and Matsushita [J. Phys. Soc. Jpn. 93, 054002 (2024); arXiv:2310.06676v2], this resolves their Section 6 conjecture that 2^(2n-1)+2n-2 CNOTs are optimal in the worst case for exact ancilla-free CNOT/R_z synthesis of reflection-symmetric diagonal unitaries on 2n qubits. The explicit hard instance has phase pi/2 at the all-zero and all-one strings. Multiplicative characters force every nonzero even parity; birth-span dimension and return conservation give the linear term. The same substitution gives the unrestricted 2dn-wire count, but not depth optimality or radial-potential optimality.
A parity network is a CNOT circuit in which every parity from a prescribed set S appears on some wire; such networks are the CNOT skeletons of phase-polynomial circuits. Amy, Azimzadeh and Mosca (Quantum Science and Technology, 2018) left open the ancilla-free problem with arbitrary output. We prove that deciding whether S admits such a network with at most K CNOTs is NP-complete, even if every CNOT must produce a new parity, all parities share a variable and have weight at most five, and connectivity is a star. Hence CNOT minimization of phase polynomials is NP-hard even with a free linear part. The reduction is from Hamiltonian cycle in grid graphs: networks meeting the trivial lower bound are path covers with at most one path per wire, and chaining many copies of the instance makes a missing Hamiltonian path cost more paths than there are wires. We also show that unrestricted networks can be shorter than fixed-target ones by a factor linear in the number of qubits. This is a preprint; it has not been peer reviewed.
A unitary operator U=∑j,kuj,k∣k⟩⟨j∣U=\sum_{j,k} u_{j,k} \ket{k} \bra{j}U=∑j,k​uj,k​∣k⟩⟨j∣ is called \emph{diagonal} when uj,k=0u_{j,k}=0uj,k​=0 unless j=kj=kj=k. The definition extends to quantum computations, where jjj and kkk vary over the 2n2^n2n binary expressions for integers 0,1⋯ ,2n−10,1 \cdots ,2^n-10,1⋯,2n−1, given nnn qubits. Such operators do not affect outcomes of the projective measurement {∣j⟩⟨j∣  ;  0≤j≤2n−1}\{ \ket{j}\bra{j} \; ; \; 0 \leq j \leq 2^n-1\}{∣j⟩⟨j∣;0≤j≤2n−1} but rather create arbitrary relative phases among the computational basis states $\{ \ket{j} \; ; \; 0 \leq j \leq 2^n-1\}.
Mid-circuit measurements with feedforward reduce the optimal worst-case quantum depth for exact nnn-qubit unitary synthesis from Θ(n)Θ(n)Θ(n) to O(1)O(1)O(1), using arbitrary one- and two-qubit gates and unrestricted ancillary space. Measurements and resets without feedforward remain subject to the circuit causal-cone bound. Our deterministic construction uses single-qubit measurements, O(1)O(1)O(1) rounds of parity feedforward, and O(n4nlog⁡(n+2))O(n4^n\log(n+2))O(n4nlog(n+2)) total qubits, with all ancillas starting and ending in ∣0⟩|0\rangle∣0⟩. Classical processing is not counted in quantum depth. We teleport only the matrix error of an approximation by Nehoran and Yuen. An exactly prepared ancillary state encodes this error, whose action is added back by coherent interference. At operator-norm error 2−n2^{-n}2−n, one step of amplitude amplification suffices. Coherent fanout circuits achieve the same constant-depth bound, while circuits using only one- and two-qubit gates attain depth Θ(n)Θ(n)Θ(n) with O(4nlog⁡2(n+2))O(4^n\log^2(n+2))O(4nlog2(n+2)) gates. Generic targets require Ω(4n/(h+1))Ω(4^n/(h+1))Ω(4n/(h+1)) qubits at depth hhh, even under unrestricted classical control. Our depth-width trade-offs meet this bound within a factor O(n2)O(n^2)O(n2) for 1≤h≤2n1\le h\le2^n1≤h≤2n.
Prior work by the authors [1] showed that the 24 vertices of the 24-cell, as unit quaternions, form the binarytetrahedral group 2T, that a controlled probe lifts the phase-blind projective group 2T/{±1} to all 24 gates, and thatthe optimal single-shot measurement discriminating them compiles, gate by gate, to an explicit RY/RZ/X/CNOTcircuit. That compilation was symmetry-blind: a textbook Givens synthesis of a generic 32×32 unitary, emitting25,210 CNOTs. Here we ask what the group structure of the input buys back. We report four findings. (A) The 24controlled-probe states span only a rank-3 subspace, so a reader need be correct only there; restricting thesynthesis to that support cuts the emitted CNOT count from 25,210 to 5,980 (4.2×) with the same single-shotarchitecture and the identical optimum. (B) The optimal POVM is exactly 2T-covariant: its 24 elements are onegroup orbit of a single seed, and the analysis map is a genuine tight-frame isometry that intertwines the supportrepresentation with the regular representation of 2T. (C) Consequently the reader factors as a data-independent2T group-Fourier transform followed by a placement whose data-dependent part is tiny (72 CNOT); the rank-3signal occupies just 5 of the 24 Fourier lines, which is the structural reason (A) works. (D, honest negative) Acheap synthesis of that group-Fourier transform is not achieved: the naive tensor product of the C3 and Q8transforms fails to block-diagonalize because 2T = Q8 : C3 is a crossed product, and the missing twiddle absorbsall the cost. We make no quantum-advantage claim; every number is a real emitted gate count or a verified matrixidentity from exact, numpy-only statevector simulation. ※ The license for codes is AGPL3.0-or-later
We determine the non-Clifford TTT-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford+T+T+T model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an nnn-qubit operator with aaa clean ancillas and at most sss TTT gates can be compressed to use at most min⁡{a,n+2s}\min\{a,n+2s\}min{a,n+2s} ancillas, without increasing the absolute error or TTT-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error εεε, a volume-covering argument combined with circuit counting gives the worst-case lower bound Ω(n2log⁡(n4/ε))Ω(n^2\sqrt{\log(n^4/ε)})Ω(n2log(n4/ε)​), matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on nnn spins, we obtain independent lower bounds Ω(n)Ω(n)Ω(n) from stabilizer nullity and Ω(log⁡(1/ε))Ω(\log(1/ε))Ω(log(1/ε)) from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling Θ(n+log⁡(1/ε))Θ(n+\log(1/ε))Θ(n+log(1/ε)). As an application, we evaluate the TTT-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation TTT-count scales as the query count times the optimal TTT-count per query.
We consider a dilute Fermi gas in three dimensions interacting through a positive, radially symmetric, compactly supported, and integrable potential in the thermodynamic limit. We establish a second-order lower bound for the ground-state energy density, with an error term that is optimal in the sense that it matches the order of the next correction term conjectured by Huang and Yang [Phys. Rev. 105, 767–775 (1957)]. Although a first rigorous derivation of the Huang–Yang formula has recently been obtained in the combined papers [Giacomelli et al. CPAM, e70040 (2026), Giacomelli et al.arXiv:2505.22340], the present work takes a different approach, inspired by the construction of suitable trial states introduced in Giacomelli et al. [CPAM, e70040 (2026)]. In particular, we provide a simple proof that is effective enough to yield the optimal error bound, by adapting the argument originally used to establish the upper bound on the energy density in Giacomelli et al. [CPAM, e70040 (2026)].