# Inductive biases, pretraining and fine-tuning jointly account for brain
responses to speech

Juliette MILLET  Jean-Rémi KING

###### Abstract

Our ability to comprehend speech remains, to date, unrivaled by deep learning
models. This feat could result from the brain’s ability to fine-tune generic
sound representations for speech-specific processes. To test this hypothesis,
we compare i) five types of deep neural networks to ii) human brain responses
elicited by spoken sentences and recorded in 102 Dutch subjects using
functional Magnetic Resonance Imaging (fMRI). Each network was either trained
on an acoustics scene classification, a speech-to-text task (based on Bengali,
English, or Dutch), or not trained. The similarity between each model and the
brain is assessed by correlating their respective activations after an optimal
linear projection. The differences in brain-similarity across networks
revealed three main results. First, speech representations in the brain can be
accounted for by random deep networks. Second, learning to classify acoustic
scenes leads deep nets to increase their brain similarity. Third, learning to
process phonetically-related speech inputs (i.e., Dutch vs English) leads deep
nets to reach higher levels of brain-similarity than learning to process
phonetically-distant speech inputs (i.e. Dutch vs Bengali). Together, these
results suggest that the human brain fine-tunes its heavily-trained auditory
hierarchy to learn to process speech.

keywords

##  1 Introduction

To understand speech, the human brain continuously transforms and parses the
stream of auditory features generated by the cochleas. To date, this ability
remains unrivaled by deep learning architectures, especially in noisy or
accented speech conditions (Zhang et al., 2020; Unni et al., 2020), partly
because the exact nature of speech representations remains underdetermined.
Indeed, while the brain – and the superior temporal cortex in particular –
represents and clusters phonetic features (Mesgarani et al., 2014; Kell et
al., 2018), the corresponding representations may not be specific to speech
but generic to sounds (Galantucci et al., 2006; Daube et al., 2019). It is
thus unclear whether speech models should be trained with speech input only or
from a wide variety of sounds.

We propose to address this issue by comparing i) the brain representations
elicited during speech comprehension to ii) the representations of artificial
neural networks, input with the same sounds, and trained in three distinct
regimes: random neural networks (i.e. not trained), neural networks trained to
process generic sounds (i.e. acoustic scene classification), and neural
networks trained to process speech (i.e. speech-to-text using Dutch, English
or Bengali). Previous studies have already shown that deep convolutional
neural networks trained to classify words, musical genres (Kell et al., 2018;
Kumar et al., 2020) or natural sounds (Koumura et al., 2019), generate brain-
like representations, in the sense that one can find a linear correspondence
between the activation of the neural networks and the activations of the brain
(Figure 1). This similarity can be quantified with a ”brain score” (Yamins et
al., 2014), a correlation between the brain measurements and a linear
projection of the model’s activations, under the assumption that
representations are defined as linearly exploitable information (Hung et al.,
2005; Kamitani & Tong, 2005; Kriegeskorte & Kievit, 2013; King et al., 2018).
We thus hypothesize that the nature of speech representations in the brain can
be elucidated by comparing them to those of random, sound-generic and speech-
specific neural networks (Figure 1).

To this end, we analyze the functional Magnetic Resonance Imaging (fMRI)
recordings of 102 Dutch speakers who each underwent a 1 h speech comprehension
task, consisting of sequences of unrelated sentences. We then compared, for
each subject separately, the resulting blood oxygenation level dependent
(BOLD) responses to the activations of 30 deep neural networks, all derived
from the same architecture taken from DeepSpeech 2 (Amodei et al., 2016).

We formalize our hypotheses with the following non-mutually exclusive
predictions (Figure 1): the brain representations of speech are likely to
benefit from an inductive bias if a random neural network can generate
representations similar to those of the brain, generic if a neural network
trained on non-speech sounds leads to representations that are more similar to
brain activity than a random network, speech-specific if a neural network
trained on speech sounds leads to representations that are more similar to
brain activity than a network trained on non-speech sounds, phoneme-specific
if a neural network trained on a language that roughly contains the same
speech sounds (or phonemes) than the participants’ native language (e.g.
English vs Dutch) leads to representations that are more similar to brain
activity than a network trained on a language that has a very different
phonemes inventory (e.g. Bengali vs Dutch), and language-specific if a neural
network trained on the same language as the participants’ native language
(i.e. Dutch) leads to representations that are more similar to brain activity
than a network trained on a distinct, but phonetically-related language (e.g.
Dutch vs English).

Our results support several of these predictions. First, the architecture of
the network, without training, suffices to significantly account for the
hierarchy of brain responses to speech. Second, training on auditory-scene
classification increases the brain-similarity of the networks. Third, training
on English leads to higher brain scores than training on Bengali. Together,
these results suggest that the brain combines inductive biases, generic, and
phoneme-specific representations to process speech.

Figure 1: A. The functional similarity between an artificial neural network
and the human brain was quantified by correlating i) brain responses to speech
to ii) the networks’activations in response to the same input, and optimally
projected with a linear operator $W$ onto the subject brain. To this end, a
linear ridge regression ($W$) is fit from the model’s activations convolved by
an HRF ($X$) to the brain response ($Y$) to the same stimulus sequence. The
resulting ”brain score” (Yamins et al., 2014) is a Pearson correlation between
true brain activity and the brain activity predicted by a linear projection of
the model’s activation. B. Four types of networks, using the same architecture
were trained on Dutch, English, and Bengali speech-to-text and on a acoustic
scene classification, respectively. The fifth network corresponds to an
untrained version, randomly initialised. Each type was trained with six random
seeds, leading to a total of 30 networks. C. The neural networks will be
considered to show no similarity with brain activity if they show brain scores
(R) not significantly above zero.

##  2 Methods

###  2.1 Stimuli

One-hundred and two subjects performed a simple speech comprehension task
while being recorded with functional Magnetic Resonance Imaging (fMRI) by
Schoffelen and colleagues (Schoffelen et al., 2019). Each participant listened
to 60 isolated sentences, grouped in series of five and selected from a pool
of 360 sentences, varying from 9 to 15 words. Each sentence lasted on average
$4.28\pm 0.6$ seconds (maximal length: 6s, minimal length: 2.8s), for a total
of 28 min and 49 seconds. All sentences were recorded by a unique female
native Dutch speaker in stereo at 44.1 kHz. We downsample the recordings to 16
kHz and convert them to mono with the Sox software
111http://sox.sourceforge.net/. Note that the dataset also contains word lists
that are not presently analyzed. However, these sound sequences included
silences between each word and thus lead to abnormal speech inputs.

###  2.2 fMRI preprocessing

Data were provided (in part) by the Donders Institute for Brain, Cognition and
Behaviour. Each subject performed two MRI scans performed: a structural
T1-weighted magnetization-prepared rapid gradient-echo (MP-RAGE) pulse
sequence (TR=2,300 ms, TE=3.03 ms, 8 degree flip-angle, 1 slab, slice-matrix
size=256×256, slice thickness=1 mm, field of view=256 mm, isotropic voxel-
size=1.0×1.0×1.0 mm) and a functional T2∗-weighted echo planar blood
oxygenation level dependent (EPI-BOLD) sequence (TR=2.0 seconds, TE=35ms, flip
angle=90 degrees, anisotropic voxel size=3.5×3.5×3.0 mm extracted from 29
oblique slices.) Additional acquisition details can be found in Schoffelen et
al. (2019).

Structural images were defaced by Schoffelen and colleagues. We then
preprocessed them with Freesurfer (Fischl, 2012), using the recon-all pipeline
with default parameters and a manual inspection of the cortical segmentations.
Region-of-interest analyses of regions the primary auditory cortex A1, Belt
(LBelt MBelt PBelt) and TPJ (STV, PFm, PGi) were selected from the PALS
Brodmann’ area atlas (Van Essen, 2005) and the Destrieux Atlas segmentation
(Destrieux et al., 2010).

Functional images are preprocessed with fMRIPrep with default parameters
(Esteban et al., 2019). The Blood Oxygenation Level Dependent (BOLD) time
series are detrended and de-confounded from 18 variables: the six head motion
parameters (transx,y,z, rotx,y,z) estimated analytically, the first 6 noise
components derived from CompCorr (Behzadi et al., 2007) and the 6 DCT-basis
regressors derived from nilearn’s clean_img pipeline and otherwise default
parameters (Abraham et al., 2014b). The resulting volumetric data are
projected onto the surface, after subselecting voxels along a 3mm “line”
orthogonal to the mid-thickness. Surface projections are spatially decimated
by 10, and are hereafter referred to as voxels, for simplicity.

To mitigate slow drifts in fMRI acquisition, the recordings of each group of 5
sentences are separately and linearly detrended. The 12 cross-validation
splits are applied across 5-sentences blocks (i.e., across detrended segments)
to ensure no information leakage between the training and testing sets.

###  2.3 Networks

We train and analyze the activations of five distinct types of neural networks
(training details are in the next section). All networks share the same
architecture derived from Deepspeech 2 (Amodei et al., 2016), and are all
input with spectrograms $U\in\mathbb{R}^{d_{\tau}\times d_{u}}$ ($d_{u}=160$)
of mono-sound waveforms computed with librosa’s stft function (McFee et al.,
2019) squared using: window size 20 milliseconds, window stride of 10 ms, and
n_ftt = 320. These spectrograms are transformed by a hierarchy of three 2D
convolutional layers (with Layer 1: kernel $k_{1}=11\times 41$, stride
$s_{1}=2\times 2$, number of channels $c_{1}=32$; Layer 2: $k_{2}=11\times
21$, $s_{2}=1\times 2$, $c_{2}=64$, Layer 3: $k_{3}=11\times 21$,
$s_{3}=1\times 2$, $c_{3}=96$), followed by one bidirectional gated recurrent
unit (GRU, 1 layer with dimension 256) and ending in a fully connected layer,
whose dimensionality varies with the task (see below). A rectified linear unit
(ReLU) function is used between each layer. Finally, a softmax layer is
applied on the linear layer’ outputs to obtain a probability distribution over
characters or acoustic-scene classes.

###  2.4 Tasks

To test our hypotheses, We train each network on one of four different
datasets (Figure 1). The Dutch and the English datasets are taken from the
aligned part of the Spoken Wikipedia Corpora (Baumann et al., 2018). The
Bengali dataset is taken from Kjartansson et al. (2018). In order to have
approximately the same number of characters possible for the three languages
we romanize the Bengali transcriptions using URoman (Hermjakob et al., 2018).
Finally, the acoustic scene classification dataset is extracted from the
curated subset of the FSDKaggle2019 dataset (Fonseca et al., 2019) with manual
annotations (Fonseca et al., 2017).

We use 66 hours and 20 minutes (roughly 100,000 sentences) of the first three
datasets to match the Dutch dataset, and ensure that the networks had a
similar data exposure. We restrict the scene acoustic dataset to its curated
version (10 hours long) to avoid introducing noisy labels. Each dataset is
then divided into a training (80%), a validation (10%) and a test set (10%).
Input samples are limited to a maximum length of 20 seconds.

Each model $m$ was trained using Connectionist Temporal Classification (CTC)
(Graves et al., 2006) parameterized over $\theta$:

$\mathop{\rm arg\,min}_{\theta}-\log\sum_{a\in
a_{U,V}}\prod_{t}^{d_{t}}p_{CTC}\left(a_{t}\mid m_{\theta}(U)\right)$ (1)

where $m_{\theta}(U)\in\mathbb{R}^{d_{\tau}\times d_{v}}$ are the
probabilistic predictions of the networks at each $\tau$ time sample given the
spectrograms $U\in\mathbb{R}^{d_{\tau}\times d_{u}}$,
$V\in\mathbb{R}^{d_{t}\times d_{v}}$ are the true transcriptions of $U$, and
$a_{U,V}$ is the set of all possible alignments between $U$ and $V$.

For the models trained on speech recognition, $V$ is a textual transcription.
Consequently, $d_{v}$ is the number of possible characters: $d_{v}=37$ for
Dutch, $d_{v}=28$ for English and Bengali. For the models trained on acoustic
scene classification, $V$ is a one hot vector indicating the class of $U$:
i.e. $d_{v}=80$ classes.

The models are trained with Openseq2seq (Kuchaiev et al., 2018), with six
different initialisation seeds for each dataset, using stochastic gradient
descent with the following optimization hyperparameters: momentum of $0.9$, an
initial learning rate of $0.001$, a polynomial decay policy with power $2$, a
batch size of $8$. After each gradient descent, we select the model based on
its performance on the validation set, with a maximum number of training steps
of 70,000. For each setting, we compute the brain scores for each
initialisation and present the average results across initialisations, for
simplicity.

On average, the Dutch, English and Bengali models achieved a Word Error Rate
(WER) of 0.59, 0.78, and 0.85, on their respective test sets. The acoustic
scene classification models achieve a class error rate of 0.64. These modest
performances results from a design choice: to avoid semantic representations,
we deliberately decided not to incorporate a pretrained language model feeding
the architecture.

###  2.5 Preprocessing of model activations

The activations of the models are sampled at a different frequency ($1/t=50$
Hz) than the fMRI BOLD signals ($1/\hat{t}=0.5$ Hz). Furthermore, BOLD signals
are known to be slow and delayed responses spanning over several seconds. To
align the activations of the models and the fMRI BOLD signals, we thus
convolve the model activations with a standard hemodynamic response function
(HRF). Specifically, activations of the network
$m(U)\in\mathbb{R}^{d_{\hat{t}}\times d_{x}}$ are normalized between $[0,1]$.
We then use nistats (Abraham et al., 2014a) compute_regressor function with
the glover model to temporally convolve ($h\in\mathbb{R}^{d_{t}}$) and
temporally downsample
($g:\mathbb{R}^{d_{\hat{t}}}\rightarrow\mathbb{R}^{d_{t}}$) each artificial
neuron $j$:

$x^{(j)}=g\Big{(}m^{(j)}(U)*h\Big{)}$ (2)

###  2.6 Brain score

The similarity between the preprocessed model’s activations
$X\in\mathbb{R}^{d_{t}\times d_{x}}$ and the BOLD response
$Y\in\mathbb{R}^{d_{t}\times d_{y}}$ is assessed with a ”brain score” (Yamins
et al., 2014). Specifically, we use a cross-validation within each subject (12
train-test splits across 5 sentences series) to fit an $L_{2}$-regularized
linear model $W\in\mathbb{R}^{d_{x}\times d_{y}}$ trained to predict the BOLD
time series from the model activations for each voxel independently:

$\mathop{\rm arg\,min}_{w}\ \sum_{i}(w^{T}X_{i}-y_{i})^{2}+\lambda\|w\|^{2}$
(3)

with $X$ and $y$ normalized across samples to have a mean of 0 and and a
variance of 1, and the training samples $i\in I$ .

Optimization is done using RidgeCV from scikit-learn (Pedregosa et al., 2011),
with the penalization hyper-parameter $\lambda$ varying between 10 and
$10^{8}$ (20 values scaled logarithmically) chosen within nested cross-
validation of the training set and independently selected for each dimension.

The performance of the ridge regression is summarized with a Pearson’s
correlation score between the predicted and the fMRI BOLD responses on the
test samples $I^{*}$, a.k.a ”brain score”:

$R=Corr(y_{I^{*}},w^{T}\cdot X_{I^{*}})$ (4)

Note that we also compute a baseline brain-score with $X$ being the
preprocessed mel filterbanks coefficients (mel) of the auditory stimuli, using
librosa (McFee et al., 2019), 25 milliseconds windowing and strides of 10
milliseconds. These spectro-temporal decompositions were originally engineered
to mimic the cochlear transformations of sounds. They thus provide a
reasonable approximation of the features input to the primary auditory cortex
(Stevens et al., 1937; Stevens & Volkmann, 1940).

###  2.7 Statistics

The reliability of brain scores is assessed with second-level analyses across
subjects, by applying a Wilcoxon signed-rank test across subjects. Statistical
correction for multiple comparisons is performed with Benjamini–Hochberg False
Discovery Rate (FDR) across voxels (Benjamini, 2010). Figures only plot brain
scores that are significant across subjects after this correction.

##  3 Results

Figure 2: A Average (across subjects and random seeds) brain scores obtained
by the random initialisation model. B. Average (across subjects and random
seeds) gains in brain scores ($\Delta R$) between the random initialisation
model and the mel filterbanks, using a concatenation of all sound features and
activations. Gray zones are not statistically significant across subjects
after FDR correction for multiple comparison. C. Average (across subjects and
random seeds) gains in brain scores ($\Delta R$) obtained between four
representative layers of the random initialisation models. D. Average (across
voxels and random seeds) brain scores obtained for each level of concatenation
for the random initialisation models. Error bars indicate SEM across subjects.
Vertical lines and stars indicate significant gains across subjects. Redundant
statistical comparisons are omitted for clarity purposes (e.g. $C>A$ is
omitted when $C>B$ and $B>A$). E.  Same as (B) for the networks trained on
Dutch. F. Same as (C) for the networks trained on Dutch.

###  3.1 Random networks reveal the inductive bias of hierarchical
convolutions

We first aim to test whether random (i.e. not trained) convolutional
architectures generate representations similar to those of the brain. To this
end, we assess, for each subject independently, whether their fMRI responses
$Y$ can be predicted with a linear regression $W$ from the concatenated
activations $X$ of the random intialisation model input with the same speech
sounds, as quantified with a Pearson correlation, hereafter referred to as
”brain scores” ($R$, Figure 2.A). Sound onset and volume are known to trigger
attentional capture in large brain networks (Daube et al., 2019).
Consequently, significant brain scores result from trivial low-level features.
To mitigate this issue, we compare the brain-scores obtained with all layers
$L\in[1,5]$ to those obtained with the mel filterbanks (denoted as $L_{0}$,
Figure 2.B):

$\Delta R=R(X_{L\in[0,5]})-R(X_{0})$ (5)

We perform a similar comparison for each pair of successive layers to identify
the layer-specific representations that correlate with brain responses (Figure
2.C):

$\Delta R_{L}=R(X_{[0,\dots,L]})-R(X_{[0,\dots,L-1]})$ (6)

The results show that the first layers of the model lead to a significant gain
in brain prediction around the primary and secondary auditory areas as well as
in the superior temporal gyrus, whereas the deepest layers led to significant
gains in a distributed set of brain areas. The average brain score obtained by
the random initialisation model for each level of concatenation can be seen in
Figure 2.D.

Overall, these results suggest that 1) the representations generated by random
convolutional networks suffice to predict a significant proportion of the
brain representations of speech _above-and-beyond_ mel filterbanks and 2) that
the hierarchy of the random neural networks automatically map onto the
hierarchy of auditory processing in the cortex.

###  3.2 Training on Dutch increases the brain-similarity of neural networks

Does training make networks’ representation more brain-like? To tackle this
issue, we follow the same brain-scores analysis with networks trained on a
Dutch speech-to-text task (Figure 2.E and 2.F). Overall, Dutch models better
predict brain responses than random networks (Figure 3.A). Layer-wise
comparison of the brain scores between the random networks and the trained
networks shows that training leads to a significant gain for each layer but
the first one ($p<10^{-6}$ across all subsequent layers, Figure 3.B).

###  3.3 Impact of the phonetic distance between training and processed speech
on brain-similarity

Training with Dutch increases brain-similarity. Is this effect due to the
generation of language-specific representations? To address this issue, we
compare networks trained with either Bengali or English, while matching the
architecture, training procedure and data exposure to the Dutch networks (see
Section 2.4).

Training on English and Bengali induces a significant increase of brain-scores
compared to random networks (Figure 3.C). Training on English does not produce
significantly higher brain scores than training on Dutch ($p=0.22$). This lack
of effect is reassuring, as it confirms that Dutch models do not implicitly
capture lexico-semantic features. On the other hand, the fact that English and
Dutch networks achieve similar brain-scores suggests that the sublexical
representations of speech in the brain are _not_ language specific.

Finally, training on Bengali produces a significantly lower gain in brain
scores than training on either Dutch ($p<0.01$) or English ($p<0.01$). Given
that Dutch and English are closer phonetically than Dutch and Bengali
(Schepens et al., 2020), these results suggests that the brain generates
phoneme-specific representations.

###  3.4 The first levels of the cortical hierarchy are most similar to sound-
generic networks

Does training on a non-speech task also increase brain-similarity?

To tackle this issue, we now focus on the networks trained on a curated
acoustic scene classification task. On average across all voxels (and across
initialization seeds), the brain scores of the acoustic scene networks are not
significantly different from those of the Dutch ($p=0.2$) and English
networks($p=0.2$).

However, the predictions of the brain activity in the first (A1) and secondary
(Belt) auditory cortices (see Figure 3.D) are significantly higher when using
acoustic scene classification networks than when using English (Mean A1:
$p<10^{-9}$, Mean Belt: $p<10^{-6}$) and Dutch networks (Mean A1: $p<10^{-7}$,
Belt: $p<10^{-5}$). On the contrary, for the temporoparietal junction, where
parts of the higher level processing of speech take place (Hickok & Poeppel,
2007), the training on Dutch leads to significantly higher gain in brain score
(Mean TPJ: $p<0.015$) than the acoustic scene classification training.

This result suggests that the brain uses sound-generic representations for the
first processing stage of its hierarchy, and then builds speech-specific
representations in higher-level processing stages.

Figure 3: A. Average (across subjects and random seeds) gains in brain scores
($\Delta R$) between the models trained on Dutch and the random networks
(untrained), using a concatenation of all sound features and activations. Gray
zones are not statistically significant across subjects after FDR correction
for multiple comparison. B. Average (across voxels and random seeds) gains in
brain scores between the trained model and the random model (untrained) for
each layer independently. Error bars indicate SEM across subjects. Stars
indicate significant gains across subjects. C. Average improvement in brain
score ($\Delta R$) obtained by the models trained –from left to right– on
Bengali, acoustic scene classification (ac. sc.), English, and Dutch, compared
to their random initialisation (untrained model). Vertical lines and stars
indicate significant gains across subjects. D. Comparison of the effect of
training on Dutch and acoustic scenes for three regions of interest: the
primary auditory cortex (A1), the secondary auditory cortex (Belt) and the
temporo-parietal junction (TPJ). Position of the three regions on the left
hemisphere of the brain is visible under each graph.

##  4 Discussion

By focusing on speech representations, the present study provides four
empirical contributions to the investigation of auditory representations in
brains and deep learning models (Yamins & DiCarlo, 2016; Keshishian et al.,
2020; Berezutskaya et al., 2020; Khosla et al., 2020; Kell et al., 2018; Kumar
et al., 2020; Koumura et al., 2019).

First, deep convolutional architectures appear to already account for the
hierarchy of brain responses to speech, in that their first and deepest layers
linearly map onto the primary auditory and associative cortices, respectively.
This result suggests that high-level auditory representations can benefit from
an inductive bias imputable to a simple and biologically plausible
architecture. Indeed, unlike visual conv nets, which require neurons with
different visual receptive fields to share weights during training (Yamins &
DiCarlo, 2016), audio conv nets apply their convolution over time and
frequency – a ubiquitous operation in sensory and associative cortices (David
& Shamma, 2013).

Second, training networks with a variety of auditory input appear to
systematically improve brain scores. This result suggests that the brain can,
in principle, use speech non-specific representations to process sounds. This
finding encourages research to test the utility of pretraining speech
recognition systems with non-speech data, in order to extract more (and
potentially better) features.

Third, training with Dutch or on English – i.e., a language phonetically-
related to Dutch – achieved the highest brain scores. This results provides
empirical evidence against the hypothesis that phonetic features are reducible
to generic auditory representations (Galantucci et al., 2006; Daube et al.,
2019). On the contrary, it suggests that learning speech leads the brain to
generate specific phonetic representations.

Finally, training on acoustic scene classification led to higher brain scores
in the primary and secondary auditory cortex than speech models. This finding
supports the idea that the brain builds speech representations ”on top” of
generic representations, and fine-tunes of ”recycles” (Dehaene & Cohen, 2011)
higher-level processing stages.

The brain scores reported throughout the study are low. This limitation can be
accounted for by two main factors. First, we do not report the absolute brain
scores but the difference of brain scores between different layers or
different models (Figure 2.A for an example of full brain score, reaching up
to R=0.42 in the superior temporal lobe). Second, fMRI responses are
notoriously noisy, especially at the single-sample and single-voxel level.
Fortunately, the large number of subjects and stimuli allows these weak
effects to achieve reasonable statistical significance.

To our surprise, we observe significant brain scores in visual regions (e.g.
Figure 3.A). We can speculate that this phenomenon may either relate to i)
feedback projection to visual areas specialized in orthographic
representations (Dehaene & Cohen, 2011) and/or ii) an auditory-dependent
processing of the fixation cross (Petro et al., 2017; Majka et al., 2019).
However, this unexpected result requires temporally-resolved brain recordings
to confirm and clarify the nature of such auditory-induced visual responses.

Overall, our study strengthens the mutual relevance of machine learning models
and neuroscience. While the present investigation remains to be generalized to
more efficient audio processing models (Baevski et al., 2020; Collobert et
al., 2016), it suggests, once again, that some of the computational solutions
designed by machine learning researchers, may actually converge to or re-
discover those implemented in the human brain (Marblestone et al., 2016;
Caucheteux & King, 2020).

## References

  * Abraham et al. (2014a) Abraham, A., Pedregosa, F., Eickenberg, M., Gervais, P., Mueller, A., Kossaifi, J., Gramfort, A., Thirion, B., and Varoquaux, G.  Machine learning for neuroimaging with scikit-learn.  _Frontiers in neuroinformatics_ , 8:14, 2014a.
  * Abraham et al. (2014b) Abraham, A., Pedregosa, F., Eickenberg, M., Gervais, P., Mueller, A., Kossaifi, J., Gramfort, A., Thirion, B., and Varoquaux, G.  Machine learning for neuroimaging with scikit-learn.  _Frontiers in neuroinformatics_ , 8:14, 2014b.
  * Amodei et al. (2016) Amodei, D., Ananthanarayanan, S., Anubhai, R., Bai, J., Battenberg, E., Case, C., Casper, J., Catanzaro, B., Cheng, Q., Chen, G., et al.  Deep speech 2: End-to-end speech recognition in english and mandarin.  In _International conference on machine learning_ , pp. 173–182, 2016.
  * Baevski et al. (2020) Baevski, A., Zhou, H., Mohamed, A., and Auli, M.  wav2vec 2.0: A framework for self-supervised learning of speech representations.  _arXiv preprint arXiv:2006.11477_ , 2020.
  * Baumann et al. (2018) Baumann, T., Köhn, A., and Hennig, F.  The spoken wikipedia corpus collection: Harvesting, alignment and an application to hyperlistening.  _Language Resources and Evaluation_ , Jan 2018.  ISSN 1574-0218.  doi: 10.1007/s10579-017-9410-y.  URL https://doi.org/10.1007/s10579-017-9410-y.
  * Behzadi et al. (2007) Behzadi, Y., Restom, K., Liau, J., and Liu, T. T.  A component based noise correction method (compcor) for bold and perfusion based fmri.  _Neuroimage_ , 37(1):90–101, 2007.
  * Benjamini (2010) Benjamini, Y.  Discovering the false discovery rate.  _Journal of the Royal Statistical Society: series B (statistical methodology)_ , 72(4):405–416, 2010.
  * Berezutskaya et al. (2020) Berezutskaya, J., Freudenburg, Z. V., Güçlü, U., van Gerven, M. A., and Ramsey, N. F.  Brain-optimized extraction of complex sound features that drive continuous auditory perception.  _PLoS computational biology_ , 16(7):e1007992, 2020.
  * Caucheteux & King (2020) Caucheteux, C. and King, J.-R.  Language processing in brains and deep neural networks: computational convergence and its limits.  _BioRxiv_ , 2020.
  * Collobert et al. (2016) Collobert, R., Puhrsch, C., and Synnaeve, G.  Wav2letter: an end-to-end convnet-based speech recognition system.  _arXiv preprint arXiv:1609.03193_ , 2016.
  * Daube et al. (2019) Daube, C., Ince, R. A., and Gross, J.  Simple acoustic features can explain phoneme-based predictions of cortical responses to speech.  _Current Biology_ , 29(12):1924–1937, 2019.
  * David & Shamma (2013) David, S. V. and Shamma, S. A.  Integration over multiple timescales in primary auditory cortex.  _Journal of Neuroscience_ , 33(49):19154–19166, 2013.
  * Dehaene & Cohen (2011) Dehaene, S. and Cohen, L.  The unique role of the visual word form area in reading.  _Trends in cognitive sciences_ , 15(6):254–262, 2011.
  * Destrieux et al. (2010) Destrieux, C., Fischl, B., Dale, A., and Halgren, E.  Automatic parcellation of human cortical gyri and sulci using standard anatomical nomenclature.  _Neuroimage_ , 53(1):1–15, 2010.
  * Esteban et al. (2019) Esteban, O., Markiewicz, C. J., Blair, R. W., Moodie, C. A., Isik, A. I., Erramuzpe, A., Kent, J. D., Goncalves, M., DuPre, E., Snyder, M., et al.  fmriprep: a robust preprocessing pipeline for functional mri.  _Nature methods_ , 16(1):111–116, 2019.
  * Fischl (2012) Fischl, B.  Freesurfer.  _Neuroimage_ , 62(2):774–781, 2012.
  * Fonseca et al. (2017) Fonseca, E., Pons Puig, J., Favory, X., Font Corbera, F., Bogdanov, D., Ferraro, A., Oramas, S., Porter, A., and Serra, X.  Freesound datasets: a platform for the creation of open audio datasets.  In _Hu X, Cunningham SJ, Turnbull D, Duan Z, editors. Proceedings of the 18th ISMIR Conference; 2017 oct 23-27; Suzhou, China.[Canada]: International Society for Music Information Retrieval; 2017. p. 486-93._ International Society for Music Information Retrieval (ISMIR), 2017\.
  * Fonseca et al. (2019) Fonseca, E., Plakal, M., Font, F., Ellis, D. P., and Serra, X.  Audio tagging with noisy labels and minimal supervision.  _arXiv preprint arXiv:1906.02975_ , 2019.
  * Galantucci et al. (2006) Galantucci, B., Fowler, C. A., and Turvey, M. T.  The motor theory of speech perception reviewed.  _Psychonomic bulletin & review_, 13(3):361–377, 2006.
  * Graves et al. (2006) Graves, A., Fernández, S., Gomez, F., and Schmidhuber, J.  Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks.  In _Proceedings of the 23rd international conference on Machine learning_ , pp. 369–376, 2006.
  * Hermjakob et al. (2018) Hermjakob, U., May, J., and Knight, K.  Out-of-the-box universal Romanization tool uroman.  In _Proceedings of ACL 2018, System Demonstrations_ , pp. 13–18, Melbourne, Australia, July 2018. Association for Computational Linguistics.  doi: 10.18653/v1/P18-4003.  URL https://www.aclweb.org/anthology/P18-4003.
  * Hickok & Poeppel (2007) Hickok, G. and Poeppel, D.  The cortical organization of speech processing.  _Nature reviews neuroscience_ , 8(5):393–402, 2007.
  * Hung et al. (2005) Hung, C. P., Kreiman, G., Poggio, T., and DiCarlo, J. J.  Fast readout of object identity from macaque inferior temporal cortex.  _Science_ , 310(5749):863–866, 2005.
  * Kamitani & Tong (2005) Kamitani, Y. and Tong, F.  Decoding the visual and subjective contents of the human brain.  _Nature neuroscience_ , 8(5):679–685, 2005.
  * Kell et al. (2018) Kell, A. J., Yamins, D. L., Shook, E. N., Norman-Haignere, S. V., and McDermott, J. H.  A task-optimized neural network replicates human auditory behavior, predicts brain responses, and reveals a cortical processing hierarchy.  _Neuron_ , 98(3):630–644, 2018.
  * Keshishian et al. (2020) Keshishian, M., Akbari, H., Khalighinejad, B., Herrero, J. L., Mehta, A. D., and Mesgarani, N.  Estimating and interpreting nonlinear receptive field of sensory neural responses with deep neural network models.  _Elife_ , 9:e53445, 2020.
  * Khosla et al. (2020) Khosla, M., Ngo, G. H., Jamison, K., Kuceyeski, A., and Sabuncu, M. R.  Cortical response to naturalistic stimuli is largely predictable with deep neural networks.  _bioRxiv_ , 2020.
  * King et al. (2018) King, J.-R., Gwilliams, L., Holdgraf, C., Sassenhagen, J., Barachant, A., Engemann, D., Larson, E., and Gramfort, A.  Encoding and decoding neuronal dynamics: Methodological framework to uncover the algorithms of cognition.  2018\.
  * Kjartansson et al. (2018) Kjartansson, O., Sarin, S., Pipatsrisawat, K., Jansche, M., and Ha, L.  Crowd-Sourced Speech Corpora for Javanese, Sundanese, Sinhala, Nepali, and Bangladeshi Bengali.  In _Proc. The 6th Intl. Workshop on Spoken Language Technologies for Under-Resourced Languages (SLTU)_ , pp. 52–55, Gurugram, India, August 2018\.  URL http://dx.doi.org/10.21437/SLTU.2018-11.
  * Koumura et al. (2019) Koumura, T., Terashima, H., and Furukawa, S.  Cascaded tuning to amplitude modulation for natural sound recognition.  _Journal of Neuroscience_ , 39(28):5517–5533, 2019.
  * Kriegeskorte & Kievit (2013) Kriegeskorte, N. and Kievit, R. A.  Representational geometry: integrating cognition, computation, and the brain.  _Trends in cognitive sciences_ , 17(8):401–412, 2013.
  * Kuchaiev et al. (2018) Kuchaiev, O., Ginsburg, B., Gitman, I., Lavrukhin, V., Li, J., Nguyen, H., Case, C., and Micikevicius, P.  Mixed-precision training for nlp and speech recognition with openseq2seq, 2018.
  * Kumar et al. (2020) Kumar, S., Ellis, C., O’Connell, T. P., Chun, M. M., and Turk-Browne, N. B.  Searching through functional space reveals distributed visual, auditory, and semantic coding in the human brain.  _bioRxiv_ , 2020.
  * Majka et al. (2019) Majka, P., Rosa, M. G., Bai, S., Chan, J. M., Huo, B.-X., Jermakow, N., Lin, M. K., Takahashi, Y. S., Wolkowicz, I. H., Worthy, K. H., et al.  Unidirectional monosynaptic connections from auditory areas to the primary visual cortex in the marmoset monkey.  _Brain Structure and Function_ , 224(1):111–131, 2019.
  * Marblestone et al. (2016) Marblestone, A. H., Wayne, G., and Kording, K. P.  Toward an integration of deep learning and neuroscience.  _Frontiers in computational neuroscience_ , 10:94, 2016\.
  * McFee et al. (2019) McFee, B., McVicar, M., Balke, S., Lostanlen, V., Thomé, C., Raffel, C., Lee, D., Kyungyun Lee, Nieto, O., Zalkow, F., Ellis, D., Battenberg, E., Yamamoto, R., Moore, J., Ziyao Wei, Bittner, R., Keunwoo Choi, Nullmightybofo, Friesch, P., Fabian-Robert Stöter, , Thassilo, Vollrath, M., Siddhartha Kumar Golu, Nehz, Waloschek, S., , Seth, Naktinis, R., Repetto, D., Hawthorne, C., and CJ Carr.  librosa/librosa: 0.6.3, 2019.  URL https://zenodo.org/record/2564164.
  * Mesgarani et al. (2014) Mesgarani, N., Cheung, C., Johnson, K., and Chang, E. F.  Phonetic feature encoding in human superior temporal gyrus.  _Science_ , 343(6174):1006–1010, 2014.
  * Pedregosa et al. (2011) Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al.  Scikit-learn: Machine learning in python.  _the Journal of machine Learning research_ , 12:2825–2830, 2011.
  * Petro et al. (2017) Petro, L., Paton, A., and Muckli, L.  Contextual modulation of primary visual cortex by auditory signals.  _Philosophical Transactions of the Royal Society B: Biological Sciences_ , 372(1714):20160104, 2017.
  * Schepens et al. (2020) Schepens, J., van Hout, R., and Jaeger, T. F.  Big data suggest strong constraints of linguistic similarity on adult language learning.  _Cognition_ , 194:104056, 2020.
  * Schoffelen et al. (2019) Schoffelen, J.-M., Oostenveld, R., Lam, N. H., Uddén, J., Hultén, A., and Hagoort, P.  A 204-subject multimodal neuroimaging dataset to study language processing.  _Scientific data_ , 6(1):1–13, 2019.
  * Stevens & Volkmann (1940) Stevens, S. S. and Volkmann, J.  The relation of pitch to frequency: A revised scale.  _The American Journal of Psychology_ , 53(3):329–353, 1940.
  * Stevens et al. (1937) Stevens, S. S., Volkmann, J., and Newman, E. B.  A scale for the measurement of the psychological magnitude pitch.  _The journal of the acoustical society of america_ , 8(3):185–190, 1937.
  * Unni et al. (2020) Unni, V., Joshi, N., and Jyothi, P.  Coupled training of sequence-to-sequence models for accented speech recognition.  In _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 8254–8258. IEEE, 2020.
  * Van Essen (2005) Van Essen, D. C.  A population-average, landmark-and surface-based (pals) atlas of human cerebral cortex.  _Neuroimage_ , 28(3):635–662, 2005.
  * Yamins & DiCarlo (2016) Yamins, D. L. and DiCarlo, J. J.  Using goal-driven deep learning models to understand sensory cortex.  _Nature neuroscience_ , 19(3):356–365, 2016.
  * Yamins et al. (2014) Yamins, D. L., Hong, H., Cadieu, C. F., Solomon, E. A., Seibert, D., and DiCarlo, J. J.  Performance-optimized hierarchical models predict neural responses in higher visual cortex.  _Proceedings of the National Academy of Sciences_ , 111(23):8619–8624, 2014.
  * Zhang et al. (2020) Zhang, S., Do, C.-T., Doddipatla, R., and Renals, S.  Learning noise invariant features through transfer learning for robust end-to-end speech recognition.  In _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 7024–7028. IEEE, 2020.


Quantum Pseudorandomness Cannot Be Shrunk
In a Black-Box Way

Samuel Bouaziz--Ermann1 Garazi Muguruza2,3
Sorbonne Université, CNRS, LIP6, France Informatics Institute, University of Amsterdam, Netherlands QuSoft, Netherlands
S. Bouaziz--Ermann G. Muguruza

Pseudorandom Quantum States (PRS) were introduced by Ji, Liu and Song as quantum analogous to Pseudorandom Generators.
They are an ensemble of states efficiently computable but computationally indistinguishable from Haar random states.
Subsequent works have shown that some cryptographic primitives can be constructed from PRSs.
Moreover, recent classical and quantum oracle separations of PRS from One-Way Functions strengthen the interest in a purely quantum alternative building block for quantum cryptography, potentially weaker than OWFs.

However, our lack of knowledge of extending or shrinking the number of qubits of the PRS output still makes it difficult to reproduce some of the classical proof techniques and results.
Short-PRSs, that is PRSs with logarithmic size output, have been introduced in the literature along with cryptographic applications, but we still do not know how they relate to PRSs.
Here we answer half of the question, by showing that it is not possible to shrink the output of a PRS from polynomial to logarithmic qubit length while still preserving the pseudorandomness property, in a relativized way.
More precisely, we show that relative to Kretschmer's quantum oracle (TQC 2021) short-PRSs cannot exist (while PRSs exist, as shown by Kretschmer's work).

§ INTRODUCTION

Pseudorandomness is an important concept in cryptography since almost all relevant classical cryptographic primitives require the existence of one-way functions (OWF) or equivalent objects such as pseudorandom generators (PRG) and pseudorandom functions (PRF) <cit.>.
It corresponds to a deterministic function whose output cannot be distinguished from the uniform distribution by a computationally bounded algorithm.

In 2018, Ji, Liu and Song <cit.> introduced a quantum analog of PRGs, called Pseudorandom Quantum States (PRS) that consists of a family of polynomial size keyed-states $\{\ket{\phi_k}\}_{k\in\mathcal{K}}$ such that no quantum polynomial-time algorithm can distinguish between a polynomial number of copies[The reason we give the adversary a polynomial number of copies of the state is that an arbitrary quantum state cannot be cloned, by the no-cloning theorem.] of a randomly sampled element from the PRSs family or a polynomial number of copies of a Haar-random state (see <Ref> for a formal definition).
We already know how to construct several cryptographic primitives from (variants of) PRSs: public key encryption with quantum keys <cit.>, quantum digital signatures <cit.>, pseudo one-time pad encryption schemes <cit.>, statistically binding and computationally hiding commitments <cit.> and quantum computational zero knowledge proofs <cit.>.
Such rapid interest derives probably from the fact that PRSs can be constructed from OWFs <cit.> (and thus PRGs), but there are oracle separations found between OWFs and PRSs <cit.>, which makes them a potentially weaker building block for quantum cryptography, with a purely quantum description.

Classically, practical applications of PRGs require stretching the output, which can be done arbitrarily by just using the output of the PRG as an input and roughly composing the PRG with itself. However, no analogous intuitive construction is possible with PRSs because the input is a classical bit string and the output is a quantum state.
Moreover, although classically shrinking a PRG does not make sense, it is still possible by discarding part of the output of the original PRG.
Quantumly, discarding half of a quantum state could lead to a maximally mixed state, making it easy to distinguish from a Haar-random state, which means that pseudorandomness is not a property respected by subsets of the registers.

This motivates the definition of short-PRS, a PRS that on input $k\in\{0,1\}^\lambda$ outputs a qubit of size $n(\lambda)=O(\log\lambda)$.
Brakerski and Shmueli <cit.> proved that $c\cdot\log\lambda$-output PRSs exist for any $c\geq1$.
While classically, “short-PRGs” and PRGs are equivalent, in the quantum setting, the following question remains open

[]Question 1: What is the relation between short and long PRSs?

In this work we answer half of the question, by showing that there exists a quantum oracle relative to which PRSs exist but short-PRSs do not, thus PRSs are a weaker assumption than short-PRSs.
Note that this question appeared in the literature <cit.>.

Our separation relies on another fundamental difference between quantum and classical cryptography; while pseudorandomness has received much attention in classical cryptography, the same cannot be said about pseudodeterminism.
A pseudodeterministic variant of PRGs (PD-PRG) was first introduced by Ananth, Lin and Yuen <cit.>, defined as a quantum polynomial-time algorithm that outputs a pseudorandom string on a fraction of the input keys.
In their work, this fraction is polynomial in size and this define polynomial pseudodeterminism, and we define overwhelming pseudodeterminsm when this fraction is overwhelming in size.
They showed that short-PRSs can be used to construct PD-PRGs.
Later Barhoush, Behera, Ozer, Salvail and Sattath <cit.> introduced the analogous pseudodeterministic one-way functions (PD-OWF) and showed that PD-PRGs imply PD-OWFs.

Relation between different primitives. Proven, expected and our result.

Although a quantum state can encode arbitrary classical information, this information is not necessarily accessible for an observer. For example, while OWFs are separated from PRSs, PD-OWFs can be built from short-PRSs <cit.>.
Another interesting question is thus

[]Question 2: What is the role of pseudodeterminism in quantum cryptography?

Pseudodeterministic variants of OWFs and PRGs seem to be enough to build many interesting tasks in cryptography.
For example, <cit.> state that overwhelming PD-PRGs are enough to build PRSs, as these can be used to generate pseudorandom phases pseudodeterministically, and they build polynomial PD-PRGs from short-PRSs. However, it is unclear how to build overwhelming PD-PRGs from short-PRSs, or if polynomial PD-PRGs are enough to build PRSs[The same construction from PRGs does not work as the polynomial error will induce too much error in the resulting state to be a PRS.].
In other words, there seems to be a gap between the cryptography we can build from polynomial or overwhelming pseudodeterminism, with short-PRSs being nearly as strong as overwhelming pseudodeterminism while PRSs are weaker than polynomial pseudodeterminism, as we show in this work.
What is clear is that pseudodeterminism is a non-trivial property in quantum cryptography.

Our contribution.

We show that Kretschmer's oracle <cit.> not only implies that OWFs do not exist, but also none of the pseudoterministic variants do either.
Since PD-PRGs and PD-OWFs can be constructed from short-PRSs <cit.>, our work gives a separation between PRSs and short-PRSs[Note that relative to Kretschmer's oracle, not only do we have PRSs, but we also have pseudorandom unitaries (PRU).] and can be stated as follows.

There exists a quantum oracle \(\mathcal{O}\) relative to which PRSs exist but short-PRSs do not.

This result might sound counterintuitive, as it shows that we cannot shrink a pseudorandom quantum state to a smaller one.
An explanation of this result could be that requiring a polynomial number of copies of a logarithmic quantum state to be indistinguishable from a polynomial number of copies of a random state is a strong assumption, that is similar to OWFs, as shown by previous works.

Relative to Kretschmer's oracle we know that poly-size PRSs exist and $\promiseBQP=\promiseQMA$.
Here we show that not only the existence of OWFs, but also the existence of polynomial error pseudodeterministic OWFs (a possibly weaker assumption, but implied by short-PRSs) also implies $\promiseBQP\not=\promiseQMA$.
For the proof to work, we rely on the promise version of the complexity classes.
Promises problems are such that there are yes instances and no instances, but also other instances where the output of an algorithm does not matter.
In our proof, we define a language with the yes instances as the values for which there exists a high probability pre-image, and the no instances are values for which there is no low probability pre-image.

Thus there is a gap between the possible success probabilities, and this gap is needed to distinguish between the yes and no instances in polynomial time.

Open questions.
We still leave open the question in the opposite direction, of building PRSs from short-PRSs.
There are two partial results regarding this in the literature; the first is that it is possible to construct PRSs with a bigger dimension, but at the cost of the security definition to hold only for single-copy PRSs <cit.>, the second gives a positive answer by assuming the existence of pseudorandom isometries <cit.>.
However, the general question, without assumptions, still remains open.

Note that our separation is relative to a quantum oracle, thus a classical oracle separation of short-PRSs from PRSs is unclear.
The classical oracle from <cit.> gives P=NP, but this is not enough for PD-OWFs, as we need promise problems in our proof.

As mentioned above, pseudodeterminism is a non-trivial feature of quantum cryptography. It is unclear where PRSs and short-PRSs lie in the graph of <Ref>: are short-PRSs equivalent to $\negl$ error pseudodeterminism? Which cryptographic tasks require negligible error pseudodeterminism and which ones inverse polynomial? Moreover, although intuitively the answer should be yes, it is still unclear if all the pseudodeterministic variants of PRGs/PRFs/OWFs are equivalent to each other.
Constructing PD-OWFs from PD-PRGs is possible by the generalization lemma of <cit.>, but proving the other direction is still open.

Finally, our results imply that the quantum oracle separation from <cit.> is not enough to separate short-PRSs from OWFs, thus it is natural to ask if this is possible.
Indeed quantum oracles for “short” PRUs will not lead to $\promiseBQP=\promiseQMA$, because the concentration inequality on the Haar measure does not hold with small dimensions for the unitaries.

As for classical oracles, there is a classical oracle separation between 1-copy short-PRSs and OWFs <cit.>, but a multi-copy separation is still unknown (both for short-PRSs and PRSs).

§ PRELIMINARIES

We use $\lambda$ to denote the security parameter.
We use $\negl[\cdot]$ to denote a negligible function.
We use \(\epsilon\) to denote the empty string.
We use \(||\) to denote the concatenation operator.
We use \(x\prec y\) to denote the fact that \(x\) is a prefix of \(y\), i.e. there exists \(x'\) such that \(y = x || x'\).
We use \(x\nprec y\) to denote the fact that \(x\) is not a prefix of \(y\).
We use $\leftarrow\mathcal{A}$ to denote uniform sampling from the set $\mathcal{A}$.

We use $\mathcal{H}_n$ to denote the Haar measure over $n$-qubit space, i.e. $\mathcal{H}((\mathbb{C})^{\otimes n})$. The Haar measure over $\mathbb{C}^d$ is the uniform measure over all $d$-dimensional unit vectors over $\mathbb{C}$.

We include here the relevant pseudorandom notions.

Let $\lambda \in \mathbb{N}$, and let $n(\lambda)$ be the number of qubits in the quantum system.
A keyed family of $n$-qubit quantum states $\{\ket{\phi_k}\}_{k \in \{0,1\}^\lambda}$ is pseudorandom if the following two conditions hold:

* Efficient generation. There is a QPT algorithm $G$ that on input $k\in\{0,1\}^\lambda$ generates

\begin{align*}
\end{align*}

* Pseudorandomness. For any QPT adversary $\adv$ and all polynomials $t(\cdot)$, we have

\begin{align*}\left| \pr[k \leftarrow \{0,1\}^\lambda]{\adv\left(1^\lambda, \ket{\varphi_k}^{\otimes t(\lambda)}\right) = 1 } - \pr[\ket{\nu} \leftarrow \mathcal{H}_n(\lambda)]{\adv\left(1^\lambda, \ket{\nu}^{\otimes t(\lambda)}\right) = 1 } \right| \leq \negl[\lambda].\end{align*}

We say that a $n(\lambda)$-PRS is a short-PRS if the output is logarithmic in the security parameter, i.e. $n(\lambda)=\Theta(\log\lambda)$. From now on we will use PRSs to refer to long-output PRSs and short-PRSs for logarithmic output.

We also include a pseudodeterministic primitive.

A QPT algorithm $F :\{0,1\}^{m(\lambda)}\rightarrow \{0,1\}^{\ell(\lambda)}$ is a quantum pseudo-deterministic one-way function if the following conditions hold:

* Pseudodeterminism. There exists a constant $c>0$ and function $\mu(\lambda)=O(\lambda^{-c})$ such that for all $\lambda\in \mathbb{N}$, there exists a set $\mathcal{K}_\lambda \subset \{0,1\}^{m(\lambda)}$:

* $\pr{x\in\mathcal{K}_\lambda \given{x\leftarrow \{0,1\}^{\ell(\lambda)}}}\geq 1-\mu(\lambda)$.

* For any $x\in \mathcal{K}_\lambda$, it holds that

\begin{align}
\label{eq:pd}\max_{y\in \{0,1\}^{\ell(\lambda)}}\pr{y=F_\lambda(x)}\geq 1-\negl[\lambda],
\end{align}

where the probability is over the randomness of $F_\lambda$.

* Security. For every QPT inverter $\adv$:

\begin{align}
\label{eq:sec} \pr[x\leftarrow \{0,1\}^{m(\lambda)}]{F\left(\adv(F(x))\right)=F(x)}\leq \negl[\lambda],
\end{align}

where the probability is over the randomness of $F$ and $\adv$.

Note that the pseudodeterminism factor in the above definition comes from the size of the good key space $\mu(\lambda)$, which is an inverse-polynomial in the security parameter $\lambda$. This means that for a non-negligible number of elements in the key space, the OWF could behave arbitrarily.
We could also define a negligible variant by requesting $\mu(\lambda)$ to be a negligible function in $\lambda$.

We can build PD-OWFs from short-PRSs.

Assuming the existence of $(c\log \lambda)$-PRSs with $c>12$, there exists a $O(\lambda^{-c/12+1})$-PD-OWF $F:\{0,1\}^{\ell(\lambda)}\rightarrow \{0,1\}^{\ell(\lambda)}$ with input/output length $\ell(\lambda)=\lambda^{c/6}$.

Finally, we will need Kretschmer's (quantum) oracle $\mathcal{O}$ relative to which OWFs do not exist, but PRSs do.
The former is because $\promiseBQP$ and $\promiseQMA$ are equal relative to this oracle
, we only include here the definitions of these languages for the sake of self-containment, but we refer the reader to the original paper for a lengthier explanation of the complexity classes.

A promise problem $\lang=\lang_{\mathrm{yes}}\cup\lang_{\mathrm{no}}\cup\lang_{\bot}$ with $\lang\subseteq \{0,1\}^*$ is in $\mathsf{PromiseQMA}$ (Quantum Merlin–Arthur) if there exists a polynomial-time quantum algorithm $\mathsf{V}(x,\ket{\psi})$ called a verifier and a polynomial $p$ such that:

* (Completeness) If $x\in\lang_{\mathrm{yes}}$, then there exists a quantum state $\ket{\psi}$ on $p(|x|)$ qubits (called a witness or proof) such that $\Pr\left[\mathsf{V}(x,\ket{\psi}) = 1\right] \geq \frac{2}{3}$.

* (Soundness) If $x\in\lang_{\mathrm{no}}$, then for every quantum state $\ket{\psi}$ on $p(|x|)$ qubits, $\Pr\left[\mathsf{V}(x,\ket{\psi}) = 1\right] \leq \frac{1}{3}$.

A promise problem $\lang=\lang_{\mathrm{yes}}\cup\lang_{\mathrm{no}}\cup\lang_{\bot}$ with $\lang\subseteq \{0,1\}^*$ is in $\mathsf{PromiseBQP}$ (Bounded-error Quantum Polynomial time) if there exists a randomized polynomial-time quantum algorithm $\adv(x)$ such that:

* If $x\in\lang_{\mathrm{yes}}$, then $\Pr\left[\adv(x) = 1\right] \geq \frac{2}{3}$.

* If $x\in\lang_{\mathrm{no}}$, then $\Pr\left[\adv(x) = 1\right] \leq \frac{1}{3}$.

There exists a quantum oracle \(\mathcal{O}\), such that:

* $\promiseBQP^{\mathcal{O}} = \promiseQMA^{\mathcal{O}}$.

* $\lambda$-PRSs exist relative to $\mathcal{O}$.[The random oracle is a random unitary operation, which gives the existence of PRUs and thus PRSs <cit.>.]

§ SEPARATING PRSS FROM SHORT-PRSS

In this section, we prove our main theorem, that we can separate poly-size PRSs and log-size PRSs.
Formally, we will be proving the following theorem.

There exists a quantum oracle \(\mathcal{O}\) such that relative to \(\mathcal{O}\), \(\lambda\)-PRSs exist, but
$(c\log \lambda)$-PRSs with $c>12$ do not exist.

The oracle necessary for the separation is actually the same oracle that Kretschmer used to separate PRSs and OWFs (<Ref>).
It turns out that this oracle is also separating PD-OWFs from PRSs, we prove here that if $\promiseBQP=\promiseQMA$, then we do not have PD-OWFs. This in addition with Barhoush and Salvail's result that short-PRSs are enough to build PD-OWFs (<Ref>) will give us the theorem.

According to the above considerations, the main theorem follows directly from the following proposition.

If PD-OWFs exist, then $\promiseBQP\neq\promiseQMA$.

Let $\lambda\in\mathbb{N}$ and $F:\dom\to\{0,1\}^{\ell(\lambda)}$ be a PD-OWF. Let us define a promise language $\lang = \lang_\textrm{yes}\cup\lang_\textrm{no}\cup\lang_\bot$ with $\lang\subseteq\{0,1\}^*$ where yes instances have a pre-image with respect to $F_\lambda$ but no instances do not. Formally,

\begin{multline}
\lang_\textrm{yes} = \left\{(1^{\ell(\lambda)},x',y)\in \{1^{\ell(\lambda)}\}\times\dom\times\{0,1\}^{\ell(\lambda)} \middle\rvert\right. \\ \left.\exists x\in \dom, x' \prec x \text{ and } \Pr[y=F_{\lambda}(x)]\geq 1-\negl[\lambda] \right\}, \label{eq:langyes}
\end{multline}

\begin{multline}
\lang_\textrm{no} = \left\{(1^{\ell(\lambda)},x',y)\in \{1^{\ell(\lambda)}\}\times\dom\times\{0,1\}^{\ell(\lambda)} \middle\rvert \right.\\ \left.\forall x\in \dom, x' \nprec x \text{ or } \Pr[y=F_{\lambda}(x)]\leq 1-\frac{1}{\lambda} \right\}. \label{eq:langno}
\end{multline}

We claim that $\lang\in\promiseQMA$ but $\lang\not\in\promiseBQP$, thus there must be a separation between both complexity classes.
These claims are proven in <Ref> and <Ref> respectively.

We now prove the two claims from the proposition. We start by showing that the language defined in <ref> is in $\promiseQMA$, this is, we will construct an algorithm (verifier) that given an element of the domain and a (quantum) proof can distinguish if the element is a yes or no instance of the language.

Let \(F\) be a PD-OWF and let $\lang$ be the language defined in <Ref>, then $\lang \in \promiseQMA$.

We define a quantum polynomial-time algorithm \(\adv\) that given an element of the domain (\(1^{\ell(\lambda)},x',y) \in \{1^{\ell(\lambda)}\}\times\dom\times\{0,1\}^{\ell(\lambda)}\) and a classical proof
$x\in \{0,1\}^{\ell(\lambda)}$, will check if the proof $x$ is indeed a pre-image of the PD-OWF by checking if it coincides with the input $y$.
[linenumbering, head=Algorithm 1: $\adv((1^{\ell(\lambda)},x',y),x)$]
x' ⊀x:

1 ≤i ≤2λ:

F_λ(x) ≠y:

Note that the algorithm runs in polynomial-time trivially because computing $F_\lambda$ is done efficiently by definition and we make $2\lambda$ calls to it. We now prove that the algorithm distinguishes between the yes/no instances.

(i) Let \((1^{\ell(\lambda)},x',y) \in \lang_\textrm{yes}\).
Then by definition there exists a proof $x\in \dom$ such that

\begin{align*}
x' \prec x \text{ and } \Pr[y=F_\lambda(x)]\geq 1-\negl[\lambda].
\end{align*}

Then the proof $x$ will be an element of the input $((1^{\ell(\lambda)},x',y),x)$ for which the algorithm $\adv$ will output $1$ with high probability because

\begin{align*}
\pr{\adv((1^{\ell(\lambda)},x',y),x)=1} &= \pr{\forall 1 \leq i \leq 2\lambda, \text{ the execution of } F_{\lambda}(x) \text{ outputs y}} \\
&\geq \left(1-\negl[\lambda]\right)^{2\lambda}
\geq 2/3,
\end{align*}

which holds whenever $\lambda\geq6$. Indeed, recall that $\negl[\lambda]\leq1/\lambda^c$ for all $c>1$, thus in particular $\negl[\lambda]\leq1/\lambda^2$, hence

\begin{align*}
\end{align*}

whenever $\lambda\geq 6$, where we used that we have an increasing function in $\lambda$.

(ii) Let \((1^{\ell(\lambda)},x',y) \in \lang_\textrm{no}\). Then by definition for every potential proof $x\in\dom$ we have that either

\begin{align*}
x'\nprec x \quad\text{or}\quad\Pr[y=F_\lambda(x)]\leq 1-\frac{1}{\lambda}.
\end{align*}

Then for every possible input $((1^{\ell(\lambda)},x',y),x)$ the algorithm will output $0$ with high probability because

\begin{align*}
\pr{\adv((1^{\ell(\lambda)},x',y),x)=1} &= \pr{x'\nprec x\wedge\forall 1 \leq i \leq 2\lambda, \text{ the execution of } F_{\lambda}(x) \text{ outputs y}} \\
&\leq \pr{\forall 1 \leq i \leq 2\lambda, \text{ the execution of } F_{\lambda}(x) \text{ outputs y}}\\
&\leq \left(1-\frac{1}{\lambda}\right)^{2\lambda}
\leq e^{-2}
\leq 1/3.
\end{align*}

Let \(F\) be a PD-OWF and let $\lang$ be the language defined in <Ref>, then $\lang \notin \promiseBQP$.

We will prove this by contradiction. Let us assume that instead \(\lang \in \promiseBQP\), this is, there exists a BQP algorithm \(\adv\) such that:

* If \((1^{\ell(\lambda)},x',y) \in \lang_{\mathrm{yes}}\), then \(\pr{\adv(1^{\ell(\lambda)},x',y)=1} \geq 2/3\).

* If \((1^{\ell(\lambda)},x',y) \in \lang_\mathrm{no}\), then \(\pr{\adv(1^{\ell(\lambda)},x',y)=1} \leq 1/3\).

Without loss of generality, we can assume that the algorithm \(\adv\) has completeness \(1-\frac{1}{\ell(\lambda)}\) and soundness \(\frac{1}{\ell(\lambda)}\).

We will now show how we can construct a QPT algorithm \(\adv'\) that finds a pre-image of every \(F_\lambda\) with high probability when it exists, by querying the original BQP algorithm \(\adv\) at most \(\ell(\lambda)+1\) times.

[linenumbering, head=Algorithm 2: $\adv'(1^{\ell(\lambda)},y)$]
b ←(1^ℓ(λ),ϵ,y)

x_0 ←ϵ

1 ≤i ≤ℓ(λ):

b ←(1^ℓ(λ),x_0 || 0,y)

x_0 = x_0 || 0

x_0 = x_0 || 1

Indeed if $(1^{\ell(\lambda)},\epsilon,y)\in\lang_\mathrm{yes}$, then the probability that the algorithm $\adv '$ outputs a correct pre-image is very high

\begin{equation}
\label{eq:algo}
\pr{y = \argmax_{y\in\{0,1\}^{\ell(\lambda)}}\pr{y=F_\lambda(x)}\given{x\leftarrow \adv'\left(1^{\ell(\lambda)},y\right)}}\geq \left(1-\frac{1}{\ell(\lambda)}\right)^{\ell(\lambda)+1}.
\end{equation}

However, this raises a contradiction with the security of the PD-OWF from the assumption <Ref>,

\begin{align*}
&\pr[x\leftarrow \{0,1\}^{\ell(\lambda)}]{F_{\lambda}(\adv'(1^{\ell(\lambda)}, F_{\lambda}(x)))=F_{\lambda}(x)}\\
&\hspace{2cm}= \pr[x\leftarrow \{0,1\}^{\ell(\lambda)}]{F_{\lambda}(\adv'(1^{\ell(\lambda)}, F_{\lambda}(x)))=F_{\lambda}(x) \given{x \in \mathcal{K}_{\lambda}}} \pr[x\leftarrow \{0,1\}^{\ell(\lambda)}]{x \in \mathcal{K}_{\lambda}} \\
&\hspace{3cm}  + \pr[x\leftarrow \{0,1\}^{\ell(\lambda)}]{F_{\lambda}(\adv'(1^{\ell(\lambda)}, F_{\lambda}(x)))=F_{\lambda}(x) \given{x \notin \mathcal{K}_{\lambda}}} \pr[x\leftarrow \{0,1\}^{\ell(\lambda)}]{x \notin \mathcal{K}_{\lambda}} \\
&\hspace{2cm}\geq \pr[x\leftarrow \{0,1\}^{\ell(\lambda)}]{F_{\lambda}(\adv'(1^{\ell(\lambda)}, F_{\lambda}(x)))=F_{\lambda}(x) \given{x \in \mathcal{K}_{\lambda}}} \pr[x\leftarrow \{0,1\}^{\ell(\lambda)}]{x \in \mathcal{K}_{\lambda}} \\
&\hspace{2cm}\geq \pr[x\leftarrow \{0,1\}^{\ell(\lambda)}]{F_{\lambda}(\adv'(1^{\ell(\lambda)}, F_{\lambda}(x)))=F_{\lambda}(x) \given{x \in \mathcal{K}_{\lambda}}} \left(1 - \mu(\lambda)\right), \\
\end{align*}

where the first equality comes from the law of total probability and the second inequality comes from the property of \(\mathcal{K}_{\lambda}\).
We can rewrite the last element as:

\begin{align*}
&\pr[x\leftarrow \{0,1\}^{\ell(\lambda)}]{y_3=y_1 \given{ y_1,y_2,y_3 \leftarrow F_{\lambda}(x), x_1 \leftarrow \adv'(1^{\ell(\lambda)}, y_2), x\in\mathcal{K}_{\lambda}}} \\
&\hspace{1cm}\geq \pr[x\leftarrow \{0,1\}^{\ell(\lambda)}]{\left(y_3=y_2=y_1=\argmax_{y\in \{0,1\}^{\ell(\lambda)}}{\Pr[y=F_\lambda(x)]}\right) \land (x_1=x) \given{
\begin{array}{c}
y_1,y_2,y_3 \leftarrow F_{\lambda}(x)\\ x_1 \leftarrow \adv'(1^{\ell(\lambda)},y_2), x\in\mathcal{K}_{\lambda}
\end{array}
&\hspace{1cm}= \pr[x\leftarrow \{0,1\}^{\ell(\lambda)}]{F_{\lambda}(x)=\argmax_{y\in \{0,1\}^{\ell(\lambda)}}{\Pr[y=F_\lambda(x)]} \given{x \in \mathcal{K}_{\lambda}}}^3\\
&\hspace{2cm}\cdot\pr[x\leftarrow \{0,1\}^{\ell(\lambda)}]{\adv'\left(1^{\ell(\lambda)},\argmax_{y\in \{0,1\}^{\ell(\lambda)}}{\Pr[y=F_\lambda(x)]}\right)=x \given{x \in \mathcal{K}_{\lambda}}}\\
&\hspace{1cm}\geq (1 - \negl[\lambda])^{3} \left(1 - \frac{1}{\ell(\lambda)}\right)^{\ell(\lambda)+1},
\end{align*}

where the first inequality comes from the law of total probability, and the last inequality from the definition of a PD-OWF and <Ref>.
This gives that:

\begin{align*}
\pr[x\leftarrow \{0,1\}^{\ell(\lambda)}]{F_{\lambda}(\adv'(1^{\ell(\lambda)},F_{\lambda}(x)))=F_{\lambda}(x)}& \geq (1 - \negl[\lambda])^{3} \left(1 - \frac{1}{\ell(\lambda)}\right)^{\ell(\lambda)+1}\left(1 - \mu(\lambda)\right)\\
& \geq\left(1-O(\mu(\lambda))\right)\left(1 - \frac{1}{\ell(\lambda)}\right)^{\ell(\lambda)+1}.
\end{align*}

Note that this bound is not negligible since

\begin{align*}
\left(1 - \frac{1}{\ell(\lambda)}\right)^{\ell(\lambda)+1}
\geq\frac{1}{10},
\end{align*}

whenever \(\lambda \geq 2\), which contradicts <Ref>.

§ ACKNOWLEDGEMENTS

We deeply thank Alex Bredariol Grilo for many precious discussions. GM was supported by the Quantum Delta NL visitor's programme travel grant, which enabled the collaboration.