Recently May and Schlieper have published a preprint (https://arxiv.org/abs/1905.10074) arguing that the modular exponential register in Shor's algorithms can be replaced with a universally hashed modular exponential register. I've previously asked here ( Shor's Discrete Logarithm Algorithm with a QFT with a small prime base) whether Shor's algorithm for discrete logarithms (which can be used for factoring semiprimes) can be modified to only output the logarithm modulo some small prime $w$ (it seems it can). If further, the QFT can be factored into $\bmod w$ and $\bmod L$ (where $N=Lw$ is about the size of the group order) QFTs, (see the later comments and the second answer) the output qubits can be found through a quantum circuit with only $\mathrm{O(\log N)}$ qubits. $\mathrm{O(\log N)}$ runs with different small prime bases suffice to reconstruct using the Chinese Remainder Theorem the entire logarithm in polynomial time (roughly quintic).
Obviously this could be wrong, but while that's open, one can ask whether May and Schlieper's hashing trick can be extended to estimating probability amplitudes for general quantum circuits. I've tried to make my argument as terse for Stack Exchange and I've focused on the proof of compressibility and left out details about how Markov random fields should represent hashed quantum circuits.
A quantum circuit can be treated as an exponentially large Factor Analysis (FA) problem. The variables and factors are the basis vectors at each layer of the quantum circuit. The quantum gates are linear transformations from factors (which can also be variable) to variables (which can also be factors). The gates are assumed to have (an arbitrary, non-physical) Gaussian noise, which allows FA to work. Factors and variables are related by
\begin{equation} x_{i+1,b} = G_ix_{i,a} + n_{i+1,b} \end{equation}
where $n$ is Gaussian noise, $x_i$ are the values of variables representing the probability amplitudes at each layer and $G_i$ is the unitary quantum gate. This implies Gaussian distributions like
\begin{equation} p(x_{i+1,a}) = \frac{1}{\sqrt{2\pi\sigma_{i,a}^2}} \exp{\bigg( -\frac{[x_{i+1,a} - G_{i}x_{i,b}]^2}{\sigma_{i,a}^2} \bigg)} \end{equation} which can then be converted to a MRF.
(Explanation of Factor Analysis)
http://users.ics.aalto.fi/harri/thesis/valpola_thesis/node37.html
https://www.cs.ubc.ca/~murphyk/Teaching/CS532c_Fall04/Lectures/lec17.pdf
This FA problem can, by the Hammersley–Clifford theorem, be converted into a Markov Random Field (MRF) whose nodes are variables and whose edges are shared variance between the nodes. This MRF can be solved in polynomial time in the size of the MRF (which is still exponential size in the number of qubits) by Gaussian Belief Propagation (GaBP). Unlike general Belief Propagation, GaBP can be guaranteed to converge exponentially quickly in polynomial time by using diagonal loading. (GaBP explained here: https://arxiv.org/abs/0811.2518)
The 4 Clifford+T gates for a universal set of quantum gates. They are
$H = \frac{1}{\sqrt{2}}$ \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}
$X = $ \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}
$CX = $ \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}
$T = $ \begin{pmatrix} 1 & 0 \\ 0 & \omega \end{pmatrix}
where $\omega = e^{\frac{i \pi}{4}}$
X Gate:
\begin{equation} p(x'_{0,Re}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{0,Re} - x_{1,Re}]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{0,Im}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{0,Im} - x_{1,Im}]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{1,Re}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{1,Re} - x_{0,Re}]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{1,Im}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{1,Im} - x_{0,Im}]^2}{\sigma^2} \bigg)} \end{equation}
T Gate:
\begin{equation} p(x'_{0,Re}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{0,Re} - x_{0,Re}]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{0,Im}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{0,Im} - x_{0,Im}]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{1,Re}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{0,Re} - \frac{1}{\sqrt{2}}(x_{0,Re}-x_{0,Im})]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{1,Im}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{1,Im} - \frac{1}{\sqrt{2}}(x_{0,Im}+x_{0,Re})]^2}{\sigma^2} \bigg)} \end{equation}
CX Gate:
\begin{equation} p(x'_{0,Re}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{0,Re} - x_{0,Re}]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{0,Im}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{0,Im} - x_{0,Im}]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{1,Re}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{1,Re} - x_{1,Re}]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{1,Im}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{1,Im} - x_{1,Im}]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{2,Re}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{2,Re} - x_{3,Re}]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{2,Im}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{2,Im} - x_{3,Im}]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{3,Re}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{3,Re} - x_{2,Re}]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{3,Im}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{3,Im} - x_{2,Im}]^2}{\sigma^2} \bigg)} \end{equation}
H Gate:
\begin{equation} p(x'_{0,Re}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{0,Re} - \frac{1}{\sqrt{2}}(x_{0,Re}+x_{1,Re})]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{0,Im}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{0,Im} - \frac{1}{\sqrt{2}}(x_{0,Im}+x_{1,Im})]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{1,Re}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{1,Re} - \frac{1}{\sqrt{2}}(x_{0,Re}-x_{1,Re})]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{1,Im}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{[x'_{1,Im} -\frac{1}{\sqrt{2}}(x_{0,Im}-x_{1,Im})]^2}{\sigma^2} \bigg)} \end{equation}
To apply the hashing trick, we would like to hash each layer, sending qubits to hashed qubits according to some universal hash function and minimize the number of edges connecting the nodes representing hashed states to minimize the runtime of GaBP. To prove that the hashing trick does approximate transition amplitudes, we need to show that each approximation of the action of a quantum gate on hashed qubits (which necessarily forgets some information containing entanglement) produces at most a certain error in probabilities and transition amplitudes. The extra structure of quantum circuits means that the proof of compressibility will be easier with quantum states than with belief propagation and MRFs, but GaBP can nail down computational complexity bounds. Unitarity is and should be necessary to show that errors per layer are additive and independent because linear non-unitary "quantum" circuits can be used to solve $\mathrm{PP-Complete}$ problems.
A natural hashing strategy is to use a non-cryptographic hash function family like $(ax+b) \bmod 2^n \div 2^{(n-p)}$ which is well adapted to hashing qubits, but for each layer keep up to 2 "windows" open on the qubits acted on by the preceding and following quantum gates. Conveniently, the shared covariance between layers can be represented sparsely by $\mathrm{O}(m=2^p)$ edges. Qubits from this hash function can be "wrapped" and "unwrapped" out of the hashed qubits for gates to act on them because the hash function is non-cryptographic.
For ordinary qubits, the universal hash function family $(ax+b) \mod 2^n \div 2^{n-p}$, where $m=2^p$ is effective. $m$, here, is the number of hashed variables (to be multiplied by the unwrapped variables for the total number of variables in the layers). These hash functions make it possible to sparsely 'wrap' and 'unwrap' hashed variables describing unhashed qubits used by gates (we can assume that at most 2 qubits are used by each gate) and the hashed remaining qubits. Each layer of variables borders two quantum gates with at most 2 qubits each, so neighboring layers will differ by at most 4 qubits and 8 variables in terms of which qubits are hashed or not hashed. Each variable is specified by a certain bit of $x$, so mapping nodes from one layer to the next entails hashing a pair of qubits from the former layer and unhashing a pair of qubits from the next layer (which is used in the gate in the layer after next). The qubits that aren't wrapped or unwrapped in neighboring layers can be specified by a 'bitfield' $x_{constant}$, the 'bitfield' to be wrapped into the hashed qubits can be specified as $x_{wrap}$, and the 'bitfield' to be unwrapped can be specified as $x_{unwrap}$. For fixed bases of both pair of qubits, the hashed qubits differ by $a(x_{wrap} - x_{unwrap}) \mod 2^n \div 2^{n-p}$. This quantity, added to the normal prehashed quantity, can result in two neighboring hashed outputs. The fraction of qubit bases going to each possible output can then be calculated. This means that each unhashed node has at most 17 neighbors including itself, but each hashed node has up to $8 \times 2 \times 2 + 2 + 1 = 35$ neighbors including itself and each layer of the MRF is sparse, so $2^p = O(m)$. If some of the wrapped and unwrapped qubits overlap, the overlapping 'bitfields' will cancel, resulting in the correct difference.
Hashed precisions $A^h_{ij}$ can be computed as multiple of the unhashed precisions $A_{ij}$ up to the point that the precision is split among adjacent hashed qubits. This is because $A_{ij}$ in unhashed form consists of copies of $A_{ij}$ restricted to qubits which are acted on by a quantum gate.
Let $B_{\alpha} = a(x_{wrap} - x_{unwrap}) \bmod 2^n \div 2^{n-p}$ and \newline $C_{\alpha}= a(x_{wrap} - x_{unwrap}) \bmod 2^{n-p} / 2^{n-p}$.
The wrapping and unwrapping affects hashed variables like
$x^h_{a,b,h(i)+B_{\alpha}+1} = C_{\alpha}\sum_i x_{a,c,i}$
$x^h_{a,b,h(i)+B_{\alpha}} = (1-C_{\alpha}) \sum_i x_{a,c,i}$
%$k$ is a normalization constant equal to the number of unhashed qubits mapped to hashed qubits.
$x'$ represents the next layer. $x$ represents the current layer. The variances can be taken to be identical across the MRF , except where very small variances are used to fix the value of a variable (which is outside of the part of the MRF used to encode quantum gates). The $\mu$s are hashed $i$s, but there is no need to specify which $i$ because each layer is homogeneous. $G$ is the unitary gate, $a,b$ represent the unwrapped variables. In most cases, $a$ and $b$ will represent different unwrapped qubits.
The noise model is
$$ C_{\alpha}x'_{a,\mu+B_{\alpha}+1} = C_{\alpha}Gx_{b,\mu} + n_{\mu} $$ and $$ (1-C_{\alpha})x'_{a,\mu+B_{\alpha}} = (1-C_{\alpha})Gx_{b,\mu} + n_{\mu} $$
The $x'$ $x$ are sums of the unhashed variables. The $C_{\alpha}$ and $1-C_{\alpha}$ weights are the fractions of the variables which map to each pattern. The noise $n_{\mu}$ is the sum of the noise for each variable with the same hash value ($C_{\alpha}\sum_{h^{-1}(\mu)} n_i$ or $(1-C_{\alpha})\sum_{h^{-1}(\mu)} n_i$) and, as such, grows quadratically, while variables grow linearly. This means the noise variables are proportional to $\sqrt{C_{\alpha}}$ or $\sqrt{1-C_{\alpha}}$ and the variance is proportional to $C_{\alpha}$ or $1-C_{\alpha}$. The linear weighting on the variance partially cancels out the quadratic weighting on the variables, resulting in a linear factor for the precision matrix.
This results in Gaussians
\begin{equation} p(x'_{a,\mu+B_{\alpha}+1}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{C_{\alpha}[x'_{a,\mu+B_{\alpha}+1} - Gx_{b,\mu}]^2}{\sigma^2} \bigg)} \end{equation}
\begin{equation} p(x'_{a,\mu+B_{\alpha}}) \propto \frac{1}{\sqrt{2\pi\sigma^2}} \exp{\bigg( -\frac{(1-C_{\alpha})[x'_{a,\mu+B_{\alpha}} - Gx_{b,\mu}]^2}{\sigma^2} \bigg)} \end{equation}
There are 4 cases over first layer precision and second layer precision and interlayer precision. The variances aren't necessarily complete, except for the interlayer precisions, and precisions from other gates may have to be added.
First and second layer precisions are the same as the unhashed precisions.
$A^h_{x,x,a,b,\mu,\mu} = A_{x,x,a,b,i,i}$
The second layer precisions are
$A^h_{x',x',a,b,\mu,\mu} = A_{x',x',a,b,i,i}$
The interlayer precisions are
$A^h_{x',x,a,b,\mu,\mu+B_{\alpha}+1} = C_{\alpha}A_{x',x,a,b,i,i}$
$A^h_{x',x,a,b,\mu,\mu+B_{\alpha}}= (1-C_{\alpha})A_{x',x,a,b,i,i}$
In other words only the interlayer precisions change.
We need to estimate the error caused by one quantum gate on a hashed quantum gate. This error is induced because, going from one layer to the next, part of the state is forgotten (that is, wrapped back into the hashed states) and part of the state is unwrapped (revealing unknown information). For a universal set of two qubit quantum gates, 4 qubits will be unwrapped in each layer, so that $32m$ variables will be used at each layer. (We can set $m = 2^{ p }$, where $m$ is the needed number of hashed variables.) Each layer will be predictable from the previous layer through a unitary transformation up to the variables representing the 2 qubits forgotten changing layers.
The error estimates in Theorem 6.1 in May and Schlieper may be adapted for hashed applications of quantum gates. The probability of observing the desired qubits $z$ may be given a lower bound of $\frac{m-1}{m}p(x)$ and, since the number of levels in $z$ is small, $c$ (usually 4), there is an upper bound of $\frac{m-1}{m}p(x)+\frac{1}{m}$ from the available probality and and upper bound of $\frac{m-1}{m}p(x)+\frac{c^2}{m}$ from summing out forgotten qubits.
Here, $x$ stands for the unwrapped qubits in the following layer. This can include the qubits unwrapped for the next gate. $y$ are the hashed qubits which are preserved going from one gate to another. $z$ are the unwrapped qubits in the previous layer that are hashed into $y$ and forgotten. $y'$ is $y$ hashed with $z$. $z'$ are the $z$ which correspond to the hashed with $z$ basis $y'$. The transformation between $w_{x,y',z'}$ and $w_{x,y,z}$ is unitary.
The weights for $w_{x,y',z'}$ are calculated from the universal hash function $(ax+b) \bmod 2^n \div 2^{n-p}$. Each basis vector can be encoded as an unsigned integer and hashed into a smaller unsigned integer, like a bitfield. To hash the $z$ qubits into the $y$ qubits, add the bitfield represening the $z$ qubits and apply the hash function. The $\bmod 2^n$ differs by $ax_z \bmod 2^n$. The resulting $y'$ value will then shift by either $\lfloor ax_z \bmod 2^n \div 2^{n-p} \rfloor$ or $\lfloor ax_z \bmod 2^n \div 2^{n-p} \rfloor +1$. The fractions of the two shifts are $$1 - \frac{ax_z \bmod 2^{n-p} }{2^{n-p}} $$ and $$\frac{ax_z \bmod 2^{n-p} }{2^{n-p}}$$, respectively.
The state after the last quantum gate is applied, but before the $z$ qubits are hashed in and discarded is: \begin{equation} \psi = \sum_x \sum_y \sum_z w_{x,y,z}|x \rangle | y \rangle |z \rangle \end{equation}
The state remembered by the next layer after $z$ is hashed into $y$ and forgotten is \begin{equation} \psi' = \sum_x \sum_{y'} w_{x,y'}|x \rangle | y' \rangle \end{equation} This differs from May and Schlieper because $z$s originally with the same $(x,y)$ will be randomly sent to a different $(x,y')$.
The condition in Theorem 6.1 \begin{equation} W_{x,y} := \sum_z w_{x,y,z} = 0 \end{equation} does not hold in general in our case. Instead we are forced to forget a only a small number of qubits each layer of the MRF to keep this sum from becoming too large. And, in any case, the formula becomes \begin{equation} W_{x,y'} := \sum_{z'} w_{x,y',z'} \end{equation}
The probability of observing a hashed state is
\begin{equation} p_h(x,y') = \frac{1}{\mathcal{H}} \sum_{h \in \mathcal{H}} (\sum_{i = 0}^{m-1} |\sum_{z'} w_{x,y',z'}|^2) \end{equation}
$\mathcal{H}$ is a normalization factor over all possible hash functions in the given family. The sum over $z'$ is correct because the $ w_{x,y',z'}$ are unitary transformations of $ w_{x,y,z}$. The universality of the hash function allows the expression to be simplified to
\begin{equation} p_h(x,y') = \sum_{z'} |w_{x,y',z'}|^2 + \frac{1}{m} \sum_{z'_1 \neq z'_2} w_{x,y',z'_1}\overline{w_{x,y',z'_2}} \end{equation}
The derivation of the error in probability is almost the same, except that there is a range in possible errors and, unlike May and Schlieper's proof the errors aren't packed into $x=0$ basis vectors.
\begin{equation} W_{x,y'} = \frac{1}{m} |\sum_{z'} w_{x,y',z'}|^2 = \frac{1}{m} \sum_{z'} |w_{x,y',z'}|^2 + \frac{1}{m} \sum_{z'_1 \neq z'_2} w_{x,y',z'_1}\overline{w_{x,y',z'_2}} = p_h(x,y') - \frac{1}{m} \sum_{z'} |w_{x,y',z'}|^2 \end{equation}
\begin{equation} \frac{m-1}{m} p(x,y') \leq p_h(x,y') \leq \frac{m-1}{m} p(x,y') + W_{x,y'} \leq\frac{m-1}{m} p(x,y') + \frac{c^2}{m} \end{equation}
Since $p_h$ is a probability, there is a different logical upper bound
\begin{equation} \frac{m-1}{m} p(x,y') \leq p_h(x,y') \leq \frac{m-1}{m} p(x,y') + \frac{1}{m} \end{equation}
On average, this second inequality should hold, although I don't know how to prove it can't be violated. Since both these upper bounds are an absolute cap on the error in probability, summing out $y$ will still leave the same error margins and the desired single qubit probability amplitude estimates will be accurate to $\mathrm{O}(\frac{1}{m})$.
Summing over only the $z$ qubits is necessary because it can be that $W_x > 1$ even with only polynomially many hashed variables which cannot be interpreted as a probability. For instance, one layer of $n$ Hadamard gates with state to be hashed $\sum^{2^n -1}_{i=0}\frac{1}{\sqrt{2^n}} x_i$, would have $W_x = 2^n$ which is nonsensically large. Even a hashed state would still have $W_x = m$. To control $W$ one needs to work only with small unitary transform that affect a constantly bounded number of qubits, like ordinary quantum gates which necessitates only summing out one quantum gate at a time.
To guarantee $W_{x,y'}$ is small enough, we need to reduce the number of $z'$ per $x,y'$ to a constant so that increasing $m$ will make them inconsequential. The terms summed in $W_{x,y'}$ will always be $|w_{x,y'}| \leq 1$ so $W_{x,y'} \leq \frac{c^2}{m}$. On average, the $w_{x,y',z'}$ will be much smaller, on the order of $\mathrm{O}(\frac{1}{\sqrt{m}})$ which results in an average error in probability around $\mathrm{O}(\frac{1}{m^2})$.
This argument narrows down the range of error in probability, but perhaps there could still be large error margins in phase. To narrow the range of error in phase, perform Hadamard(s) on the $y'$ qubits and extract the phase. The probability estimates then make comparable restrictions the range of phase error. So the restriction on errors in probability is also a restriction on errors in probability amplitude.
We can then use the unitarity of quantum gates to show that quantum gates preserve the magnitude of errors in amplitude. Since unitary transformations preserve inner products, the correlation between the correct state and the approximate state will remain the same. Non-unitary linear transformations can also be represented as FA problems and hashed and it must be because errors can be amplified by non-unitary gates that the hashing trick will fail on them. Otherwise, the hashing trick could be used to solve $\mathrm{PP-Complete}$ counting problems which are considerably hard than $\mathrm{NP}$.
In the worst case, amplitude errors will add up over $g$ gates, so amplitude and probability errors at the end of the circuit will be at most $\mathrm{O}(\frac{g}{m})$. Likewise, the independence of errors between implies that the total error for the circuit are roughly bounded by multiplying the probability error margins together and assuming $m$ is large enough for the linear approximation to hold to get
\begin{equation} \frac{m-g}{m} p^{total}(x,y') \leq p^{total}_h(x,y') \leq \frac{m-g}{m} p^{total}(x,y') + \frac{g}{m} \end{equation}
So, as long as $m \gg g \epsilon$, the final error in probability and probability amplitude will be $< \epsilon$.
Using the broadcast variant of GaBP, the runtime to calculate probability amplitudes is $\mathrm{O}(E \log N)$, where $E$ is the number of edges and $N$ is the number of nodes in the MRF. For quantum circuits the running time is roughly quadratic log. For estimates of probability amplitudes which are accurate up to $\pm \epsilon$, the running time is $\mathrm{O}((\frac{g^2+gn\log g}{\epsilon})\log{(\frac{g^2+gn\log g}{\epsilon}}))$, where $n$ is the number of qubits and $g$ is the number of gates.
