calculations did not converge to this tolerance within the default PySCF
settings. There were two different classes of convergence problems. First, for
a few systems, some CIDER calculations did not converge from the PySCF
starting guess, but the convergence issues were resolved by starting from PBE
ground-state orbitals. Second, for some systems (especially isolated atoms and
ions, as well as alkali and alkaline earth-containing systems), a numerical
stability issue was observed for some CIDER calculations, in which the energy
converged to a reasonable tolerance (less than $10^{-7}$ Eh), but the orbital
gradients oscillated around $10^{-3}$ Eh without converging fully. In these
cases, the energy tolerance was set to $10^{-7}$ Eh, and the gradient
tolerance was set to the (rather large) $2\times 10^{-3}$ Eh. All CIDER
calculations converged to these thresholds. PBE starting orbitals were also
used for these loose-threshold calculations. Even with these looser
thresholds, the achieved energy and orbital gradient convergence is still
sufficient to compare thermochemical data in the GMTKN55 database.

###  A.10 CIDER Functional Settings

The CIDER functionals require a few additional settings to specify the
precision of the accelerated feature calculations. For the molecular version,
these settings are $l_{\text{max}}$, the maximum spherical harmonic order for
auxiliary basis expansions in Section II.5; $\lambda$, in Eq. 60;
$\beta^{\text{aux}}$, in Eq. 71; and $q_{\text{max}}$, the maximum value of
$q_{\alpha}$ (Eq. 60). The $\xi$ basis in Eq. 74 uses the same parameter
$\lambda$ for the even-tempered basis as Eq. 60. We chose $l_{\text{max}}=10$,
$\lambda=\beta^{\text{aux}}=1.6$, and
$q_{\text{max}}=\frac{1000}{36}Z_{\text{max}}^{2}$, where $Z_{\text{max}}$ is
the minimum of 36 and the charge of the largest nucleus in the given GMTKN55
sub-database. These settings were found to be in good agreement with numerical
integration of the features. The minimum control point $q_{0}$ was set
automatically based on the minimum allowed value of the kernel exponent
$a(\mathbf{r})$.

For the plane-wave implementation, only $\lambda=1.8$ and $q_{\text{max}}=300$
needed to be specified. A larger $q_{\text{max,atom}}=10Z^{2}$ was used for
each atom on the radial support grids, with $Z$ being the atomic number. In
both the Gaussian-type orbital and plane-wave implementations, all other
CIDER-specific parameters (like the minimum exponents for the various
auxiliary bases) were set automatically based on the chosen basis set and
nonlocal feature parameters (i.e. the parameters in Appendix A.8).

###  A.11 Band Gap Calculations

Band gaps for the database of Borlido _et al._ [42] were computed in GPAW [62,
63] as the difference between the conduction band minimum and valence band
maximum for a ground-state SCF calculation. The energy cutoff for these
calculations was 520 eV, and the grid spacing was set to $h=0.134$ Å to avoid
any aliasing of the density. Fermi-Dirac k-point smearing was used with a
width of 0.01 eV, except for the noble gas systems, for which no k-point
smearing was used. The k-point mesh for each system was selected to be the
smallest even, $\Gamma$-centered mesh with a linear k-point density of at
least 6 k-points per Å-1. For each system, if the PBE band gap we obtained was
more than 0.1 eV larger than the PBE band gap obtained by Borlido _et al._
[42], we inferred that the k-point mesh was too coarse and reran the band gap
calculation with a linear k-point density of 10 k-points per Å-1. Using this
methodology, we reproduced the PBE band gaps of Borlido _et al._ with a mean,
mean absolute, and maximum error of -0.01, 0.03, amd 0.17 eV, respectively,
and the SCAN results with a mean, mean absolute, and maximum error of 0.00,
0.03, and 0.15 eV, respectively.

For PBE0/NL-MGGA-DTR and PBE0(0.35)/NL-MGGA-DTR, a few systems did not
converge with the default CIDER PAW corrections, and a denser core integration
grid and smaller set of feature projectors (i.e. the $g_{i}^{A}$ and
$p_{i}^{A}$ functions of Section II.6) were used. Even with these settings,
one system (ReSe2) did not converge with PBE0(0.35)/NL-MGGA-DTR, and it had to
be run with SG15 norm-conserving pseudopotentials (NCPP) [123]. For the 255
calculations in the main text, the mean, mean absolute, and maximum deviations
between PBE0/NL-MGGA-DTR with NCPP and PAW were 0.03, 0.12, and 1.12 eV,
respectively. In addition, the band gap for ReSe2 with PBE0/NL-MGGA-DTR was
1.29 eV with PAW and 1.30 eV with NCPP, so the use of pseudopotentials appears
reasonable for this particular case. We think that the convergence issues are
due to numerical problems with the PAW corrections for nonlocal features, and
improving the numerical stability of these corrections will be a subject of
future work.

For the band gaps in Table 4, the same procedure was used, except with denser
k-point meshes containing 12 k-points per Å-1. The HSE06 band gaps were
computed using VASP [91], with the k-point mesh set to contain 4000 k-points
divided by the number of atoms in the unit cell. This is a coarser mesh than
was used for the semilocal and CIDER calculations, but we found that the band
gap difference compared to larger k-point densities was less than 0.01 eV.

###  A.12 Supercell and Neutral Defect Performance Benchmark

The atomic structure of the 215-atom single vacancy cells of diamond and
silicon were obtained using VASP [91, 92, 93] with PAW datasets [68, 61], an
energy cutoff of 520 eV, the “Accurate” precision setting, and a $2\times
2\times 2$ Monkhorst-Pack k-point mesh [89], starting with the PBE lattice
constant obtained in VASP using the same settings with a $14\times 14\times
14$ $\Gamma$-centered k-point mesh. Using these structures, SCF ground-state
calculations with static atomic positions were performed in GPAW [62, 63] for
the 216-atom bulk and 215-atom vacancy cells for each functional. The
formation energy of the neutral defect was computed as

$E^{\text{formen}}=E^{\text{defect}}-\frac{215}{216}E^{\text{bulk}},$ (121)

where the bulk and defect energies were computed with 216 and 215-atom
supercells, respectively, with a $2\times 2\times 2$ Monkhorst-Pack k-point
mesh, 520 eV plane-wave cutoff, 0.134 Å grid spacing, and $10^{-5}$ eV
convergence threshold. The time to evaluate the formation energy for each
functional was computed as the sum of the time taken for the bulk and vacancy
cell calculations, as obtained from the GPAW internal calculation timer. The
HSE06 and PBE0 formation energies were obtained using VASP with the same
structures, k-point grid, and energy cutoff.

For the $\Gamma$-point calculations used in fig 8a, GPAW was also used for the
semilocal and ML functionals. For the hybrid DFT calculations, JDFTx [90] was
used with the adaptively compressed exchange [17] algorithm for exchange, a
19.2 Eh plane-wave cutoff, a $10^{-6}$ Eh convergence threshold, and SG15
norm-conserving pseudopotentials [123].

###  A.13 Charged Defect Calculations

The charged defect levels were computed with PBE, PBE0/NL-MGGA-DTR, and
PBE0(0.3)/NL-MGGA-DTR. The mixing parameter $\alpha=0.3$ of the last
functional was selected to match the zero-temperature experimental band gap of
silicon, 1.17 eV. For each functional, the lattice constant, band edges, and
band gap were obtained from a unit cell relaxation with 520 eV cutoff,
$h=0.134$ Å, and a $24\times 24\times 24$ k-point mesh in GPAW [62, 63]. Then,
a 512-atom supercell was created for each defect, with perturbed structures
used for the vacancy to break symmetry. For each charge state and defect, the
geometry was relaxed in GPAW using the BFGS with Line Search algorithm to a
tolerance of 0.05 eV/Å with a $\Gamma$-point only calculation. This geometry
was then used as the starting point for the final geometry relaxation, which
was performed with a $2\times 2\times 2$ $\Gamma$-centered k-point mesh and a
force convergence tolerance of 0.01 eV/Å. Because PBE0(0.3)/NL-MGGA-DTR is so
similar to PBE0/NL-MGGA-DTR, and because the lattice constants are similar, we
saved time for this functional by starting the final relaxation from the
fractional coordinates of the PBE0/NL-MGGA-DTR calculations.

The formation energies of the defects were calculated as [6]

$\displaystyle E^{f}[X^{q}]=$ $\displaystyle
E_{\text{tot}}[X^{q}]-E_{\text{tot}}[\text{bulk}]$
$\displaystyle-\sum_{i}n_{i}\mu_{i}+qE_{F}+E_{\text{corr}}[X^{q}],$ (122)

where $E_{\text{tot}}$ is the total ground-state energy of the supercell DFT
calculation, $X^{q}$ is defect $X$ in charge state $q$, $E_{F}$ is the Fermi
level, and $E_{\text{corr}}[X^{q}]$ is a finite-size energy correction for the
defect. The stoichiometry changes and chemical potentials $n_{i}$ and
$\mu_{i}$ were neglected because they do not impact electronic transition
levels. We used the Freysoldt finite-size correction-scheme for
$E_{\text{corr}}[X^{q}]$ [94], which combines an electrostatic and potential
alignment correction. This correction requires an estimate of the dielectric
constant $\epsilon$, for which we used the experimental value of 11.9 [124].

Because some of the defects studied in this work are shallow donors and
acceptors, and because electrostatic corrections like those developed by
Freysoldt _et al._ [94] and Kumagai _et al._ [125] assume localized charges,
these corrections might be inaccurate. Therefore, for comparison, we also
computed the transition levels using the potential alignment correction only,
i.e.

$E_{\text{corr}}[X^{q}]=q\left(\bar{V}_{\text{esp}}^{\infty}[X^{q}]-\bar{V}_{\text{esp}}^{\infty}[\text{bulk}]\right),$
(123)

where $\bar{V}_{\text{esp}}^{\infty}$ is the average electrostatic potential
in a region far from the defect site. This is equivalent to the full Freysoldt
correction with $\epsilon\rightarrow\infty$. We used pymatgen [104] to perform
the corrections.

##  Appendix B Construction of Feature Projector Functions for CIDER within
PAW

###  B.1 Construction of Feature Smoothing Projectors

We solve for the coefficients $D_{j\beta}$ and $C_{i\alpha}$ in Eqs. 85 and 86
by minimizing the loss function

$\mathcal{L}=\sum_{\beta}w_{\beta}\int\differential[3]\mathbf{r}\left[\hat{y}_{A,\beta}(\mathbf{r})-\Delta
F_{A,\beta}(\mathbf{r})\right]^{2}.$ (124)

For the current implementation, $w_{\beta}=1$, but this could be changed if
needed to encourage better smoothness or numerical precision. We start with
the following set of functions:

$\displaystyle g_{i\leftarrow nlm}(\mathbf{r})$
$\displaystyle=\begin{cases}Y_{lm}(\mathbf{\hat{r}})P(2n+l,r/r_{c})&r<r_{c}\\\
0&r\geq r_{c}\end{cases}$ (125) $\displaystyle P(n,x)$
$\displaystyle=\begin{cases}\frac{1}{2}(1+\cos\pi x)&n=0\\\
Q(n-1,x)&n\in\mathbb{O}\\\ R(n-2,x)&n\in\mathbb{E}\end{cases}$ (126)
$\displaystyle Q(m,x)$ $\displaystyle=5\left(\sin\frac{\pi
x}{2}-\frac{1}{2}+\frac{1}{2}\cos\pi x\right)x^{m}e^{-mx^{2}}$ (127)
$\displaystyle R(m,x)$ $\displaystyle=\frac{1}{2}\left(1-\cos(2\pi
x)\right)x^{m}e^{-mx^{2}},$ (128)

where $\mathbb{O}$ and $\mathbb{E}$ are the sets of positive odd and even
integers, respectively. Then we introduce the matrix $\mathbf{P}$

$\mathbf{P}=\begin{pmatrix}\mathbf{P}^{11}&\mathbf{P}^{12}\\\
(\mathbf{P}^{12})^{\top}&\mathbf{P}^{22}\end{pmatrix}.$ (129)

In the above equation, $\mathbf{P}^{11}$ is an $N_{h}N_{a}\times N_{h}N_{a}$
matrix,

$P^{11}_{j\beta,j^{\prime}\beta^{\prime}}=\delta_{\beta\beta^{\prime}}\innerproduct{h_{j}^{A}}{h_{j^{\prime}}}+\delta_{jj^{\prime}}\delta_{\beta\beta^{\prime}}\sigma_{11},$
(130)

where $N_{h}$ is the number of $h_{j}^{A}$ functions and $N_{a}$ is the number
of control points for kernel interpolation. Similarly, $\mathbf{P}^{22}$ is an
$N_{g}N_{a}\times N_{g}N_{a}$ matrix,

$\displaystyle P^{22}_{i\alpha,i^{\prime}\alpha^{\prime}}$
$\displaystyle=\sum_{\beta}w_{\beta}I_{\beta,i\alpha,i^{\prime}\alpha^{\prime}}+\delta_{ii^{\prime}}\delta_{\alpha\alpha^{\prime}}\sigma_{22}^{\prime}$
(131) $\displaystyle I_{\beta,i\alpha,i^{\prime}\alpha^{\prime}}$
$\displaystyle=\int\differential[3]\mathbf{r}\,\phi_{i\alpha\beta}(\mathbf{r})\phi_{i^{\prime}\alpha^{\prime}\beta}(\mathbf{r})\left(1+\sigma_{22}f_{cut}(\mathbf{r})\right)$
(132) $\displaystyle\phi_{i\alpha\beta}(\mathbf{r})$
$\displaystyle=\int\differential[3]\mathbf{r}^{\prime}\,\Phi_{\alpha\beta}(\mathbf{r}^{\prime}-\mathbf{r})g_{i}^{A}(\mathbf{r}^{\prime}),$
(133)

where $N_{g}$ is the number of $g_{i}^{A}$ functions. The constants
$\sigma_{11}$, $\sigma_{22}$, and $\sigma_{22}^{\prime}$ are regularization
constants to reduce the magnitude of the feature augmentation correction in
the core region, which helps with numerical stability by preventing the
pseudo-feature from being unrealistically large in the core.

Lastly, $\mathbf{P}^{12}$ is an $N_{h}N_{a}\times N_{g}N_{a}$ matrix:

$P^{12}_{j\beta,i\alpha}=w_{\beta}\int\differential[3]\mathbf{r}\,h_{j}(\mathbf{r})\phi_{i\alpha\beta}(\mathbf{r}).$
(134)

The coefficients can be solved by minimizing the loss Eq. 124, which results
in the linear system

$\begin{pmatrix}\mathbf{D}\\\
\mathbf{C}\end{pmatrix}=\begin{pmatrix}\mathbf{P}^{11}&\mathbf{P}^{12}\\\
(\mathbf{P}^{12})^{\top}&\mathbf{P}^{22}\end{pmatrix}^{-1}\begin{pmatrix}\mathbf{b}^{1}\\\
\mathbf{b}^{2}\end{pmatrix},$ (135)

where

$\displaystyle b^{1}_{j\beta}$
$\displaystyle=w_{\beta}\int\differential[3]\mathbf{k}\,\Delta
F_{A,\beta}(\mathbf{k})h_{j}^{A}(\mathbf{k})$ (136) $\displaystyle
b^{2}_{i\alpha}$
$\displaystyle=\sum_{\beta}w_{\beta}\int\differential[3]\mathbf{k}\,\Delta
F_{A,\beta}(\mathbf{k})\phi_{i\alpha\beta}(\mathbf{k}).$ (137)

The matrix $\mathbf{P}$ is block-diagonal in the angular momentum channels due
to the orthogonality of spherical harmonics, so each angular momentum channel
can be solved separately. This makes the whole routine fairly efficient, and
the number of operations per SCF cycle is linear-scaling in the number of
atoms. The Fourier transforms of the $g_{i}^{A}$ and $h_{j}^{A}$ functions
needed for Eqs. 136 and 137 are obtained using the NUMSBT algorithm [126], and
the $\Delta F_{A,\beta}(\mathbf{k})$ is decomposed into angular momentum
channels via the $\Delta F_{A,L,\beta}(k)$ term obtained in Eq. 83. Also, note
that there are a larger number of $\alpha$ and $\beta$ indices in the atomic
augmentation regions than on the FFT grid. The above fitting procedure is only
used for indices going up to the maximum $\alpha$ index on the FFT grid. The
higher indices (corresponding to larger values of $q_{\alpha}$ that are only
relevant in the core regions) are solved by simply projecting onto the
$h_{j}^{A}(\mathbf{r})$ basis, i.e. setting
$\mathbf{D}=\left(\mathbf{P}^{11}\right)^{-1}\mathbf{b}^{1}$ in the subspace
of core region-only $\alpha$ indices. This procedure is equivalent to assuming
that the larger $q_{\alpha}$ contributions to $\theta_{\alpha}$ and
$F_{\beta}$ are localized in the core region, which is reasonable because
these contributions correspond to high densities and short length-scales for
$\Phi_{\alpha\beta}(r)$ (Eq. 19).

###  B.2 Construction of the Feature Augmentation Projectors

The feature augmentation projectors used in Eq. 90 are constructed as

$\displaystyle p_{i\leftarrow nlm}(\mathbf{r})$
$\displaystyle=Y_{lm}(\hat{\mathbf{r}})P(2n+l,r/r_{0})$ (138) $\displaystyle
P(n,x)$ $\displaystyle=\begin{cases}x^{n}(x^{2}-1)^{2}&x<1\\\ 0&x\geq
1\end{cases}.$ (139)

The on-site function sets $\tilde{f}_{i}^{A}(\mathbf{r})$ and
$\tilde{p}_{j}^{A}(\mathbf{r})$ are then computed as

$\displaystyle\tilde{p}_{i}(\mathbf{r})$
$\displaystyle=p_{i}(\mathbf{r})f_{\text{cut}}(\mathbf{r})$ (140)
$\displaystyle\tilde{f}_{i}(\mathbf{r})$
$\displaystyle=\sum_{j}\left(\mathbf{S}^{-1}\right)_{ij}p_{j}(\mathbf{r})$
(141) $\displaystyle S_{ij}$
$\displaystyle=\int\differential[3]\mathbf{r}\,p_{i}(\mathbf{r})p_{j}(\mathbf{r})f_{\text{cut}}(\mathbf{r})$
(142) $\displaystyle f_{\text{cut}}(\mathbf{r})$
$\displaystyle=\begin{cases}\frac{1}{2}\left(1+\cos\frac{\pi
r}{r_{c}}\right)&r<r_{c}\\\ 0&r\geq r_{c}\end{cases}.$ (143)

The construction localizes $\tilde{p}_{j}^{A}(\mathbf{r})$ inside the core
region and satisfies the condition that
$\innerproduct{\tilde{f}_{i}^{A}}{\tilde{p}_{j}^{A}}=\delta_{ij}$.

###### Acknowledgements.

The authors thank Jennifer Coulter for helpful guidance on running JDFTx
calculations. This work was supported by the National Defense Science and
Engineering Graduate (NDSEG) Fellowship Program under contract
FA9550-21-F-0003, the Camille and Henry Dreyfus Foundation Grant No.
ML-22-075, and the Department of Navy award N00014-20-1-2418 issued by the
Office of Naval Research. Computational resources were provided by the Harvard
University FAS Division of Science Research Computing Group.

## References

  * Mardirossian and Head-Gordon [2017] N. Mardirossian and M. Head-Gordon, Thirty years of density functional theory in computational chemistry: an overview and extensive assessment of 200 density functionals, Mol. Phys. 115, 2315 (2017).
  * Kohn and Sham [1965] W. Kohn and L. J. Sham, Self-Consistent Equations Including Exchange and Correlation Effects, Phys. Rev. 140, A1133 (1965).
  * Wellendorff  _et al._ [2015] J. Wellendorff, T. L. Silbaugh, D. Garcia-Pintos, J. K. Nørskov, T. Bligaard, F. Studt, and C. T. Campbell, A benchmark database for adsorption bond energies to transition metal surfaces and comparison to selected DFT functionals, Surf. Sci. 640, 36 (2015).
  * He  _et al._ [2019] Q. He, B. Yu, Z. Li, and Y. Zhao, Density Functional Theory for Battery Materials, ENERGY Environ. Mater. 2, 264 (2019).
  * Lany and Zunger [2008] S. Lany and A. Zunger, Assessment of correction methods for the band-gap problem and for finite-size effects in supercell defect calculations: Case studies for ZnO and GaAs, Phys. Rev. B 78, 235104 (2008).
  * Freysoldt  _et al._ [2014] C. Freysoldt, B. Grabowski, T. Hickel, J. Neugebauer, G. Kresse, A. Janotti, and C. G. Van de Walle, First-principles calculations for point defects in solids, Rev. Mod. Phys. 86, 253 (2014).
  * Perdew [2001] J. P. Perdew, Jacob’s ladder of density functional approximations for the exchange-correlation energy, in  _AIP Conf. Proc._, Vol. 577 (AIP, 2001) pp. 1–20.
  * Perdew and Levy [1983] J. P. Perdew and M. Levy, Physical Content of the Exact Kohn-Sham Orbital Energies: Band Gaps and Derivative Discontinuities, Phys. Rev. Lett. 51, 1884 (1983).
  * Godby  _et al._ [1986] R. W. Godby, M. Schlüter, and L. J. Sham, Accurate Exchange-Correlation Potential for Silicon and Its Discontinuity on Addition of an Electron, Phys. Rev. Lett. 56, 2415 (1986).
  * Goerigk  _et al._ [2017] L. Goerigk, A. Hansen, C. Bauer, S. Ehrlich, A. Najibi, and S. Grimme, A look at the density functional theory zoo with the advanced GMTKN55 database for general main group thermochemistry, kinetics and noncovalent interactions, Phys. Chem. Chem. Phys. 19, 32184 (2017).
  * Yang  _et al._ [2016] Z.-h. Yang, H. Peng, J. Sun, and J. P. Perdew, More realistic band gaps from meta-generalized gradient approximations: Only in a generalized Kohn-Sham scheme, Phys. Rev. B 93, 205205 (2016).
  * Aschebrock and Kümmel [2019] T. Aschebrock and S. Kümmel, Ultranonlocality and accurate band gaps from a meta-generalized gradient approximation, Phys. Rev. Res. 1, 033082 (2019).
  * Kovács  _et al._ [2022] P. Kovács, F. Tran, P. Blaha, and G. K. H. Madsen, What is the optimal mGGA exchange functional for solids?, J. Chem. Phys. 157, 094110 (2022).
  * Lebeda  _et al._ [2022] T. Lebeda, T. Aschebrock, and S. Kümmel, First steps towards achieving both ultranonlocality and a reliable description of electronic binding in a meta-generalized gradient approximation, Phys. Rev. Res. 4, 023061 (2022).
  * Becke [1993] A. D. Becke, Density‐functional thermochemistry. III. The role of exact exchange, J. Chem. Phys. 98, 5648 (1993).
  * Janesko  _et al._ [2009] B. G. Janesko, T. M. Henderson, and G. E. Scuseria, Screened hybrid density functionals for solid-state chemistry and physics, Phys. Chem. Chem. Phys. 11, 443 (2009).
  * Lin [2016] L. Lin, Adaptively Compressed Exchange Operator, J. Chem. Theory Comput. 12, 2242 (2016).
  * Hu  _et al._ [2017] W. Hu, L. Lin, A. S. Banerjee, E. Vecharynski, and C. Yang, Adaptively Compressed Exchange Operator for Large-Scale Hybrid Density Functional Calculations with Applications to the Adsorption of Water on Silicene, J. Chem. Theory Comput. 13, 1188 (2017).
  * Carnimeo  _et al._ [2019] I. Carnimeo, S. Baroni, and P. Giannozzi, Fast hybrid density-functional computations using plane-wave basis sets, Electron. Struct. 1, 015009 (2019).
  * Vinson [2020] J. Vinson, Faster exact exchange in periodic systems using single-precision arithmetic, J. Chem. Phys. 153, 204106 (2020).
  * Ko  _et al._ [2020] H.-Y. Ko, J. Jia, B. Santra, X. Wu, R. Car, and R. A. DiStasio Jr., Enabling Large-Scale Condensed-Phase Hybrid Density Functional Theory Based Ab Initio Molecular Dynamics. 1. Theory, Algorithm, and Performance, J. Chem. Theory Comput. 16, 3757 (2020).
  * Lee  _et al._ [2022] J. Lee, A. Rettig, X. Feng, E. Epifanovsky, and M. Head-Gordon, Faster Exact Exchange for Solids via occ-RI-K: Application to Combinatorially Optimized Range-Separated Hybrid Functionals for Simple Solids with Pseudopotentials Near the Basis Set Limit, J. Chem. Theory Comput. 18, 7336 (2022).
  * Perdew  _et al._ [1996] J. P. Perdew, K. Burke, and M. Ernzerhof, Generalized Gradient Approximation Made Simple, Phys. Rev. Lett. 77, 3865 (1996).
  * Sun  _et al._ [2015] J. Sun, A. Ruzsinszky, and J. Perdew, Strongly Constrained and Appropriately Normed Semilocal Density Functional, Phys. Rev. Lett. 115, 036402 (2015).
  * Perdew  _et al._ [2005] J. P. Perdew, A. Ruzsinszky, J. Tao, V. N. Staroverov, G. E. Scuseria, and G. I. Csonka, Prescription for the design and selection of density functional approximations: More constraint satisfaction with fewer fits, J. Chem. Phys. 123, 062201 (2005).
  * Kaplan  _et al._ [2023] A. D. Kaplan, M. Levy, and J. P. Perdew, The Predictive Power of Exact Constraints and Appropriate Norms in Density Functional Theory, Annu. Rev. Phys. Chem. 74, 193 (2023).
  * Stephens  _et al._ [1994] P. J. Stephens, F. J. Devlin, C. F. Chabalowski, and M. J. Frisch, Ab Initio calculation of vibrational absorption and circular dichroism spectra using density functional force fields, J. Phys. Chem. 98, 11623 (1994).
  * Mardirossian and Head-Gordon [2014] N. Mardirossian and M. Head-Gordon, $\omega$B97X-V: A 10-parameter, range-separated hybrid, generalized gradient approximation density functional with nonlocal correlation, designed by a survival-of-the-fittest strategy, Phys. Chem. Chem. Phys. 16, 9904 (2014).
  * Dick and Fernandez-Serra [2021] S. Dick and M. Fernandez-Serra, Highly accurate and constrained density functional obtained with differentiable programming, Phys. Rev. B 104, L161109 (2021).
  * Nagai  _et al._ [2020] R. Nagai, R. Akashi, and O. Sugino, Completing density functional theory by machine learning hidden messages from molecules, npj Comput. Mater. 6, 1 (2020).
  * Kasim and Vinko [2021] M. F. Kasim and S. M. Vinko, Learning the Exchange-Correlation Functional from Nature with Fully Differentiable Density Functional Theory, Phys. Rev. Lett. 127, 126403 (2021).
  * Nagai  _et al._ [2022] R. Nagai, R. Akashi, and O. Sugino, Machine-learning-based exchange correlation functional with physical asymptotic constraints, Phys. Rev. Res. 4, 013106 (2022).
  * Trepte and Voss [2022] K. Trepte and J. Voss, Data‐driven and constrained optimization of semi‐local exchange and nonlocal correlation functionals for materials and surface chemistry, J. Comput. Chem. 43, 1104 (2022).
  * Sparrow  _et al._ [2022] Z. M. Sparrow, B. G. Ernst, T. K. Quady, and R. A. DiStasio, Uniting Nonempirical and Empirical Density Functional Approximation Strategies Using Constraint-Based Regularization, J. Phys. Chem. Lett. 13, 6896 (2022).
  * Bystrom and Kozinsky [2022] K. Bystrom and B. Kozinsky, CIDER: An Expressive, Nonlocal Feature Set for Machine Learning Density Functionals with Exact Constraints, J. Chem. Theory Comput. 18, 2180 (2022).
  * Kirkpatrick  _et al._ [2021] J. Kirkpatrick, B. McMorrow, D. H. P. Turban, A. L. Gaunt, J. S. Spencer, A. G. D. G. Matthews, A. Obika, L. Thiry, M. Fortunato, D. Pfau, L. R. Castellanos, S. Petersen, A. W. R. Nelson, P. Kohli, P. Mori-Sánchez, D. Hassabis, and A. J. Cohen, Pushing the frontiers of density functionals by solving the fractional electron problem, Science 374, 1385 (2021).
  * Wellendorff  _et al._ [2012] J. Wellendorff, K. T. Lundgaard, A. Møgelhøj, V. Petzold, D. D. Landis, J. K. Nørskov, T. Bligaard, and K. W. Jacobsen, Density functionals for surface science: Exchange-correlation model development with Bayesian error estimation, Phys. Rev. B 85, 235149 (2012).
  * Wellendorff  _et al._ [2014] J. Wellendorff, K. T. Lundgaard, K. W. Jacobsen, and T. Bligaard, mBEEF: An accurate semi-local Bayesian error estimation density functional, J. Chem. Phys. 140, 144107 (2014).
  * Lundgaard  _et al._ [2016] K. T. Lundgaard, J. Wellendorff, J. Voss, K. W. Jacobsen, and T. Bligaard, mBEEF-vdW: Robust fitting of error estimation density functionals, Phys. Rev. B 93, 235162 (2016).
  * Mavros  _et al._ [2014] M. G. Mavros, T. Tsuchimochi, T. Kowalczyk, A. McIsaac, L.-P. Wang, and T. V. Voorhis, What Can Density Functional Theory Tell Us about Artificial Catalytic Water Splitting?, Inorg. Chem. 53, 6386 (2014).
  * Shukla  _et al._ [2022] V. Shukla, Y. Jiao, J. H. Lee, E. Schröder, J. B. Neaton, and P. Hyldgaard, Accurate Nonempirical Range-Separated Hybrid van der Waals Density Functional for Complex Molecular Problems, Solids, and Surfaces, Phys. Rev. X 12, 041003 (2022).
  * Borlido  _et al._ [2019] P. Borlido, T. Aull, A. W. Huran, F. Tran, M. A. L. Marques, and S. Botti, Large-Scale Benchmark of Exchange–Correlation Functionals for the Determination of Electronic Band Gaps of Solids, J. Chem. Theory Comput. 15, 5069 (2019).
  * Lei and Medford [2019] X. Lei and A. J. Medford, Design and analysis of machine learning exchange-correlation functionals via rotationally invariant convolutional descriptors, Phys. Rev. Mater. 3, 063801 (2019).
  * Levy and Perdew [1985] M. Levy and J. P. Perdew, Hellmann-Feynman, virial, and scaling requisites for the exact universal density functionals. Shape of the correlation potential and diamagnetic susceptibility for atoms, Phys. Rev. A 32, 2010 (1985).
  * Oliver and Perdew [1979] G. L. Oliver and J. P. Perdew, Spin-density gradient expansion for the kinetic energy, Phys. Rev. A 20, 397 (1979).
  * Dirac [1930] P. A. M. Dirac, Note on Exchange Phenomena in the Thomas Atom, Math. Proc. Cambridge Philos. Soc. 26, 376 (1930).
  * Dreizler and Gross [1990] R. M. Dreizler and E. K. U. Gross, The Kohn-Sham Scheme, in  _Density Functional Theory An Approach to Quantum Many-Body Problem_ (Springer Berlin Heidelberg, Berlin, Heidelberg, 1990) pp. 43–74.
  * Rasmussen and Williams [2006] C. E. Rasmussen and C. K. I. Williams,  _Gaussian Processes for Machine Learning_ (The MIT Press, Cambridge, MA, USA, 2006).
  * Duvenaud  _et al._ [2011] D. Duvenaud, H. Nickisch, and C. E. Rasmussen, Additive Gaussian processes, Adv. Neural Inf. Process. Syst. 24 (NIPS 2011) (2011).
  * Glielmo  _et al._ [2018] A. Glielmo, C. Zeni, and A. De Vita, Efficient nonparametric n -body force fields from machine learning, Phys. Rev. B 97, 184307 (2018).
  * Vandermause  _et al._ [2020] J. Vandermause, S. B. Torrisi, S. Batzner, Y. Xie, L. Sun, A. M. Kolpak, and B. Kozinsky, On-the-fly active learning of interpretable Bayesian force fields for atomistic rare events, npj Comput. Mater. 6, 20 (2020).
  * Xie  _et al._ [2021] Y. Xie, J. Vandermause, L. Sun, A. Cepellotti, and B. Kozinsky, Bayesian force fields from active learning for simulation of inter-dimensional transformation of stanene, npj Comput. Mater. 7, 40 (2021).
  * Román-Pérez and Soler [2009] G. Román-Pérez and J. M. Soler, Efficient Implementation of a van der Waals Density Functional: Application to Double-Wall Carbon Nanotubes, Phys. Rev. Lett. 103, 096102 (2009).
  * Vydrov and Van Voorhis [2010] O. A. Vydrov and T. Van Voorhis, Nonlocal van der Waals density functional: The simpler the better, J. Chem. Phys. 133, 244103 (2010).
  * Sun  _et al._ [2018] Q. Sun, T. C. Berkelbach, N. S. Blunt, G. H. Booth, S. Guo, Z. Li, J. Liu, J. D. McClain, E. R. Sayfutyarova, S. Sharma, S. Wouters, and G. K. Chan, PySCF: the Python‐based simulations of chemistry framework, WIREs Comput. Mol. Sci. 8, e1340 (2018).
  * Sun  _et al._ [2020] Q. Sun, X. Zhang, S. Banerjee, P. Bao, M. Barbry, N. S. Blunt, N. A. Bogdanov, G. H. Booth, J. Chen, Z.-H. Cui, J. J. Eriksen, Y. Gao, S. Guo, J. Hermann, M. R. Hermes, K. Koh, P. Koval, S. Lehtola, Z. Li, J. Liu, N. Mardirossian, J. D. McClain, M. Motta, B. Mussard, H. Q. Pham, A. Pulkin, W. Purwanto, P. J. Robinson, E. Ronca, E. R. Sayfutyarova, M. Scheurer, H. F. Schurkus, J. E. T. Smith, C. Sun, S.-N. Sun, S. Upadhyay, L. K. Wagner, X. Wang, A. White, J. D. Whitfield, M. J. Williamson, S. Wouters, J. Yang, J. M. Yu, T. Zhu, T. C. Berkelbach, S. Sharma, A. Y. Sokolov, and G. K.-L. Chan, Recent developments in the PySCF program package, J. Chem. Phys. 153, 024109 (2020).
  * Franchini  _et al._ [2014] M. Franchini, P. H. T. Philipsen, E. van Lenthe, and L. Visscher, Accurate Coulomb Potentials for Periodic and Molecular Systems through Density Fitting, J. Chem. Theory Comput. 10, 1994 (2014).
  * Becke [1988] A. D. Becke, A multicenter numerical integration scheme for polyatomic molecules, J. Chem. Phys. 88, 2547 (1988).
  * Lebedev and Laikov [1999] V. I. Lebedev and D. N. Laikov, Quadrature formula for the sphere of 131st algebraic order of accuracy, Dokl. Akad. Nauk 59, 477 (1999).
  * Johnson  _et al._ [1993] B. G. Johnson, P. M. W. Gill, and J. A. Pople, The performance of a family of density functional methods, J. Chem. Phys. 98, 5612 (1993).
  * Blöchl [1994] P. E. Blöchl, Projector augmented-wave method, Phys. Rev. B 50, 17953 (1994).
  * Mortensen  _et al._ [2005] J. J. Mortensen, L. B. Hansen, and K. W. Jacobsen, Real-space grid implementation of the projector augmented wave method, Phys. Rev. B 71, 035109 (2005).
  * Enkovaara  _et al._ [2010] J. Enkovaara, C. Rostgaard, J. J. Mortensen, J. Chen, M. Dułak, L. Ferrighi, J. Gavnholt, C. Glinsvad, V. Haikola, H. A. Hansen, H. H. Kristoffersen, M. Kuisma, A. H. Larsen, L. Lehtovaara, M. Ljungberg, O. Lopez-Acevedo, P. G. Moses, J. Ojanen, T. Olsen, V. Petzold, N. A. Romero, J. Stausholm-Møller, M. Strange, G. A. Tritsaris, M. Vanin, M. Walter, B. Hammer, H. Häkkinen, G. K. H. Madsen, R. M. Nieminen, J. K. Nørskov, M. Puska, T. T. Rantala, J. Schiøtz, K. S. Thygesen, and K. W. Jacobsen, Electronic structure calculations with GPAW: a real-space implementation of the projector augmented-wave method, J. Phys. Condens. Matter 22, 253202 (2010).
  * Klimeš  _et al._ [2011] J. Klimeš, D. R. Bowler, and A. Michaelides, Van der Waals density functionals applied to solids, Phys. Rev. B 83, 195131 (2011).
  * Lehtomäki  _et al._ [2014] J. Lehtomäki, I. Makkonen, M. A. Caro, A. Harju, and O. Lopez-Acevedo, Orbital-free density functional theory implementation with the projector augmented-wave method, J. Chem. Phys. 141, 234102 (2014).
  * Xu  _et al._ [2022] Q. Xu, C. Ma, W. Mi, Y. Wang, and Y. Ma, Nonlocal pseudopotential energy density functional for orbital-free density functional theory, Nat. Commun. 13, 1385 (2022).
  * Witt  _et al._ [2018] W. C. Witt, B. G. Del Rio, J. M. Dieterich, and E. A. Carter, Orbital-free density functional theory for materials research, J. Mater. Res. 33, 777 (2018).
  * Kresse and Joubert [1999] G. Kresse and D. Joubert, From ultrasoft pseudopotentials to the projector augmented-wave method, Phys. Rev. B 59, 1758 (1999).
  * Zhang  _et al._ [2018] G.-X. Zhang, A. M. Reilly, A. Tkatchenko, and M. Scheffler, Performance of various density-functional approximations for cohesive properties of 64 bulk solids, New J. Phys. 20, 063020 (2018).
  * Chachiyo and Chachiyo [2020] T. Chachiyo and H. Chachiyo, Simple and accurate exchange energy for density functional theory, Molecules 25, 3485 (2020).
  * Adamo and Barone [1999] C. Adamo and V. Barone, Toward reliable density functional methods without adjustable parameters: The PBE0 model, J. Chem. Phys. 110, 6158 (1999).
  * Caldeweyher  _et al._ [2019] E. Caldeweyher, S. Ehlert, A. Hansen, H. Neugebauer, S. Spicher, C. Bannwarth, and S. Grimme, A generally applicable atomic-charge dependent London dispersion correction, J. Chem. Phys. 150, 154122 (2019).
  * Furness  _et al._ [2020] J. W. Furness, A. D. Kaplan, J. Ning, J. P. Perdew, and J. Sun, Accurate and Numerically Efficient r2SCAN Meta-Generalized Gradient Approximation, J. Phys. Chem. Lett. 11, 8208 (2020).
  * Mori-Sánchez and Cohen [2014] P. Mori-Sánchez and A. J. Cohen, The derivative discontinuity of the exchange–correlation functional, Phys. Chem. Chem. Phys. 16, 14378 (2014).
  * Cohen  _et al._ [2008] A. J. Cohen, P. Mori-Sánchez, and W. Yang, Insights into Current Limitations of Density Functional Theory, Science 321, 792 (2008).
  * Zhao and Truhlar [2005] Y. Zhao and D. G. Truhlar, Design of Density Functionals That Are Broadly Accurate for Thermochemistry, Thermochemical Kinetics, and Nonbonded Interactions, J. Phys. Chem. A 109, 5656 (2005).
  * Zhang and Yang [1998] Y. Zhang and W. Yang, Comment on “Generalized Gradient Approximation Made Simple”, Phys. Rev. Lett. 80, 890 (1998).
  * Mardirossian and Head-Gordon [2015] N. Mardirossian and M. Head-Gordon, Mapping the genome of meta-generalized gradient approximation density functionals: The search for B97M-V, J. Chem. Phys. 142, 074111 (2015).
  * Mardirossian and Head-Gordon [2016] N. Mardirossian and M. Head-Gordon, $\omega$ B97M-V: A combinatorially optimized, range-separated hybrid, meta-GGA density functional with VV10 nonlocal correlation, J. Chem. Phys. 144, 214110 (2016).
  * Sham and Schlüter [1983] L. J. Sham and M. Schlüter, Density-Functional Theory of the Energy Gap, Phys. Rev. Lett. 51, 1888 (1983).
  * Perdew [1986] J. P. Perdew, Density functional theory and the band gap problem, Int. J. Quantum Chem. 30, 451 (1986).
  * Schultz [2006] P. A. Schultz, Theory of Defect Levels and the “Band Gap Problem” in Silicon, Phys. Rev. Lett. 96, 246401 (2006).
  * Perdew  _et al._ [2017] J. P. Perdew, W. Yang, K. Burke, Z. Yang, E. K. U. Gross, M. Scheffler, G. E. Scuseria, T. M. Henderson, I. Y. Zhang, A. Ruzsinszky, H. Peng, J. Sun, E. Trushin, and A. Görling, Understanding band gaps of solids in generalized Kohn–Sham theory, Proc. Natl. Acad. Sci. 114, 2801 (2017).
  * Borlido  _et al._ [2020] P. Borlido, J. Schmidt, A. W. Huran, F. Tran, M. A. L. Marques, and S. Botti, Exchange-correlation functionals for band gaps of solids: benchmark, reparametrization and machine learning, npj Comput. Mater. 6, 96 (2020).
  * Tran and Blaha [2009] F. Tran and P. Blaha, Accurate Band Gaps of Semiconductors and Insulators with a Semilocal Exchange-Correlation Potential, Phys. Rev. Lett. 102, 226401 (2009).
  * Heyd  _et al._ [2003] J. Heyd, G. E. Scuseria, and M. Ernzerhof, Hybrid functionals based on a screened Coulomb potential, J. Chem. Phys. 118, 8207 (2003).
  * Krukau  _et al._ [2006] A. V. Krukau, O. A. Vydrov, A. F. Izmaylov, and G. E. Scuseria, Influence of the exchange screening parameter on the performance of screened hybrid functionals, J. Chem. Phys. 125, 224106 (2006).
  * Moussa  _et al._ [2012] J. E. Moussa, P. A. Schultz, and J. R. Chelikowsky, Analysis of the Heyd-Scuseria-Ernzerhof density functional parameter space, J. Chem. Phys. 136, 204117 (2012).
  * Monkhorst and Pack [1976] H. J. Monkhorst and J. D. Pack, Special points for Brillouin-zone integrations, Phys. Rev. B 13, 5188 (1976).
  * Sundararaman  _et al._ [2017] R. Sundararaman, K. Letchworth-Weaver, K. A. Schwarz, D. Gunceler, Y. Ozhabes, and T. Arias, JDFTx: Software for joint density-functional theory, SoftwareX 6, 278 (2017).
  * Kresse and Hafner [1993] G. Kresse and J. Hafner, Ab initio molecular dynamics for liquid metals, Phys. Rev. B 47, 558 (1993).
  * Kresse and Furthmüller [1996a] G. Kresse and J. Furthmüller, Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set, Phys. Rev. B 54, 11169 (1996a).
  * Kresse and Furthmüller [1996b] G. Kresse and J. Furthmüller, Efficiency of ab-initio total energy calculations for metals and semiconductors using a plane-wave basis set, Comput. Mater. Sci. 6, 15 (1996b).
  * Freysoldt  _et al._ [2009] C. Freysoldt, J. Neugebauer, and C. G. Van de Walle, Fully Ab Initio Finite-Size Corrections for Charged-Defect Supercell Calculations, Phys. Rev. Lett. 102, 016402 (2009).
  * Watkins and Troxell [1980] G. D. Watkins and J. R. Troxell, Negative-U Properties for Point Defects in Silicon, Phys. Rev. Lett. 44, 593 (1980).
  * Fischer and Rome [1983] D. W. Fischer and J. J. Rome, Additional structure in infrared excitation spectra of group-III acceptors in silicon, Phys. Rev. B 27, 4826 (1983).
  * Jagannath  _et al._ [1981] C. Jagannath, Z. W. Grabowski, and A. K. Ramdas, Linewidths of the electronic excitation spectra of donors in silicon, Phys. Rev. B 23, 2082 (1981).
  * Knack  _et al._ [2002] S. Knack, J. Weber, H. Lemke, and H. Riemann, Copper-hydrogen complexes in silicon, Phys. Rev. B 65, 165203 (2002).
  * Schulz  _et al._ [2002] M. Schulz, T. Dalibor, W. Martienssen, H. Landolt, and R. Börnstein,  _Impurities Defects Gr. IV Elem. IV-IV III-V Compd. Part a Gr. IV Elem._, edited by O. Madelung, U. Rössler, and M. Schulz, Landolt-Börnstein - Group III Condensed Matter, Vol. 41A2a (Springer-Verlag, Berlin/Heidelberg, 2002).
  * Deák  _et al._ [2010] P. Deák, B. Aradi, T. Frauenheim, E. Janzén, and A. Gali, Accurate defect levels obtained from the HSE06 range-separated hybrid functional, Phys. Rev. B 81, 153203 (2010).
  * Sharan  _et al._ [2017] A. Sharan, Z. Gui, and A. Janotti, Hybrid-Functional Calculations of the Copper Impurity in Silicon, Phys. Rev. Appl. 8, 024023 (2017).
  * Broberg  _et al._ [2023] D. Broberg, K. Bystrom, S. Srivastava, D. Dahliah, B. A. D. Williamson, L. Weston, D. O. Scanlon, G.-M. Rignanese, S. Dwaraknath, J. Varley, K. A. Persson, M. Asta, and G. Hautier, High-throughput calculations of charged point defect properties with semi-local density functional theory—performance benchmarks for materials screening applications, npj Comput. Mater. 9, 72 (2023).
  * Berland  _et al._ [2015] K. Berland, V. R. Cooper, K. Lee, E. Schröder, T. Thonhauser, P. Hyldgaard, and B. I. Lundqvist, van der Waals forces in density functional theory: a review of the vdW-DF method, Reports Prog. Phys. 78, 066501 (2015).
  * Ong  _et al._ [2013] S. P. Ong, W. D. Richards, A. Jain, G. Hautier, M. Kocher, S. Cholia, D. Gunter, V. L. Chevrier, K. A. Persson, and G. Ceder, Python Materials Genomics (pymatgen): A robust, open-source python library for materials analysis, Comput. Mater. Sci. 68, 314 (2013).
  * Hjorth Larsen  _et al._ [2017] A. Hjorth Larsen, J. Jørgen Mortensen, J. Blomqvist, I. E. Castelli, R. Christensen, M. Dułak, J. Friis, M. N. Groves, B. Hammer, C. Hargus, E. D. Hermes, P. C. Jennings, P. Bjerre Jensen, J. Kermode, J. R. Kitchin, E. Leonhard Kolsbjerg, J. Kubal, K. Kaasbjerg, S. Lysgaard, J. Bergmann Maronsson, T. Maxson, T. Olsen, L. Pastewka, A. Peterson, C. Rostgaard, J. Schiøtz, O. Schütt, M. Strange, K. S. Thygesen, T. Vegge, L. Vilhelmsen, M. Walter, Z. Zeng, and K. W. Jacobsen, The atomic simulation environment—a Python library for working with atoms, J. Phys. Condens. Matter 29, 273002 (2017).
  * Jain  _et al._ [2015] A. Jain, S. P. Ong, W. Chen, B. Medasani, X. Qu, M. Kocher, M. Brafman, G. Petretto, G. M. Rignanese, G. Hautier, D. Gunter, and K. A. Persson, Fireworks: A dynamic workflow system designed for highthroughput applications, Concurr. Comput. 27, 5037 (2015).
  * Pedregosa  _et al._ [2011] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, Scikit-learn: Machine Learning in Python, J. Mach. Learn. Res. 12, 2825 (2011).
  * Weigend  _et al._ [2003] F. Weigend, F. Furche, and R. Ahlrichs, Gaussian basis sets of quadruple zeta valence quality for atoms H–Kr, J. Chem. Phys. 119, 12753 (2003).
  * Rappoport and Furche [2010] D. Rappoport and F. Furche, Property-optimized Gaussian basis sets for molecular response calculations, J. Chem. Phys. 133, 134105 (2010).
  * Weigend [2008] F. Weigend, Hartree–Fock exchange fitting basis sets for H to Rn, J. Comput. Chem. 29, 167 (2008).
  * Neese  _et al._ [2009] F. Neese, F. Wennmohs, A. Hansen, and U. Becker, Efficient, approximate and parallel Hartree-Fock and hybrid DFT calculations. A ’chain-of-spheres’ algorithm for the Hartree-Fock exchange, Chem. Phys. 356, 98 (2009).
  * Jain  _et al._ [2013] A. Jain, S. P. Ong, G. Hautier, W. Chen, W. D. Richards, S. Dacek, S. Cholia, D. Gunter, D. Skinner, G. Ceder, and K. A. Persson, Commentary: The Materials Project: A materials genome approach to accelerating materials innovation, APL Mater. 1, 011002 (2013).
  * Neese [2012] F. Neese, The ORCA program system, WIREs Comput. Mol. Sci. 2, 73 (2012).
  * Neese [2018] F. Neese, Software update: the ORCA program system, version 4.0, WIREs Comput. Mol. Sci. 8, e1327 (2018).
  * Neese  _et al._ [2020] F. Neese, F. Wennmohs, U. Becker, and C. Riplinger, The ORCA quantum chemistry program package, J. Chem. Phys. 152, 224108 (2020).
  * Barnard [2013] A. S. Barnard, Modeling polydispersive ensembles of diamond nanoparticles, Nanotechnology 24, 085703 (2013).
  * Barnard [2014] A. Barnard, Diamond Nanoparticle Structure Set (2014), 10.4225/08/546A9F79EC99C.
  * Becke and Johnson [2005] A. D. Becke and E. R. Johnson, A density-functional model of the dispersion interaction, J. Chem. Phys. 123, 154101 (2005).
  * Johnson and Becke [2006] E. R. Johnson and A. D. Becke, A post-Hartree-Fock model of intermolecular interactions: Inclusion of higher-order corrections, J. Chem. Phys. 124, 174104 (2006).
  * Grimme  _et al._ [2010] S. Grimme, J. Antony, S. Ehrlich, and H. Krieg, A consistent and accurate ab initio parametrization of density functional dispersion correction (DFT-D) for the 94 elements H-Pu, J. Chem. Phys. 132, 154104 (2010).
  * Higham [2002] N. J. Higham,  _Accuracy and Stability of Numerical Algorithms_, 2nd ed. (Society for Industrial and Applied Mathematics, 2002) https://epubs.siam.org/doi/pdf/10.1137/1.9780898718027 .
  * Harbrecht  _et al._ [2012] H. Harbrecht, M. Peters, and R. Schneider, On the low-rank approximation by the pivoted Cholesky decomposition, in  _Appl. Numer. Math._, Vol. 62 (2012).
  * Hamann [2013] D. R. Hamann, Optimized norm-conserving Vanderbilt pseudopotentials, Phys. Rev. B 88, 085117 (2013).
  * Sze and Ng [2006] S. Sze and K. K. Ng,  _Physics of Semiconductor Devices_ (John Wiley & Sons, Inc., Hoboken, NJ, USA, 2006).
  * Kumagai and Oba [2014] Y. Kumagai and F. Oba, Electrostatics-based finite-size corrections for first-principles point defect calculations, Phys. Rev. B 89, 195205 (2014).
  * Talman [2009] J. D. Talman, NumSBT: A subroutine for calculating spherical Bessel transforms numerically, Comput. Phys. Commun. 180, 332 (2009).


P BQP EQP PP RP BPP PostEQP PostZPP PostBQP A B EPP

# On the Rational Degree of Boolean Functions and Applications

###### Abstract

We study a natural complexity measure of Boolean functions known as the
(exact) rational degree. For total functions $f$, it is conjectured that
$\operatorname{rdeg}(f)$ is polynomially related to $\mathrm{deg}(f)$, where
$\mathrm{deg}(f)$ is the Fourier degree. Towards this conjecture, we show that
symmetric functions have rational degree at least $\mathrm{deg}(f)/2$ and
monotone functions have rational degree at least $\sqrt{\mathrm{deg}(f)}$. We
observe that both of these lower bounds are tight. In addition, we show that
all read-once depth-$d$ Boolean formulae have rational degree at least
$\Omega(\mathrm{deg}(f)^{1/d})$. Furthermore, we show that almost every
Boolean function on $n$ variables has rational degree at least
$n/2-\mathcal{O}(\sqrt{n})$.

In contrast to total functions, we exhibit partial functions that witness
unbounded separations between rational and approximate degree, in both
directions. As a consequence, we show that for quantum computers, post-
selection and bounded-error are incomparable resources in the black-box model.

Vishnu Iyer | Siddhartha Jain | Matt Kovacs-Deak | Vinayak M. Kumar
---|---|---|---
UT Austin | UT Austin | University of Maryland | UT Austin
Luke Schaeffer | Daochen Wang | Michael Whitmeyer
---|---|---
University of Maryland | University of Maryland | University of Washington

##  1 Introduction

Starting with the seminal work of Minsky and Papert [MP69], a long line of
research has sought to relate various measures of Boolean function complexity.
In [NS92], Nisan and Szegedy proved that the deterministic decision tree
complexity $\mathrm{D}(f)$ of a Boolean function $f$ is polynomially related
to its degree $\mathrm{deg}(f)$ as a multilinear polynomial. The same paper
posed two open questions. One of them conjectures that the sensitivity and
block sensitivity of a Boolean function are polynomially related. This
conjecture was recently proven in a breakthrough by Huang [Hua19]. Huang’s
result brought sensitivity into a happy flock of complexity measures on total
Boolean functions that are all polynomially related: sensitivity, degree,
approximate degree, and notions of query complexity.

Another natural measure of Boolean function complexity is the minimal degree
of a rational polynomial which represents the function exactly, called the
_rational degree_ (denoted $\operatorname{rdeg}$). However,
$\operatorname{rdeg}$ is _not_ known to be either polynomially related to or
separated from the complexity measures mentioned above. In fact, this was the
other open question posed over 30 years ago in the paper of Nisan and Szegedy
(via personal communication with Fortnow) [NS92]. This question was reiterated
by Aaronson et al. [ABDK+21] yet very little progress has been made toward its
resolution.

######  Question 1 (Fortnow [NS92]).

Does there exist $c>1$ such that for all total Boolean functions $f$,
$\mathrm{deg}(f)\leq\mathcal{O}(\operatorname{rdeg}(f)^{c})$?

One of the motivations for Fortnow’s question was complexity-theoretic: is the
intersection of and strictly contained in with respect to a generic oracle
[For03]? and are counting classes [AK] which we define later, and rational
degree corresponds to the black-box version of their intersection.

The rational degree is also related to quantum query complexity. In
particular, de Wolf defined the _non-deterministic degree_
$\operatorname{ndeg}(f)$ of a Boolean function $f$ as the minimal degree of a
polynomial whose zero set is precisely the set of inputs on which $f$
evaluates to false [Wol00], and related it to the rational degree through the
identity
$\operatorname{rdeg}(f)=\max\\{\operatorname{ndeg}(f),\operatorname{ndeg}(\bar{f})\\}$.
de Wolf also proved that the non-deterministic degree $\operatorname{ndeg}(f)$
equals the _non-deterministic quantum query complexity_ up to a constant
factor.

In the same manuscript, de Wolf stated the following conjecture which,
together with the inequality $\mathrm{deg}(f)\leq\mathrm{D}(f)$, would resolve
Fortnow’s question in the affirmative with $c=2$.

######  Conjecture 1 (de Wolf [Wol00]).

For all Boolean functions $f$,
$\mathrm{D}(f)\leq\mathcal{O}(\operatorname{ndeg}(f)\operatorname{ndeg}(\bar{f}))$.

Mahadev and de Wolf showed [MW15] an even tighter connection between the
notion of rational degree and quantum query complexity: denoting by
$\mathrm{\operatorname{rdeg}}_{\varepsilon}(f)$ the minimum degree of a
rational polynomial that $\varepsilon$-approximates $f$ pointwise, they showed
that $\mathrm{\operatorname{rdeg}}_{\varepsilon}(f)$ equals (up to a constant
factor) the query complexity of a quantum algorithm with _post-selection_
111Post-selection is an operation that allows for projection onto an
efficiently computable set of basis states for free, even if this set accounts
for an arbitrarily small fraction of the probability mass. that computes $f$
with error $\varepsilon$. For partial functions, it can be shown that the
rational degree gives a lower bound on the query complexity of algorithms with
post-selection, though the opposite direction is not known to be true.
Furthermore, this result extends to the case of $\varepsilon=0$, the so-called
zero-error setting.

###  1.1 Our Results

We prove lower bounds on the rational degree for certain classes of total
Boolean functions. We summarize our results according to section:

  * Sec 3.1

For symmetric functions we show that
$\mathrm{deg}(f)/2\leq\operatorname{rdeg}(f)$. This lower bound is tight, as
witnessed by the $\operatorname{\mathsf{PARITY}}_{n}$ function. Our technique
for symmetric functions generalizes to classes of functions including ones
which are constant on many Hamming weights.

  * Sec 3.2

We employ the lower bound on symmetric functions to show that for depth-$d$
Boolean formulae, $\operatorname{rdeg}(f)\geq\Omega(\mathrm{deg}(f)^{1/d})$.
For $d=2$ this is tight, as witnessed by the
$\operatorname{\mathsf{AND}}_{n}\circ\operatorname{\mathsf{OR}}_{n}$ function.

  * Sec 3.3

For monotone functions we prove that
$\operatorname{rdeg}(f)=\mathrm{s}(f)\geq\sqrt{\mathrm{deg}(f)}$. This is also
tight as witnessed by the
$\operatorname{\mathsf{AND}}_{n}\circ\operatorname{\mathsf{OR}}_{n}$ function.

  * Sec 3.4

Our final lower bound on total functions is extremal: we prove that almost all
Boolean functions on $n$ bits have rational degree at least
$n/2-\mathcal{O}(\sqrt{n})$.

| Rational Degree Lower Bound | Attained By
---|---|---
Symmetric Functions | $\mathrm{deg}(f)/2$ | $\operatorname{\mathsf{PARITY}}_{n}$
Monotone Functions | $\sqrt{\mathrm{deg}(f)}$ | $\operatorname{\mathsf{AND}}_{n}\circ\operatorname{\mathsf{OR}}_{n}$
Read-once CNF/DNF Formulae | $\Omega(\sqrt{\mathrm{deg}(f)})$ | $\operatorname{\mathsf{AND}}_{n}\circ\operatorname{\mathsf{OR}}_{n}$
Read-once Depth $d$ Formulae | $\Omega(\mathrm{deg}(f)^{1/d})$ | —
Almost all $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ | $n/2-\mathcal{O}(\sqrt{n})$ | N/A
Figure 1: A table summarizing our lower bounds on rational degree for total
functions. The third column gives an example of a function that demonstrates
the tightness of our lower bound, where applicable.

On the other hand, we show that for partial functions, the rational and
approximate degrees can be unboundedly separated in both directions. These
separations also resolve an open question of Fortnow [For03].

  * Sec 4.1

We give a partial function ${\text{MajOrNone}}_{n}$ on $n$ bits with constant
quantum query complexity yet rational degree $\Omega(n)$. As a result,
${\text{MajOrNone}}_{n}$ has constant approximate degree and $\Omega(n)$ zero-
error post-selected quantum query complexity.

  * Sec 4.2

On the other hand, we give a partial function ${\text{Imbalance}}_{n}$ on $n$
bits with approximate degree $\Omega(n)$ yet constant rational degree. As a
result, ${\text{Imbalance}}_{n}$ has constant zero-error post-selected quantum
query complexity and quantum query complexity $\Omega(n)$.

Now, employing the framework of standard complexity results such as [FSS81],
we can argue that post-selection and bounded error are incomparable resources
in the black-box setting. To formalise this, we define as the class of
decision problems which can be decided deterministically in polynomial time by
quantum computers with access to post-selection. In particular, there exists a
bidirectional separation between $\posteqp$ and $\bqp$ with respect to generic
oracles. Formally, combining the results of Corollaries 22 and 18 we get the
following statement.

######  Corollary 1.

There exist oracles $O_{1}$ and $O_{2}$ such that
$\bqp^{O_{1}}\not\subseteq\posteqp^{O_{1}}$ yet
$\posteqp^{O_{2}}\not\subseteq\bqp^{O_{2}}$.

These complexity-theoretic consequences are summarized in Figure 2. As the
figure illustrates, these are the strongest possible separations in the black-
box model.

$\ptime$$\rp$$\bpp$$\eqp$$\bqp$$\posteqp$$\postbqp$Corollary 18Corollary 22
Figure 2: Relevant complexity classes. We are able to obtain the strongest
possible oracle separations in this picture. An arrow $\cA\rightarrow\cB$
means $\cA\subseteq\cB$ relative to all oracles. A dashed arrow
$\cA\dashrightarrow\cB$ means $\cA\not\subseteq\cB$ relative to some oracle.

In addition to these consequences for $\posteqp$, our lower bound also
resolves Fortnow’s complexity-theoretic question. We show that not only is
$\ceqp\cap\coeqp$ strictly contained in , even is not in this intersection
with respect to a generic oracle. The class is the set of languages decidable
by an machine such that if the string is in the language, the number of
accepting paths is _exactly_ equal to the number of rejecting paths. Finally,
to contextualize the power of $\posteqp$, we provide strong evidence that
zero-error post-selection can offer advantage over efficient classical
computation, even in the non-relativized setting.

  * Sec 4.3

We show that $\posteqp$ contains $\NP\cap\coNP$. We remark that $\NP\cap\coNP$
is not even believed to be contained in $\bpp$.

##  2 Preliminaries

In this section we review some of the notation and definitions used in our
paper. For a more comprehensive introduction to the analysis of Boolean
functions see [Sak93, O’D14]. We denote by $[n]$ the set $\\{1,2,...,n\\}$.
Given a function $f\colon S\to\mathbb{R}$ we denote by $\left\lVert
f\right\rVert_{1}$ its $l_{1}$ norm, $\left\lVert f\right\rVert_{1}=\sum_{x\in
S}\left\lvert f(x)\right\rvert$. For a bitstring $x\in\\{0,1\\}^{n}$, we
denote by $|x|$ the Hamming weight of $x$: the number of indices equal to $1$.
If $x\in\\{-1,1\\}^{n}$ the Hamming weight is the number of bits that equal
$-1$.

###  2.1 Boolean Functions

A (total) Boolean function is any function $f\colon\Sigma^{n}\to\Sigma$ where
$\Sigma$ is some two-element set. We will refer to the set $\Sigma^{n}$ as the
Boolean hypercube. We will primarily work over the sets $\Sigma=\\{0,1\\}$ and
$\Sigma=\\{-1,1\\}$. The mapping $t\mapsto(t+1)/2$ maps $\\{-1,1\\}$ onto
$\\{0,1\\}$. While not all Boolean complexity measures are left invariant by
this change of representation, all of the measures considered in this paper
are preserved.

We also consider restrictions of Boolean functions to proper subsets of the
Boolean cube $D\subset\Sigma^{n}$. We refer to such functions $f\colon
D\to\Sigma$ as _partial_ Boolean functions. Given a Boolean function $f$, we
denote its negation by $\bar{f}$. We can define an inner product on the space
of functions $f\colon\\{-1,1\\}^{n}\to\mathbb{R}$:

$\displaystyle\langle f,g\rangle=2^{-n}\sum_{x\in\\{-1,1\\}^{n}}f(x)g(x).$

For each $S\subseteq[n]$ we define the _character function $\chi_{S}$ on $S$_
as $\chi_{S}(x)=\prod_{i\in S}x_{i}$. The character functions $\chi_{S}$ form
an orthonormal basis under the above inner product. Thus each function over
$\\{-1,1\\}^{n}$ can be uniquely expressed via its _Fourier representation_ :

$\displaystyle f=\sum_{S\subseteq[n]}\widehat{f}(S)\cdot\chi_{S},$

where we refer to $\widehat{f}(S)=\langle f,\chi_{S}\rangle$ as the _Fourier
coefficient of $f$ at $S$_. We say an input $i\in[n]$ is _relevant_ for $f$ if
$x_{i}$ appears in the Fourier expansion for $f$. In other words, $f$ depends
on $x_{i}$ in a nontrivial manner.

###  2.2 Polynomials

As described above, each Boolean function can be represented uniquely as a
formal multilinear polynomial through its Fourier representation. We define
the Fourier _degree_ (or simply degree) of $f$ as
$\mathrm{deg}(f)=\max\\{\left\lvert S\right\rvert:\widehat{f}(S)\neq 0\\}$. We
can extend this notion to polynomials that pointwise approximate $f$:

######  Definition 2.

Let $D\subseteq\\{-1,1\\}^{n}$ and $f\colon D\to\\{-1,1\\}$. A polynomial
$p:\\{-1,1\\}^{n}\to\mathbb{R}$ is said to $\varepsilon$-approximate $f$ if
for all $x\in D$, $|p(x)-f(x)|\leq\varepsilon$ and for all
$x\in\\{-1,1\\}^{n}$, $|p(x)|\leq 1$. The _$\varepsilon$ -approximate degree_
of $f$, denoted
$\widetilde{\vphantom{t}\smash{\mathrm{deg}}}_{\varepsilon}(f)$, is defined as
the minimum degree of any polynomial that $\varepsilon$-approximates $f$. The
_degree_ of $f$, denoted $\mathrm{deg}(f)$, is defined as
$\widetilde{\vphantom{t}\smash{\mathrm{deg}}}_{0}(f)$. The _approximate
degree_ of $f$, denoted $\widetilde{\vphantom{t}\smash{\mathrm{deg}}}(f)$, is
defined as $\widetilde{\vphantom{t}\smash{\mathrm{deg}}}_{1/3}(f)$.

In this paper, we are primarily concerned with representations of $f$ via
rational polynomials. This gives rise to a measure known as _rational degree_
, which is formally defined as follows.

######  Definition 3.

Let $D\subseteq\\{-1,1\\}^{n}$ and $f\colon D\to\\{-1,1\\}$. If $p\colon
D\to\mathbb{R}$ and $q\colon D\to\mathbb{R}$ are polynomials such that
$\left\lvert f(x)-p(x)/q(x)\right\rvert\leq\varepsilon$ for all $x\in D$, we
say that $p/q$ is an $\varepsilon$-approximate rational representation of $f$.
The _$\varepsilon$ -approximate rational degree_ of $f$, denoted
$\operatorname{rdeg}_{\varepsilon}(f)$, is defined as the minimum value of
$\max\\{\mathrm{deg}(p),\mathrm{deg}(q)\\}$ such that $p/q$ is an
$\varepsilon$-approximate rational representation of $f$. The _rational
degree_ of $f$, denoted $\operatorname{rdeg}(f)$, is defined as
$\operatorname{rdeg}_{0}(f)$.

Unlike in the definition of approximate degree, there is no requirement for an
approximate rational representation to be bounded outside of $D$. Whether or
not such a boundedness condition is imposed matters significantly for the
degree (see [BKT20]) but not for the rational degree (see Appendix A).

###  2.3 Sensitivity and Certificate Complexity

We now define some useful combinatorial measures of Boolean function
complexity. Let $f$ be a Boolean function, $x\in\\{-1,1\\}^{n}$, and
$B\subseteq[n]$. We say that $B$ is a sensitive block of $f$ at $x$ if
$f(x)\neq f(x^{B})$ where $x^{B}$ denotes the bitstring obtained by flipping
all bits of $x$ indexed by $B$. We define, and denote by $\mathrm{bs}_{f}(x)$,
the _block sensitivity of $f$ at $x$_ as the maximum number of disjoint blocks
that are all sensitive at $x$. By restricting our attention to sensitive
blocks that are singletons we obtain the analogous notion of the _sensitivity
of $f$ at $x$_, denoted $\mathrm{s}_{f}(x)$. The block sensitivity of $f$ is
defined as $\mathrm{bs}(f)=\max_{x}\mathrm{bs}_{f}(x)$. Similarly the
_sensitivity of $f$_ is defined as $\mathrm{s}(f)=\max_{x}\mathrm{s}_{f}(x)$.
For $b\in\\{0,1\\}$, we also write $\mathrm{s}^{(b)}(f)=\max_{x\in
f^{-1}(b)}\mathrm{s}_{f}(x)$.

A partial assignment is some function $\rho:[n]\to\\{-1,1,\star\\}$. We
define, and denote by $\left\lvert\rho\right\rvert$, the size of the partial
assignment $\rho$ as cardinality of the set $\\{i\in[n]:\rho(i)\neq\star\\}$.
We say that a partial assignment $\rho$ is _consistent_ with some
$x\in\\{-1,1\\}^{n}$ if $x_{i}=\rho(i)$ for all $i$ with $\rho(i)\neq\star$.
Given a Boolean function $f$ we denote by $f|_{\rho}$ the restriction of $f$
to the set of inputs $x\in\\{-1,1\\}^{n}$ that are consistent with $\rho$.
Given $b\in\\{-1,1\\}$, we say that a partial assignment $\rho$ is a _$b$
-certificate for $f$_ if $f|_{\rho}(x)=b$ for all
$x\in\mathrm{Dom}(f|_{\rho})$. The _$b$ -certificate complexity_ of $f$ is
defined as

$\displaystyle\mathrm{C}_{b}(f)=\max_{x\in
f^{-1}(b)}\min\\{\left\lvert\rho\right\rvert:\rho\text{ is a $b$-certificate
for $f$ consistent with $x$}\\}.$

The _certificate complexity of $f$_ is defined as
$\mathrm{C}(f)=\max_{b\in\\{-1,1\\}}\mathrm{C}_{b}(f)$.

###  2.4 Sign and Non-Deterministic Degree

For a Boolean function $f$ we say that a polynomial
$p:\\{-1,1\\}^{n}\to\mathbb{R}$ is a _(strong) sign representation_ if
$\mathrm{sgn}(p(x))=f(x)$ for all $x\in\\{-1,1\\}^{n}$ and $p(x)\neq 0$ on the
entire hypercube. The _(strong) sign degree_ of $f$ is defined as the minimum
degree of any polynomial that strongly sign represents $f$. Alon [Alo93] and
Anthony [Ant95] have shown that all but a negligible fraction of $n$-bit
Boolean functions have sign degree at least $n/2$. Later, O’Donnell and
Servedio proved [OS08] that almost every Boolean function has sign degree at
most $n/2+\mathcal{O}(\sqrt{n\log{n}})$.

A less common but somewhat similar notion is that of a _non-deterministic
polynomial_ introduced by de Wolf [Wol00]. In this context, it is customary to
consider Boolean functions using the $\\{0,1\\}^{n}\to\\{0,1\\}$
representation.

We say that $p:\\{0,1\\}^{n}\to\mathbb{R}$ is a non-deterministic polynomial
for $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ if $p(x)=0$ if and only if $f(x)=0$. An
easy calculation establishes the following relationship between the rational
and non-deterministic degrees

$\displaystyle\operatorname{rdeg}(f)=\max\\{\operatorname{ndeg}(f),\operatorname{ndeg}(\bar{f})\\}.$

As mentioned in the introduction de Wolf conjectured that
$\mathrm{D}(f)\leq\mathcal{O}(\operatorname{ndeg}(f)\operatorname{ndeg}(\bar{f}))$
for all total Boolean functions. By showing that
$\operatorname{ndeg}(f)\leq\mathrm{C}_{1}(f)$, de Wolf also established the
inequality $\operatorname{rdeg}(f)\leq\mathrm{C}(f)$ [Wol00].

###  2.5 Quantum Query Complexity and Post-selection

We assume basic familiarity with concepts in quantum information. While we
review some of these, we direct the reader to, e.g. [NC11], for background.

Consider a Boolean function $f$ over a domain $D$. We say an
$\varepsilon$-error quantum algorithm computes $f$ if it outputs a bit $a(x)$
such that for all $x\in D$, $\Pr[a(x)=f(x)]\geq 1-\varepsilon$. $\bqp$ is the
class of problems that have efficient (polynomial-time) quantum algorithms
with error $1/3$ and $\eqp$ is the analogous class of zero-error algorithms.
We can also define complexity classes corresponding to quantum algorithms
augmented with the power of _post-selection_.

######  Definition 4.

$\postbqp$ is the set of languages decidable by a polynomial time quantum
algorithm that outputs two bits $a,b$ such that for all inputs
$x\in\\{0,1\\}^{n}$

  1. (i)

$\Pr[a(x)=1]>0$.

  2. (ii)

If $x\in L$, then $\Pr[b(x)=1|a(x)=1]\geq 2/3$.

  3. (iii)

If $x\not\in L$, then $\Pr[b(x)=1|a(x)=1]\leq 1/3$.

$\posteqp$ is the corresponding class of _zero-error_ algorithms with post-
selection.

Each of these computational complexity classes has an associated query
measure. Formally, we say a function has query access to a string $w$ if it
has black-box access to a unitary s.t. $U\ket{i}\ket{b}=\ket{i}\ket{b\oplus
w_{i}}$. When the input $w$ encodes the truth table of a Boolean function $f$,
we will often write this as $U\ket{x}\ket{b}=\ket{x}\ket{b\oplus f(x)}$, where
$x\in\\{0,1\\}^{n}$. The number of calls an algorithm makes to the unitary $U$
is its _query complexity_. By $\func{Q}_{\varepsilon}(f)$ and
$\func{Q}_{E}(f)$ we denote the query complexities of $\varepsilon$-error and
zero-error quantum algorithms, respectively. $\func{PostQ}_{\varepsilon}(f)$
and $\func{PostQ}_{E}(f)$ are defined analogously for quantum algorithms with
post-selection. For simplicity of notation, $\func{Q}(f)$ and
$\func{PostQ}(f)$ are understood to correspond to $\varepsilon=1/3$.

A seminal result by Beals et al. gives a lower bound quantum query complexity
using polynomials [BBC+01]. Formally, we have
$\func{Q}_{\varepsilon}(f)\geq\widetilde{\vphantom{t}\smash{\mathrm{deg}}}_{\varepsilon}(f)/2$
for all (possibly partial) Boolean functions $f$. As a special case,
$\func{Q}_{E}(f)\geq\mathrm{deg}(f)/2$. This result gave rise to the so-called
_polynomial method_ for quantum query lower bounds. Similarly, it was shown by
Mahadev and de Wolf that
$\func{PostQ}_{\varepsilon}(f)=\Theta(\operatorname{rdeg}_{\varepsilon}(f))$
and $\func{PostQ}_{E}(f)=\Theta(\operatorname{rdeg}_{0}(f))$ for total
functions $f$ [MW15]. It is not difficult to extend this result for partial
functions, see Appendix A. Nonetheless, it is surprising that the result does
still hold for partial functions since the analogous result for quantum query
complexity and approximate degree was recently shown to be false in [AB23].

##  3 Rational Degree Lower Bounds

In this section, we present rational degree lower bounds for certain classes
of Boolean functions. Our results constitute progress towards showing that
rational degree is polynomially related to Fourier degree for total functions.

First, we establish the tight lower bound
$\mathrm{deg}(f)/2\leq\operatorname{rdeg}(f)$ for symmetric functions. This
result then becomes key in proving a rational degree lower bound for read-once
Boolean formulae, which is tight for formulae of depth $2$. Next, we prove
that the rational degree equals the sensitivity for monotone functions, which
implies that $\sqrt{\mathrm{deg}(f)}\leq\operatorname{rdeg}(f)$ for monotone
functions. This lower bound is also tight. Finally, we show that almost all
Boolean functions $f\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$ have rational degree at
least $n/2-\mathcal{O}(\sqrt{n})$.

###  3.1 Symmetric Functions

Our first lower bounds are for (possibly partial) functions which are constant
on a large number of Hamming slices. Of course, this subsumes the class of
symmetric functions. This lemma will later be useful in obtaining an unbounded
separation of rational degree from quantum query complexity (and thus
approximate degree) in the case of partial functions.

######  Lemma 5.

Let $f$ be a (possibly partial) nonconstant Boolean function over input domain
$D\subseteq\\{0,1\\}^{n}$ and define $S_{0}=\\{k\in[n]\colon|x|=k\implies
f(x)=0\\}$, $S_{1}=\\{k\in[n]\colon|x|=k\implies f(x)=1\\}$. Then
$\mathrm{rdeg}(f)\geq\max(|S_{0}|,|S_{1}|)$.

We use the Minsky-Papert symmetrization technique, which converts a
multivariate polynomial over $\\{0,1\\}^{n}$ to a univariate polynomial over
$\mathbb{R}$ [MP69]. Formally, given $p:\\{0,1\\}^{n}\to\mathbb{R}$ we define
$P(k)\coloneqq\mathop{\mathbb{E}}_{|x|=k}[p(x)]$.

###### Proof.

Since $\operatorname{rdeg}(f)=\operatorname{rdeg}(\bar{f})$, we can assume
without loss of generality that $|S_{0}|\geq|S_{1}|$. It suffices to show that
$\operatorname{rdeg}(f)\geq|S_{0}|$. Indeed, let $f=p/q$ be a rational
representation of $f$. Applying the Minsky-Papert symmetrization technique to
$p(x)$ we obtain a univariate polynomial $P(k)$ such that
$\mathrm{deg}(p)\geq\mathrm{deg}(P)$ and $P(k)=0$ for any $k\in S_{0}$. On the
other hand, there exists at least one $k\in[n]$ such that $P(k)\neq 0$, since
$f$ is nonconstant. Thus $\mathrm{deg}(p)\geq\mathrm{deg}(P)\geq|S_{0}|$.
Since this holds for every rational representation of $f$, the result follows.
∎

Of course, a special case of this result is a strong lower bound for symmetric
total functions.

######  Corollary 6.

If $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is symmetric then
$\operatorname{rdeg}(f)\geq\mathrm{deg}(f)/2$.

###  3.2 Read-Once Formulae

We now turn our attention to a generalized version of read-once Boolean
formulae, where each gate is an arbitrary nonconstant symmetric gate. The key
observations behind the lower bound are that these formulae can be written as
compositions of symmetric gates, and that any depth $d$ tree must contain a
node with branching factor $\geq n^{1/d}$.

######  Lemma 7.

Let $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ and
$g_{i}\colon\\{0,1\\}^{n_{i}}\to\\{0,1\\}$ be Boolean functions where every
variable in each function is relevant. Defining $h:\\{0,1\\}^{\sum
n_{i}}\to\\{0,1\\}$ to be
$h(x^{1},\dots,x^{n})=f(g_{1}(x^{1}),\dots,g_{n}(x^{n}))$, we have that

$\displaystyle\operatorname{rdeg}(h)\geq\max\\{\operatorname{rdeg}(f),\operatorname{rdeg}(g_{1}),\dots,\operatorname{rdeg}(g_{n})\\}.$

###### Proof.

Since every variable is relevant for each $g_{i}$, we know there exists
restrictions $\rho^{i}$ to all but $1$ variable in each $x^{i}$ such that
$g_{i}|_{\rho^{i}}(x^{i})=x_{k_{i}}^{i}$ or $(1-x_{k_{i}}^{i})$ for some
$1\leq k_{i}\leq n_{i}$. Considering the restriction
$\rho=\rho^{1}\cup\dots\cup\rho^{n}$, it is evident that
$h|_{\rho}(x)=f(x^{1}_{k_{1}},\dots,x^{n}_{k_{n}})$ up to negations.
Therefore,

$\displaystyle\operatorname{rdeg}(h)\geq\operatorname{rdeg}(h|_{\rho})\geq\operatorname{rdeg}(f).$
(1)

Now pick an arbitrary $i$. Since, by assumption, every variable of $f$ is
relevant, there exists an assignment $x_{j}=z_{j}$ for all $j\neq i$ such that
$f(z_{1},\dots z_{i-1},x_{i},z_{i+1},\dots,z_{n})=x_{i}$ or
$\overline{x_{i}}$. Since $g_{i}$ is nonconstant, it follows that there exists
an assignment to the variables $(x^{j})_{j\neq i}$ such that each
$g_{j}(x^{j})$ is fixed to $z_{j}$.

Let $\tau$ be the restriction induced by this partial assignment. Then

$\displaystyle h|_{\tau}(x)=f(z_{1},\dots z_{i-1},g_{i}(x^{i}),z_{i+1},\dots
z_{n})=g_{i}(x^{i})\text{ or }\overline{g_{i}(x^{i})}.$

Consequently,

$\displaystyle\operatorname{rdeg}(h)\geq\operatorname{rdeg}(h|_{\tau})\geq\operatorname{rdeg}(g_{i}).$
(2)

Combining Equations 1 and 2 gives the desired result. ∎

######  Lemma 8.

Let $f$ be written as a read-once formula with symmetric gates where the
maximum branching factor of any node is $w$. Then
$\operatorname{rdeg}(f)=\Omega(w)$.

###### Proof.

Let $p/q$ be a rational representation of $f$. We can assume without loss of
generality that $f$ is monotone (i.e. only the literals $x_{i}$, and not
$\overline{x_{i}}$ appear in the formula).

Now consider the node $G$ with branching factor $w$. Let $F$ be the subformula
with top gate $G$ and let $F_{1},\dots,F_{w}$ be the read-once subformulas
below $G$. Each $F_{i}$ is nonconstant, which implies the existence of a
restriction $\rho_{i}$ of all but $1$ variable in each $V_{i}$ such that
toggling the sole live variable (say $x_{k_{i}}$) toggles the value of $F_{i}$
(i.e. $F_{i}|_{\rho_{i}}=x_{j}$ or $\overline{x_{k}}$ for some $k$). As the
$V_{i}$ are disjoint (as $f$ is read-once), these restrictions together define
a unified restriction $\rho$ such that
$F|_{\rho}(x)=G(x_{k_{1}},\dots,x_{k_{w}})$ up to negations. Inductively using
Lemma 7 on the formula $f|_{\rho}$ by starting at the top node and going down
the path to $G$, it follows that

$\operatorname{rdeg}(f)\geq\operatorname{rdeg}(f|_{\rho})\geq\operatorname{rdeg}(F|_{\rho})=\operatorname{rdeg}(G)\geq
w/2,$ (3)

where the last inequality follows from Lemma 5. ∎

Now we can prove polynomial rational degree lower bounds on read-once
formulae.

######  Corollary 9.

Let $f$ be written as a depth-$d$ read-once formula with symmetric gates. Then
$\mathrm{rdeg}(f)=\Omega(\mathrm{deg}(f)^{1/d})$.

###### Proof.

The result follows from Lemma 8 and a simple contradiction argument: if all
nodes have branching factor strictly less than $n^{1/d}$ then there must be
strictly fewer than $n$ literals. Note that $n\geq\mathrm{deg}(f)$ so the
lower bound $\Omega(n^{1/d})$ is stronger. ∎

This lower bound is tight for $d=2$, as witnessed by the
$\operatorname{\mathsf{AND}}$-of-$\operatorname{\mathsf{OR}}$s function
$f=\operatorname{\mathsf{AND}}_{\sqrt{n}}\circ\operatorname{\mathsf{OR}}_{\sqrt{n}}$.
Indeed,
$\operatorname{rdeg}\left(f\right)\leq\mathrm{C}(f)=n^{1/2}=\sqrt{\mathrm{deg}(f)}$.
However, for larger depth $d>2$, it is unclear whether a depth-$d$ read-once
$\AC^{0}$ formula with rational degree $O(n^{1/d})$ exists or if the lower
bound can be improved. It can be shown that there exist arbitrary-depth read-
once formulae with rational degree at most $\sqrt{n}$ (see Figure 3. We leave
as an open question whether the bound $\Omega(\mathrm{deg}(f)^{1/d})$ is
tight.

Figure 3: A depth-$d$
$\operatorname{\mathsf{AND}}$-$\operatorname{\mathsf{OR}}$ tree with
certificate complexity $\sqrt{n}$, and thus rational degree at most
$\sqrt{n}$. Indeed, setting all input wires to $1$ for
$\operatorname{\mathsf{AND}}$ functions and a single input wire to $1$ for
$\operatorname{\mathsf{OR}}$ functions along a single path to root gives a $1$
certificate, and setting all input wires to $0$ for
$\operatorname{\mathsf{OR}}$ functions and a single input wire to $0$ for
$\operatorname{\mathsf{AND}}$ functions gives a $0$-certificate. One can
easily verify that both of these certificates are of size $\sqrt{n}$.

###  3.3 Monotone Functions

A Boolean function $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is said to be monotone
if $\forall x,y\in\\{0,1\\}^{n}$, $x\leq y$ implies $f(x)\leq f(y)$ where
$x\leq y$ is taken pointwise. In this subsection we prove that
$\operatorname{rdeg}(f)=\mathrm{s}(f)$ for monotone Boolean function $f$. We
note that it suffices to prove that $\mathrm{s}(f)\leq\operatorname{rdeg}(f)$.
This is because the certificate complexity of a monotone Boolean functions $f$
equals its sensitivity $\mathrm{C}(f)=\mathrm{s}(f)$ [Nis91]. Combining this
with the fact that $\operatorname{rdeg}(f)\leq C(f)$ we can already conclude
the other inequality.

######  Claim 10.

For monotone Boolean functions $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$,
$s(f)\leq\operatorname{rdeg}(f)$.

Our proof is similar to the proof that for all monotone Boolean functions
$s(f)\leq\mathrm{deg}(f)$ as presented in [BW02, Proposition 4].

###### Proof.

Suppose without loss of generality that $f$ is monotone increasing. We prove
the claim by showing that

$\mathrm{s}_{0}(f)\leq\operatorname{ndeg}(\bar{f})\quad\text{and}\quad\mathrm{s}_{1}(f)\leq\operatorname{ndeg}(f).$
(4)

We only prove the first inequality as the second can be proven analogously.
Let $x$ be such that $\mathrm{s}_{0}(f)=s_{f}(x)$. All sensitive variables
must be $0$ in $x$ since $f$ is monotone increasing. Moreover, setting any
sensitive variable to $1$ changes the value of $f$ from $0$ to $1$. Therefore,
fixing all variables in $x$ except for the $\mathrm{s}_{0}(f)$ many sensitive
variables yields the $\operatorname{\mathsf{OR}}_{m}$ function on
$m\coloneqq\mathrm{s}_{0}(f)$ variables. Since
$\operatorname{ndeg}(\overline{\operatorname{\mathsf{OR}}}_{m})\geq m$,
$\operatorname{ndeg}(\bar{f})\geq s_{0}(f)$. ∎

Since $\mathrm{s}(f)=\mathrm{C}(f)$ and
$\sqrt{\mathrm{deg}(f)}\leq\mathrm{s}(f)$ for monotone functions, we have the
following corollary.

######  Corollary 11.

For monotone Boolean functions $f$, $\operatorname{rdeg}(f)=\mathrm{s}(f)$. In
particular, $\sqrt{\mathrm{deg}(f)}\leq\operatorname{rdeg}(f)$.

Note that this bound is tight, as witnessed by the
$\operatorname{\mathsf{AND}}$-of-$\operatorname{\mathsf{OR}}$s function,
$f=\operatorname{\mathsf{AND}}_{n}\circ\operatorname{\mathsf{OR}}_{n}$, on
$n^{2}$ bits, which has
$\operatorname{rdeg}\left(f\right)\leq\mathrm{C}(f)=n=\sqrt{\mathrm{deg}(f)}$.
We remark that 10 cannot be extended to all Boolean functions, as evidenced by
the Kushilevitz function $K_{m}\colon\\{0,1\\}^{6^{m}}\to\\{0,1\\}$ [NW95].
Indeed, $K_{m}$ has full sensitivity, but its degree is $3^{m}$.

###  3.4 Random Functions

As our final piece of evidence that rational degree is polynomially related to
degree, we prove that all but a negligible fraction of Boolean functions
$f\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$ have rational degree at least
$n/2-\mathcal{O}(\sqrt{n})$.

As mentioned in the introduction Alon [Alo93] and Anthony [Ant95] used
counting arguments to show that all but a negligible fraction of $n$-bit
Boolean functions have sign degree at least $n/2$. Below we restate a variant
of the function counting theorem used by Athony.

Given a finite set $X$ and a mapping $\phi\colon X\to\mathbb{R}^{d}$, we say
that a $\phi$-separable dichotomy of $X$ is a partition of $X$ into subsets
$X^{+}\cup X^{-}$ such that there exists some $w\in\mathbb{R}^{d}$ for which
$w\cdot\phi(x)>0$ for all $x\in X^{+}$ and $w\cdot\phi(x)<0$ for all $x\in
X^{-}$.

######  Theorem 12 (Function counting theorem, [Cov65]).

Let $\phi\colon S\to\mathbb{R}^{d}$. Let $X=\\{x_{1},\dots,x_{N}\\}\subseteq
S$. If a $\phi$-surface (i.e., a set of the form $\\{x\in
S:w\cdot\phi(x)=0\\}$ for some $w\in\mathbb{R}^{d}$) contains a set of points
$Y=\\{y_{1},y_{2},\dots,y_{k}\\}\subseteq S$, where $\phi(y_{i})$ are linearly
independent for all $i$, and where the projection of
$\phi(x_{1}),\dots,\phi(x_{N})$ onto the orthogonal subspace to the space
spanned by the $\phi(y_{i})$’s is in general position, then there are
$C(N,d-k)$ many $\phi$-separable dichotomies of $X$, where

$\displaystyle C(N,d)=2\sum_{i=0}^{d-1}\binom{N-1}{i}.$

We consider the following adaptation of the above theorem. Consider a set of
$N$ points $S=\\{v_{1},\dots,v_{n}\\}$ in $\mathbb{R}^{D}$. Given a 2-coloring
of the points $f\colon[N]\to\\{-1,1\\}$, we say that the coloring $f$ is
separable by two hyperplanes if there exist hyperplanes $H_{j}=\\{v:\
\alpha_{j}\cdot v=0\\}$ for $j=1,2$ such that

$\displaystyle\forall i\in[N]\colon\ f(i)=\mathrm{sgn}((\alpha_{1}\cdot
v_{i})(\alpha_{2}\cdot v_{i})).$

######  Corollary 13.

Given $N$ points in $\mathbb{R}^{M}$, the number of two colorings
$f\colon[N]\to\\{-1,1\\}$ that are separable by two hyperplanes is at most
$C(N,M)^{2}$.

###### Proof.

Let $S\subset\mathbb{R}^{M}$ be given and suppose that $f$ is a coloring that
is separated by the hyperplanes $H_{1}$ and $H_{2}$. Then there exist
colorings $f_{1},f_{2}$ that are separated by the hyperplanes $H_{1}$ and
$H_{2}$ respectively. Since there are at most $C(N,M)$ choices for each of
$f_{1}$ and $f_{2}$, the number of such colorings $f$ is bounded by
$C(N,M)^{2}$. ∎

######  Lemma 14.

Let $m\leq n$ be two positive integers. The number of Boolean functions
$f\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$ with rational degree at most $m$ is at
most $C(2^{n},\binom{n}{\leq m})^{2}$.

###### Proof.

Let $M=\binom{n}{\leq m}$. For each $x\in\\{-1,1\\}^{n}$ define
$v_{x}\in\mathbb{C}^{M}$ by letting $(v_{x})_{S}=\chi_{S}(x)$ for
$S\subseteq[n]$, $\left\lvert S\right\rvert\leq m$. Suppose $p/q$ is a
rational representation of $f$ of degree at most $m$. Then

$\displaystyle
f(x)=\mathrm{sgn}(p(x)/q(x))=\mathrm{sgn}(p(x)q(x))=\mathrm{sgn}((\widehat{p}\cdot
v_{x})(\widehat{q}\cdot v_{x})).$

Thus the coloring given by $f$ is separated by the hyperplanes defined by
$\widehat{p}$ and $\widehat{q}$. The result follows by Corollary 13. ∎

We can now state and prove our extremal lower bound on rational degree.

######  Corollary 15.

All but a negligible fraction of Boolean functions on $n$ variables have
rational degree at least $n/2-\mathcal{O}(\sqrt{n})$.

###### Proof.

Write $m=n/2-\sqrt{cn}$ for some constant $c$, and let $N=2^{n}$. Then by
Corollary 13 there are at most $C\bigl{(}N,\binom{n}{\leq m}\bigr{)}^{2}$
Boolean functions on $n$ variables of rational degree less than $m$. By the
Chernoff bound $\binom{n}{\leq n/2-\lambda}<2^{n}e^{-2\lambda^{2}/n}$ and the
Hamming bound, we have that the proportion of Boolean functions with rational
degree strictly less $m$ is bounded above by

$\displaystyle\frac{C\bigl{(}N,\binom{n}{\leq
m}\bigr{)}^{2}}{2^{N}}\leq\frac{C(N,Ne^{-2c})^{2}}{2^{N}}\leq
O\bigl{(}2^{N(2h_{2}(e^{-2c})-1)}\bigr{)},$

where $h_{2}(\cdot)$ denotes the binary entropy function. Solving the
inequality $h_{2}(e^{-2c})<1/2$ numerically we find that for $c\geq 1.104$,
the above bound tends to $0$. ∎

##  4 Applications in Complexity Theory

In this section, we give two functions: one whose rational degree is
unboundedly higher than its approximate degree and one which has approximate
degree unboundedly higher than its rational degree. These examples in turn
give bidirectional separations between $\bqp$ and $\posteqp$ with respect to
generic oracles. We conclude the section by giving evidence that zero-error
quantum computation with post-selection gives advantage over bounded-error
randomized algorithms, providing context to our results.

###  4.1 Post-Selection can be a Weak Resource

In this subsection, we give an oracle which witnesses that
$\bqp\not\subseteq\posteqp$ (in fact, even $\rp\not\subseteq\posteqp$). This
is accomplished by constructing a partial function which has constant 1-sided
error randomized query complexity but maximal $\func{PostQ}_{E}$. In fact,
this problem also demonstrates that the rational degree can be arbitrarily
higher than the approximate degree for partial functions.

######  Problem 16 (Majority or None).

The ${\text{MajOrNone}}_{n}$ function is defined as a partial Boolean function
on the set of bitstrings $x\in\\{0,1\\}^{n}$ that have Hamming weight either
$0$ or at least $n/2$. The function ${\text{MajOrNone}}_{n}$ takes value $0$
in the former case, and takes value $1$ otherwise.

######  Theorem 17.

The ${\text{MajOrNone}}_{n}$ function can be decided by a quantum algorithm
using constantly many queries, yet its rational degree is at least
$\Omega(n)$. Consequently, ${\text{MajOrNone}}_{n}$ witnesses the following
separations:

$\displaystyle\widetilde{\vphantom{t}\smash{\mathrm{deg}}}({\text{MajOrNone}}_{n})$
$\displaystyle\leq\mathcal{O}(1)\quad\text{ yet
}\quad\operatorname{rdeg}({\text{MajOrNone}}_{n})$
$\displaystyle\geq\Omega(n),$ $\displaystyle\func{Q}({\text{MajOrNone}}_{n})$
$\displaystyle\leq\mathcal{O}(1)\quad\text{ yet
}\quad\func{PostQ}_{E}({\text{MajOrNone}}_{n})$ $\displaystyle\geq\Omega(n).$

###### Proof.

The ${\text{MajOrNone}}_{n}$ function even has constant $\RP$ query
complexity. Indeed, we may simply query a constant number of random bits and
output $1$ if any of them are $1$. Therefore, ${\text{MajOrNone}}_{n}$ has
constant quantum query complexity, which in turn implies a constant
approximate degree. We show via a rational degree lower bound that
$\func{PostQ}_{E}({\text{MajOrNone}}_{n})=\Omega(n)$. In particular, we show
that $\mathrm{rdeg}({\text{MajOrNone}}_{n})=\Omega(n)$. Using the notation of
Lemma 5, for ${\text{MajOrNone}}_{n}$ we have $|S_{1}|\geq n/2$, giving us

$\func{PostQ}_{E}({\text{MajOrNone}}_{n})\geq\mathrm{rdeg}({\text{MajOrNone}}_{n})=\Omega(n).\qed$

The complexity classes $\func{Q}$ and $\func{PostQ}_{E}$ are the query
complexity equivalents of $\bqp$ and $\posteqp$, respectively. As such, our
unbounded separation between these complexity measures gives a separation of
$\bqp$ and $\posteqp$ with respect to a generic oracle.

######  Corollary 18.

There exists an oracle $O$ such that $\rp^{O}\not\subseteq\posteqp^{O}$. ∎

###  4.2 Post-Selection can be a Strong Resource

On the other hand, we can give an oracle which witnesses
$\posteqp\not\subseteq\bqp$. We do this by constructing a promise problem $f$
for which $\func{PostQ}_{E}(f)=\mathcal{O}(1)$ but
$\func{Q}_{\varepsilon}(f)\geq\Omega(n)$. This problem also witnesses the fact
that approximate degree can be unboundedly larger than rational degree.

######  Problem 19 (Imbalance).

Let $n=4m+2$ for some positive integer $m$. Define the functions
$L,R:\\{-1,1\\}^{n}\rightarrow\mathbb{R}$ as
$L(x)=x_{1}+x_{2}+\ldots+x_{2m+1}$ and $R(x)=x_{2m+2}+\ldots+x_{4m+2}$. Then
the ${\text{Imbalance}}\colon\\{-1,1\\}^{n}\to\mathbb{R}$ function is defined
as ${\text{Imbalance}}(x)=\frac{L(x)}{R(x)}$.

Note that we assumed $4\nmid n$ to ensure that the denominator $R(x)$ cannot
be 0.

######  Problem 20 (Boolean Imbalance).

Let $m$ and $n$ be as in the above problem. We define the Boolean Imbalance
${\text{BI}}_{n}$ function as the restriction of Imbalance to the union
$S_{-}\cup S_{+}$ where we let

$\displaystyle S_{+}$
$\displaystyle=\\{(x_{L},x_{R})\colon|x_{L}|=|x_{R}|=m\\},$ $\displaystyle
S_{-}$ $\displaystyle=\\{(x_{L},x_{R})\colon|x_{L}|+|x_{R}|=2m+1\text{ and
}|x_{L}|,|x_{R}|\geq m\\}.$

Note that ${\text{BI}}_{n}(x)=1$ for any $x\in S_{+}$ since the numerator and
denominator evaluate to the same quantity. On the other hand, for any $x\in
S_{-}$ we have that ${\text{BI}}_{n}(x)=-1$ since both $L(x)$ and $R(x)$ must
be $\pm 1$ but they must be different.

By a generalisation of the equivalence of Mahadev and de Wolf (Lemma 25) we
have an upper bound of 2 on $\func{PostQ}_{E}({\text{BI}}_{n}$). We now show
that it has a linear lower bound on the approximate degree.

######  Lemma 21.

The ${\text{BI}}_{n}$ function can be decided by a postselected quantum
algorithm using only 2 queries, yet its rational degree is at least
$\Omega(n)$. Consequently, ${\text{BI}}_{n}$ witnesses the following
separations:

$\displaystyle\operatorname{rdeg}({\text{BI}}_{n})$
$\displaystyle\leq\mathcal{O}(1)\quad\text{ yet
}\quad\widetilde{\vphantom{t}\smash{\mathrm{deg}}}({\text{BI}}_{n})$
$\displaystyle\geq\Omega(n),$ $\displaystyle\func{PostQ}_{E}({\text{BI}}_{n})$
$\displaystyle\leq\mathcal{O}(1)\quad\text{ yet
}\quad\func{Q}({\text{BI}}_{n})$ $\displaystyle\geq\Omega(n).$

###### Proof.

Note that ${\text{BI}}_{n}$ is defined on inputs of Hamming weight $2m$ and
$2m+1$. By a result of Nayak and Wu any function which is constant on Hamming
slices $l,l+1$ and flips its value has approximate degree
$\Omega(\max\\{l,n-l\\})$ [NW99]. In this case, since the function value flips
on Hamming weights $2m,2m+1$ we get a lower bound of
$\Omega(\max\\{2m+1,2m\\})=\Omega(n)$. ∎

Finally, just like in the previous section, this separation between complexity
measures allows us to construct an oracle relative to which $\posteqp$ is not
contained in $\bqp$.

######  Corollary 22.

There exists an oracle $O$ such that $\posteqp^{O}\not\subseteq\bqp^{O}$. ∎

Our unbounded separation of rational degree and approximate degree gives a
generic oracle separation of $\posteqp$ and $\bqp$. Combined with Corollary
18, this tells us that zero-error post-selection and bounded error are
incomparable resources in the black-box model: one is not stronger than the
other.

###  4.3 Post-Selection and Non-Determinism

To conclude the section, we provide more context to our results by giving
evidence that zero-error quantum computation with post-selection gives
advantage over efficient classical computation.

######  Claim 23.

$\NP\cap\coNP\subseteq\posteqp$.

###### Proof.

Let $L\in\NP\cap\coNP$. Since $L\in\NP$, there is an efficient algorithm
$M_{1}$ and a polynomial $p_{1}$ such that for every $x\in L$, there exists
$u_{1}\in\\{0,1\\}^{p_{1}(|x|)}$ such that $M_{1}(x,u_{1})=1$ and for every
$x\not\in L$ and $u\in\\{0,1\\}^{p_{1}(|x|)}$ we have $M_{1}(x,u)=0$.
Similarly since $L\in\coNP$ there is an efficient algorithm $M_{2}$ and
polynomial $p_{2}$ such that for every $x\not\in L$, there exists
$u_{2}\in\\{0,1\\}^{p_{2}(|x|)}$ such that $M_{2}(x,u_{2})=1$ and for every
$x\in L$ and $u_{2}\in\\{0,1\\}^{p_{2}(|x|)}$ we have $M_{2}(x,u_{2})=0$.

Now, given $x$, our quantum computer can generate a uniform superposition over
all the possible certificates for both $M_{1}$ and $M_{2}$ (concatenated
together), and post-select on the event that either $M(x,u_{1})=1$ or
$M_{2}(x,u_{2})=1$. Then, the quantum algorithm can measure all registers and
simulate both $M_{1}(x,u_{1})$ and $M_{2}(x,u_{2})$ and see which one is 1. By
definition, only one of $M_{1}$ and $M_{2}$ will accept, and whichever one
accepts tells us if $x\in L$ or not. ∎

It is widely believed that $\NP\cap\coNP$ is not contained in $\P$ or even
$\bpp$. As such, there is reason to believe that zero-error quantum algorithms
with post-selection can offer advantage over efficient classical computation.

##  5 Open Questions

In this paper, we considered the problem of lower bounding the rational degree
of Boolean functions in terms of their Fourier degree. While we could not
answer this question in its full generality, we showed that the square root of
the degree lower bounds the rational degree for both monotone and symmetric
Boolean functions. We conjecture that this lower bound extends to all total
Boolean functions.

######  Conjecture 2.

For all Boolean functions $f\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$,
$\sqrt{\mathrm{deg}(f)}\leq\operatorname{rdeg}(f)$.

Answering this conjecture in the affirmative would place rational degree
within a plethora of Boolean function complexity measures all of which are
polynomially related. Recall that for partial functions, we have unbounded
separations between the rational and approximate degrees in both directions.

In this work, we showed that a hypothetical total function that witnesses any
such separation must lack a certain level of structure: in particular, it
cannot be symmetric, monotone, or expressible by a low-depth read-once Boolean
formula. In this direction, an easier question is whether there are other
classes of functions for which rational degree cannot be separated from
Fourier degree. Some candidates that may be amenable to current techniques
include unate and transitive-symmetric functions. In particular, showing that
unate functions have polynomial rational degree would, in turn, imply
polynomial rational degree lower bounds for read-once $\TC_{0}$ circuits by
adapting our result for read-once Boolean formulae with symmetric gates.

We also proved that almost all Boolean functions
$f\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$ have rational degree at least
$n/2-\mathcal{O}(\sqrt{n})$. As mentioned in the preliminaries O’Donnell and
Servedio proved [OS08] that almost all Boolean functions
$f\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$ have sign degree at most
$n/2+\mathcal{O}(\sqrt{n\log{n}})$. It would be interesting to know if an
analogous result can be established for the rational degree.

######  Conjecture 3.

All but a negligible fraction of Boolean functions
$f\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$ have rational degree at most $n/2+o(n)$.

### Acknowledgements

The authors thank Scott Aaronson, Yuval Filmus, Lance Fortnow, Sabee Grewal,
Robin Kothari, Geoffrey Mon, Rocco Servedio, Avishay Tal, Ronald de Wolf, and
David Zuckerman for helpful conversations.

VI and SJ are supported by Scott Aaronson’s Vannevar Bush Fellowship from the
US Department of Defense, the Berkeley NSF-QLCI CIQC Center, a Simons
Investigator Award, and the Simons “It from Qubit” collaboration. VI is
supported by a National Science Foundation Graduate Research Fellowship. MKD
and DW acknowledge support from the Army Research Office (grant
W911NF-20-1-0015) and the Department of Energy, Office of Science, Office of
Advanced Scientific Computing Research, Accelerated Research in Quantum
Computing program. VMK acknowledges support from NSF Grant CCF-2008076 and a
Simons Investigator Award (#409864, David Zuckerman). MW was supported by NSF
grant CCF-2006359.

## References

  * [AB23] Andris Ambainis and Aleksandrs Belovs.  An exponential separation between quantum query complexity and the polynomial degree.  In Proceedings of the 38th Annual Conference on Computational Complexity (CCC), 2023.  arXiv:2301.09218, doi:10.4230/LIPIcs.CCC.2023.24.
  * [ABDK+21] Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal.  Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, page 1330–1342, 2021.  arXiv:2010.12629, doi:10.1145/3406325.3451047.
  * [AK] Scott Aaronson and Greg Kuperberg.  Complexity zoo.  https://complexityzoo.net/Complexity_Zoo.
  * [Alo93] Noga Alon.  Personal communication to M. Saks.  Reported in M. Saks, Slicing the Hypercube, 1993.
  * [Ant95] Martin Anthony.  Classification by polynomial surfaces.  Discrete Applied Mathematics, 61(2):91–103, 1995.  doi:10.1016/0166-218X(94)00008-2.
  * [BBC+01] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf.  Quantum lower bounds by polynomials.  Journal of the ACM, 48(4):778–797, 2001.  arXiv:quant-ph/9802049.
  * [BKT20] Mark Bun, Robin Kothari, and Justin Thaler.  The polynomial method strikes back: Tight quantum query bounds via dual polynomials.  Theory of Computing, 16(10):1–71, 2020.  doi:10.4086/toc.2020.v016a010.
  * [BW02] Harry Buhrman and Ronald de Wolf.  Complexity measures and decision tree complexity: a survey.  Theoretical Computer Science, 288(1):21–43, 2002.  doi:10.1016/S0304-3975(01)00144-X.
  * [Cov65] Thomas M. Cover.  Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition.  IEEE Transactions on Electronic Computers, EC-14(3):326–334, 1965.  doi:10.1109/PGEC.1965.264137.
  * [For03] Lance Fortnow.  Computational complexity - rational functions and decision-tree complexity.  https://blog.computationalcomplexity.org/2003/11/rational-functions-and-decision-tree.html, 2003.
  * [FSS81] Merrick Furst, James B. Saxe, and Michael Sipser.  Parity, circuits, and the polynomial-time hierarchy.  In 22nd Annual Symposium on Foundations of Computer Science, pages 260–270, 1981.  doi:10.1109/SFCS.1981.35.
  * [Hua19] Hao Huang.  Induced subgraphs of hypercubes and a proof of the sensitivity conjecture.  Ann. of Math. (2), 190(3):949–955, 2019.  arXiv:1907.00847, doi:10.4007/annals.2019.190.3.6.
  * [MP69] Marvin Minsky and Seymour Papert.  Perceptrons.  MIT Press, Cambridge, MA, 1969.
  * [MW15] Urmila Mahadev and Ronald de Wolf.  Rational approximations and quantum algorithms with postselection.  Quantum Info. Comput., 15(3–4):295–307, 2015.  arXiv:1401.0912, doi:10.48550/ARXIV.1401.0912.
  * [NC11] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, USA, 10th edition, 2011.
  * [Nis91] Noam Nisan.  Crew prams and decision trees.  SIAM Journal on Computing, 20(6):999–1007, 1991.  doi:10.1137/0220062.
  * [NS92] Noam Nisan and Mario Szegedy.  On the degree of boolean functions as real polynomials.  In Proceedings of the 24th ACM Symposium on Theory of Computing (STOC), pages 462–467. ACM, 1992.  doi:10.1145/129712.129757.
  * [NW95] Noam Nisan and Avi Wigderson.  On rank vs. communication complexity.  Combinatorica, 15(4):557–565, 1995.  doi:10.1007/BF01192527.
  * [NW99] Ashwin Nayak and Felix Wu.  The quantum query complexity of approximating the median and related statistics.  In Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), pages 384–393. ACM, New York, 1999.  doi:10.1145/301250.301349.
  * [O’D14] Ryan O’Donnell.  Analysis of Boolean functions.  Cambridge University Press, New York, 2014.  arXiv:2105.10386, doi:10.1017/CBO9781139814782.
  * [OS08] Ryan O’Donnell and Rocco A. Servedio.  Extremal properties of polynomial threshold functions.  Journal of Computer and System Sciences, 74(3):298–312, 2008.  Computational Complexity 2003.  doi:10.1016/j.jcss.2007.06.021.
  * [Sak93] Michael E. Saks.  Slicing the hypercube, page 211–256.  London Mathematical Society Lecture Note Series. Cambridge University Press, 1993.  doi:10.1017/CBO9780511662089.009.
  * [Wol00] Ronald de Wolf.  Characterization of non-deterministic quantum query and quantum communication complexity.  In Proceedings of the 15th Annual Conference on Computational Complexity (CCC), pages 271–278. 2000.  arXiv:cs/0001014, doi:10.1109/CCC.2000.856758.

##  Appendix A Rational Degree and Query Complexity with Post-Selection

In this appendix, we show that the main theorem of [MW15], stated for total
Boolean functions, in fact also holds for partial ones. We do so simply by
observing that the proof given in [MW15] also works for partial Boolean
functions.

######  Theorem 24.

For any (possibly partial) Boolean function $f$ on $n$ variables and
$\varepsilon\in[0,1/2)$,
$\operatorname{rdeg}_{\varepsilon}(f)=\Theta(\func{PostQ}_{\varepsilon}(f))$.

First we show that rational degree lower bounds quantum query complexity with
post-selection.

######  Lemma 25.

Let $D\subseteq\\{0,1\\}^{n}$ and consider $f\colon D\to\\{0,1\\}$. Then
$\operatorname{rdeg}_{\varepsilon}(f)\leq\func{PostQ}_{\varepsilon}(f)$.

###### Proof.

Suppose there is a $T$-query post-selected $\varepsilon$-error algorithm for
$f$. As in Definition 4 let $a(x)$ be the random variable corresponding to the
measurement of the post-selected qubit and $b(x)$ the random variable
corresponding to the measurement of the output qubit. We have that

$\displaystyle\left\lvert\Pr[b(x)=1|a(x)=1]-f(x)\right\rvert\leq\varepsilon.$

Now, by [BBC+01], the amplitudes of a quantum algorithm after $T$ oracle
queries are polynomials in $x_{1},\dots,x_{n}$ of degree at most $2T$. It
immediately follows that $\Pr[a(x)\land b(x)=1]$ and $\Pr[a(x)=1]$ are
polynomials of degree at most $2T$: call them $p$ and $q$ respectively. Thus
we have

$\displaystyle\left\lvert\dfrac{p(x)}{q(x)}-f(x)\right\rvert=\left\lvert\Pr[b(x)=1|a(x)=1]-f(x)\right\rvert\leq\varepsilon,$

which gives us the desired rational approximation of $f$. ∎

Now, we show that, up to a constant factor, the rational degree upper bounds
quantum query complexity with post-selection. The proof is Fourier analytic,
and so we switch to the $\\{-1,1\\}$ basis.

######  Lemma 26.

Let $D\subseteq\\{-1,1\\}^{n}$ and consider $f\colon D\to\\{-1,1\\}$. Then
$\func{PostQ}_{\varepsilon}(f)\leq 2\operatorname{rdeg}_{\varepsilon}(f)$.

###### Proof.

Suppose $f\colon D\to\\{-1,1\\}^{n}$ has an $\varepsilon$-approximate rational
representation $p/q$ such that $\max\\{\mathrm{deg}(p),\mathrm{deg}(q)\\}=d$.
Considering the Fourier expansions of $p,q$, we can construct the state

$\sum_{S\subseteq[n]}\widehat{p}(S)\ket{0}\ket{S}+\widehat{q}(S)\ket{1}\ket{S},$

where $\ket{S}$ is the basis state that corresponds to the indicator bitstring
for the set $S$. For simplicity, we have left out normalizing constants. Then,
using $\max\\{\mathrm{deg}(p),\mathrm{deg}(q)\\}=d$ queries to $x$, we can
construct the state

$\sum_{S\subseteq[n]}\widehat{p}(S)\chi_{S}(x)\ket{0}\ket{S}+\widehat{q}(S)\chi_{S}(x)\ket{1}\ket{S}.$

Now we apply an $n$-qubit Hadamard to the second register, obtaining the state

$\ket{0}\left(\sum_{S\subseteq[n]}\widehat{p}(S)\ket{0^{n}}+...\right)+\ket{1}\left(\sum_{S\subseteq[n]}\widehat{q}(S)\ket{0^{n}}+...\right)$

after which we postselect on the second register being equal to $0^{n}$. This
gives us the (again, unnormalized) state

$\ket{0}\left(\sum_{S\subseteq[n]}\widehat{p}(S)\ket{0^{n}}\right)+\ket{1}\left(\sum_{S\subseteq[n]}\widehat{q}(S)\ket{0^{n}}\right)=\left(p(x)\ket{0}+q(x)\ket{1}\right)\ket{0^{n}}.$

After discarding the second register and normalizing, we are left with

$\frac{p(x)}{p(x)^{2}+q(x)^{2}}\ket{0}+\frac{q(x)}{p(x)^{2}+q(x)^{2}}\ket{1}.$

We measure this state in the Hadamard basis and interpret the result as having
value in $\\{-1,1\\}$. If $f(x)=-1$, then
$p(x)/q(x)\in[-1-\varepsilon,-1+\varepsilon]$. The probability of measuring
$\ket{-}$ is

$\frac{(q(x)-p(x))^{2}}{2(p(x)^{2}+q(x)^{2})}=\frac{(1-p(x)/q(x))^{2}}{2((p(x)/q(x))^{2}+1}\leq\frac{\varepsilon^{2}}{2(1+(1-\varepsilon)^{2})}\leq\varepsilon.$

∎

Note that in the proof of Lemma 25 we get a rational polynomial which is
bounded outside of the promise. Therefore, as a consequence we have that
imposing this boundedness condition only increases the
$\varepsilon$-approximate rational degree by at most a factor of 2.