text:
# Signature of a Pairing Transition in the Heat Capacity of Finite Nuclei

## Abstract

The heat capacity of iron isotopes is calculated within the interacting shell model using the complete $`(pf+0g_{9/2})`$-shell. We identify a signature of the pairing transition in the heat capacity that is correlated with the suppression of the number of spin-zero neutron pairs as the temperature increases. Our results are obtained by a novel method that significantly reduces the statistical errors in the heat capacity calculated by the shell model Monte Carlo approach. The Monte Carlo results are compared with finite-temperature Fermi gas and BCS calculations.

Pairing effects in finite nuclei are well known; examples include the energy gap in the spectra of even-even nuclei and an odd-even effect observed in nuclear masses. However, less is known about the thermal signatures of the pairing interaction in nuclei. In a macroscopic conductor, pairing leads to a phase transition from a normal metal to a superconductor below a certain critical temperature, and in the BCS theory  the heat capacity is characterized by a finite discontinuity at the transition temperature. As the linear dimension of the system decreases below the pair coherence length, fluctuations in the order parameter become important and lead to a smooth transition. The effects of both static fluctuations  and small quantal fluctuations  have been explored in studies of small metallic grains. A pronounced peak in the heat capacity is observed for a large number of electrons, but for less than $`100`$ electrons the peak in the heat capacity all but disappears. In the nucleus, the pair coherence length is always much larger than the nuclear radius, and large fluctuations are expected to suppress any singularity in the heat capacity. An interesting question is whether any signature of the pairing transition still exists in the heat capacity of the nucleus despite the large fluctuations. When only static and small-amplitude quantal fluctuations are taken into account, a shallow ‘kink’ could still be seen in the heat capacity of an even-even nucleus . This calculation, however, was limited to a schematic pairing model. Canonical heat capacities were recently extracted from level density measurements in rare-earth nuclei  and were found to have an $`S`$-shape that is interpreted to represent the suppression of pairing correlations with increasing temperature.

The calculation of the heat capacity of the finite interacting nuclear system beyond the mean-field and static-path approximations is a difficult problem. Correlation effects due to residual interactions can be accounted for in the framework of the interacting nuclear shell model. However, at finite temperature a large number of excited states contribute to the heat capacity and very large model spaces are necessary to obtain reliable results. The shell model Monte Carlo (SMMC) method  enables zero- and finite-temperature calculations in large spaces. In particular, the thermal energy $`E(T)`$ can be computed versus temperature $`T`$ and the heat capacity can be obtained by taking a numerical derivative $`C=dE/dT`$. However, the finite statistical errors in $`E(T)`$ lead to large statistical errors in the heat capacity at low temperatures (even for good-sign interactions). Such large errors occur already around the pairing transition temperature and thus no definite signatures of the pairing transition could be identified. Furthermore, the large errors often lead to spurious structure in the calculated heat capacity. Presumably, a more accurate heat capacity can be obtained by a direct calculation of the variance of the Hamiltonian, but in SMMC such a calculation is impractical since it involves a four-body operator. The variance of the Hamiltonian has been calculated using a different Monte Carlo algorithm , but that method is presently limited to a schematic pairing interaction. Here we report a novel method for calculating the heat capacity within SMMC that takes into account correlated errors and leads to much smaller statistical errors. Using this method we are able to identify a signature of the pairing transition in realistic calculations of the heat capacity of finite nuclei. The signature is well correlated with the suppression in the number of spin-zero pairs across the transition temperature.

The Monte Carlo approach is based on the Hubbard-Stratonovich (HS) representation of the many-body imaginary-time propagator, $`e^{\beta H}=D[\sigma ]G_\sigma U_\sigma `$, where $`\beta `$ is the inverse temperature, $`G_\sigma `$ is a Gaussian weight and $`U_\sigma `$ is a one-body propagator that describes non-interacting nucleons moving in fluctuating time-dependent auxiliary fields $`\sigma `$. The canonical thermal expectation value of an observable $`O`$ can be written as $`O=D[\sigma ]G_\sigma \mathrm{Tr}(OU_\sigma )/D[\sigma ]G_\sigma \mathrm{Tr}U_\sigma `$, where $`\mathrm{Tr}`$ denotes a canonical trace for $`N`$ neutrons and $`Z`$ protons. We can rewrite

$$O=\frac{\left[\mathrm{Tr}(OU_\sigma )/\mathrm{Tr}U_\sigma \right]\mathrm{\Phi }_\sigma _W}{\mathrm{\Phi }_\sigma _W},$$
(1)
where $`\mathrm{\Phi }_\sigma =\mathrm{Tr}U_\sigma /|\mathrm{Tr}U_\sigma |`$ is the Monte Carlo sign, and we have used the notation $`X_\sigma _WD[\sigma ]W(\sigma )X_\sigma /D[\sigma ]W(\sigma )`$ with $`W(\sigma )G_\sigma |\mathrm{Tr}U_\sigma |`$. In SMMC we divide the imaginary-time interval $`(0,\beta )`$ into $`N_t`$ time slices of length $`\mathrm{\Delta }\beta =\beta /N_t`$, and sample the fields $`\sigma (\tau _n)`$ fields at all $`N_t`$ time slices $`\tau _n=n\mathrm{\Delta }\beta `$ according to the positive-definite weight function $`W(\sigma )`$. Each quantity $`X_\sigma _W`$ in Eq. (1) is then estimated as an arithmetic average over the chosen samples.

In particular the thermal energy can be calculated as a thermal average of the Hamiltonian $`H`$. The heat capacity $`C=\beta ^2E/\beta `$ is then calculated by estimating the derivative as a finite difference

$`C=\beta ^2{\displaystyle \frac{E(\beta +\delta \beta )E(\beta \delta \beta )}{2\delta \beta }}+O(\delta \beta )^2.`$ (2)
At low temperatures, $`E(\beta )`$ decreases slowly with $`\beta `$ and even small errors in $`E(\beta )`$ lead to relatively large statistical errors in $`C`$. Conventionally, the calculation of $`E(\beta )`$ for each $`\beta `$ is done by a new Monte Carlo sampling of the $`\sigma `$ fields and consequently the energies $`E(\beta \delta \beta )`$ and $`E(\beta +\delta \beta )`$ in (2) are uncorrelated. However, if the calculation of both $`E(\beta \pm \delta \beta )`$ can be done using a common set of sampling fields, the correlated errors of $`C`$ are expected to be smaller.

The energies $`E(\beta \pm \delta \beta )`$ are calculated from

$$E(\beta \pm \delta \beta )=\frac{D[\sigma ^\pm ]G_{\sigma ^\pm }(\beta \pm \delta \beta )\mathrm{Tr}[HU_{\sigma ^\pm }(\beta \pm \delta \beta )]}{D[\sigma ^\pm ]G_{\sigma ^\pm }(\beta \pm \delta \beta )\mathrm{Tr}U_{\sigma ^\pm }(\beta \pm \delta \beta )},$$
(3)
where the corresponding $`\sigma `$ fields are denoted by $`\sigma ^\pm `$. To have the same number of time slices $`N_t`$ in the discretized version of (3) as in the original HS representation of $`E(\beta )`$, we define modified time slices $`\mathrm{\Delta }\beta _\pm `$ by $`N_t\mathrm{\Delta }\beta _\pm =\beta \pm \delta \beta `$. We next change integration variables in (3) from $`\sigma ^\pm `$ to $`\sigma `$ according to $`\sigma ^\pm =(\mathrm{\Delta }\beta /\mathrm{\Delta }\beta _\pm )^{1/2}\sigma `$, so that the Gaussian weight is left unchanged $`G_{\sigma ^\pm }(\beta \pm \delta \beta )\mathrm{exp}\left[\underset{\alpha n}{}\frac{1}{2}|v_\alpha |(\sigma _\alpha ^\pm (\tau _n))^2\mathrm{\Delta }\beta _\pm \right]=\mathrm{exp}\left[\underset{\alpha n}{}\frac{1}{2}|v_\alpha |(\sigma _\alpha (\tau _n))^2\mathrm{\Delta }\beta \right]=G_\sigma (\beta )`$ ($`v_\alpha `$ are the interaction ‘eigenvalues’, obtained by writing the interaction in a quadratic form $`_\alpha v_\alpha \widehat{\rho }_\alpha ^2/2`$, where $`\widehat{\rho }_\alpha `$ are one-body densities). Rewriting (3) using the measure $`D[\sigma ]`$ (the Jacobian resulting from the change in integration variables is constant and canceled between the numerator and denominator), we find

$$E(\beta \pm \delta \beta )=\frac{\frac{\mathrm{Tr}HU_{\sigma ^\pm }(\beta \pm \delta \beta )}{\mathrm{Tr}U_{\sigma ^\pm }(\beta \pm \delta \beta )}\frac{\mathrm{Tr}U_{\sigma ^\pm }(\beta \pm \delta \beta )}{\mathrm{Tr}U_\sigma (\beta )}\mathrm{\Phi }_\sigma _W}{\frac{\mathrm{Tr}U_{\sigma ^\pm }(\beta \pm \delta \beta )}{\mathrm{Tr}U_\sigma (\beta )}\mathrm{\Phi }_\sigma _W}\frac{H_\pm }{Z_\pm }.$$
(4)
The heat capacity in (2) is calculated from $`C=\beta ^2(2\delta \beta )^1(H_+/Z_+H_{}/Z_{})`$. Since the same set of fields $`\sigma `$ is used in the calculation of both $`E(\beta \pm \delta \beta )`$, we expect strong correlations among the quantities $`H_\pm `$ and $`Z_\pm `$, which would lead to a smaller error for $`C`$. The covariances among $`H_\pm `$ and $`Z_\pm `$ as well as their variances can be calculated in the Monte Carlo and used to estimate the correlated error of the heat capacity.

We have calculated the heat capacity for the iron isotopes 52-62Fe using the complete $`(pf+0g_{9/2})`$-shell and the good-sign interaction of Ref. . Fig. 4 demonstrates the significant improvement in the statistical Monte Carlo errors. On the left panel of this figure we show the heat capacity of 54Fe calculated in the conventional method, while the right panel shows the results from the new method. The statistical errors for $`T0.51`$ MeV are reduced by almost an order of magnitude. The results obtained in the conventional calculation seem to indicate a shallow peak in the heat capacity around $`T1.25`$ MeV, but the calculation using the improved method shows no such structure.

The heat capacities of four iron isotopes 55-58Fe, calculated with the new method, are shown in the top panel of Fig. 4. The heat capacities of the two even-mass iron isotopes (56Fe and 58Fe) show a different behavior around $`T0.70.8`$ MeV as compared with the two odd-mass isotopes (55Fe and 57Fe). While the heat capacity of the odd-mass isotopes increases smoothly as a function of temperature, the heat capacity of the even-mass isotopes is enhanced for $`T0.61`$ MeV, increasing sharply and then leveling off, displaying a ‘shoulder.’ This ‘shoulder’ is more pronounced for the isotope with more neutrons (58Fe). To correlate this behavior of the heat capacity with a pairing transition, we calculated the number of $`J=0`$ nucleon pairs in these nuclei. A $`J=0`$ pair operator is defined as usual by

$$\mathrm{\Delta }^{}=\underset{a,m_a>0}{}\frac{(1)^{j_am_a}}{\sqrt{j_a+1/2}}a_{j_am_a}^{}a_{j_am_a}^{},$$
(5)
where $`j_a`$ is the spin and $`m_a`$ is the spin projection of a single-particle orbit $`a`$. Pair-creation operators of the form (5) can be defined for protons ($`\mathrm{\Delta }_{pp}^{}`$), neutrons ($`\mathrm{\Delta }_{nn}^{}`$), and proton-neutrons ($`\mathrm{\Delta }_{pn}^{}`$). The average number $`\mathrm{\Delta }^{}\mathrm{\Delta }`$ of $`J=0`$ pairs (of each type) can be calculated exactly in SMMC as a function of temperature. The bottom panel of Fig. 4 shows the number of neutron pairs $`\mathrm{\Delta }_{nn}^{}\mathrm{\Delta }_{nn}`$ for 55-58Fe. At low temperature the number of neutron pairs for isotopes with an even number of neutrons is significantly larger than that for isotopes with an odd number of neutrons. Furthermore, for the even-mass isotopes we observe a rapid suppression of the number of neutron pairs that correlates with the ‘shoulder’ observed in the heat capacity. The different qualitative behavior in the number of neutron pairs versus temperature between odd- and even-mass iron isotopes provides a clue to the difference in their heat capacities. A transition from a pair-correlated ground state to a normal state at higher temperatures requires additional energy for breaking of neutron pairs, hence the steeper increase observed in the heat capacity of the even-mass iron isotopes. Once the pairs are broken, less energy is required to increase the temperature, and the heat capacity shows only a moderate increase.

It is instructive to compare the SMMC heat capacity with a Fermi gas and BCS calculations. The heat capacity can be calculated from the entropy using the relation $`C=TS/T`$. The entropy $`S`$ of uncorrelated fermions is given by

$$S(T)=\underset{a}{}[f_a\mathrm{ln}f_a+(1f_a)\mathrm{ln}(1f_a)],$$
(6)
with $`f_a`$ being the finite-temperature occupation numbers of the single-particle orbits $`a`$. Above the pairing transition-temperature $`T_c`$, $`f_a`$ are just the Fermi-Dirac occupancies $`f_a=[1+e^{\beta (ϵ_a\mu )}]^1`$, where $`\mu `$ is the chemical potential determined from the total number of particles and $`ϵ_a`$ are the single-particle energies. Below $`T_c`$, it is necessary to take into account the BCS solution which has lower free energy. Since condensed pairs do not contribute to the entropy, the latter is still given by (6) but $`f_a`$ are now the quasi-particle occupancies ,

$$f_a=\frac{1}{1+e^{\beta E_a}}.$$
(7)
$`E_a=\sqrt{(ϵ_a\mu )^2+\mathrm{\Delta }^2}`$ are the quasi-particle energies, where the gap $`\mathrm{\Delta }(T)`$ and the chemical potential $`\mu (T)`$ are determined from the finite-temperature BCS equations. In practice, we treat protons and neutrons separately.

We applied the Fermi gas and BCS approximations to estimate the heat capacities of the iron isotopes. To take into account effects of a quadrupole-quadrupole interaction, we used an axially deformed Woods-Saxon potential to extract the single-particle spectrum $`ϵ_a`$ . A deformation parameter $`\delta `$ for the even iron isotopes can be extracted from experimental $`B(E2)`$ values. However, since $`B(E2)`$ values are not available for all of these isotopes, we used an alternate procedure. The excitation energy $`E_x(2_1^+)`$ of the first excited $`2^+`$ state in even-even nuclei can be extracted in SMMC by calculating $`J^2_\beta `$ at low temperatures and using a two-state model (the $`0^+`$ ground state and the first excited $`2^+`$ state) where $`J^2_\beta 6/(1+e^{\beta E_x(2_1^+)}/5)`$ . The excitation energy of the $`2_1^+`$ state is then used in the empirical formula of Bohr and Mottelson  $`\tau _\gamma =(5.94\pm 2.43)\times 10^{14}E_x^4(2_1^+)Z^2A^{1/3}`$ to estimate the mean $`\gamma `$-ray lifetime $`\tau _\gamma `$ and the corresponding $`B(E2)`$. The deformation parameter $`\delta `$ is then estimated from $`B(E2)=[(3/4\pi )Zer_0^2A^{2/3}\delta ]^2/5`$. We find (using $`r_0=1.27`$ fm) $`\delta =0.225,0.215,0.244,0.222,0.230`$, and $`0.220`$ for the even iron isotopes 52Fe – 62Fe, respectively. For the odd-mass iron isotopes we adapt the deformations in Ref. . The zero-temperature pairing gap $`\mathrm{\Delta }`$ is extracted from experimental odd-even mass differences and used to determine the pairing strength $`G`$ (needed for the finite temperature BCS solution).

The top panels of Fig. 4 show the Fermi-gas heat capacity (dotted-dashed lines) for 59Fe (right) and 60Fe (left) in comparison with the SMMC results (symbols). The SMMC heat capacity in the even-mass 60Fe is below the Fermi-gas estimate for $`T0.5`$ MeV, but is enhanced above the Fermi gas heat capacity in the region $`0.5T0.9`$ MeV. The line shape of the heat capacity is similar to the $`S`$-shape found experimentally in the heat capacity of rare-earth nuclei . We remark that the saturation of the SMMC heat capacity above $`1.5`$ MeV (and eventually its decrease with $`T`$) is an artifact of the finite model space. The solid line shown for 60Fe is the result of the BCS calculation. There are two ‘peaks’ in the heat capacity corresponding to separate pairing transitions for neutrons ($`T_c^n0.9`$ MeV) and protons ($`T_c^p1.2`$ MeV). The finite discontinuities in the BCS heat capacity are shown by the dotted lines. The pairing solution describes well the SMMC results for $`T0.6`$ MeV. However, the BCS peak in the heat capacity is strongly suppressed around the transition temperature. This is expected in the finite nuclear system because of the strong fluctuations in the vicinity of the pairing transition (not accounted for in the mean-field approach). Despite the large fluctuations, a ‘shoulder’ still remains around the neutron-pairing transition temperature.

The bottom panels of Fig. 4 show the number of spin-zero pairs versus temperature in SMMC. The number of $`p`$-$`p`$ and $`n`$-$`p`$ pairs are similar in the even and odd-mass iron isotopes. However, the number of $`n`$-$`n`$ pairs at low $`T`$ differs significantly between the two isotopes. The $`n`$-$`n`$ pair number of 60Fe decreases rapidly as a function of $`T`$, while that of 59Fe decreases slowly. The S-shape or shoulder seen in the SMMC heat capacity of 60Fe correlates well with the suppression of neutron pairs.

Fig. 4 shows the complete systematics of the heat capacity for the iron isotopes in the mass range $`A=5262`$ for both even-mass (left panel) and odd-mass (right panel). At low temperatures the heat capacity approaches zero, as expected. When $`T`$ is high, the heat capacity for all isotopes converges to approximately the same value. In the intermediate temperature region ($`T0.7`$ MeV), the heat capacity increases with mass due to the increase of the density of states with mass. Pairing leads to an odd-even staggering effect in the mass dependence (see also in Fig. 4) where the heat capacity of an odd-mass nucleus is significantly lower than that of the adjacent even-mass nuclei. For example, the heat capacity of 57Fe is below that of both 56Fe and 58Fe. The heat capacities of the even-mass 58Fe, 60Fe, and 62Fe all display a peak around $`T0.7`$ MeV, which becomes more pronounced with an increasing number of neutrons.

In conclusion, we have introduced a new method for calculating the heat capacity in which the statistical errors are strongly reduced. A systematic study in several iron isotopes reveals signatures of the pairing transition in the heat capacity of finite nuclei despite the large fluctuations.

This work was supported in part by the Department of Energy grants No. DE-FG-0291-ER-40608. Computational cycles were provided by the San Diego Supercomputer Center (using NPACI resources), and by the NERSC high performance computing facility at LBL.


format: text

text:
# Cosmic Rays above 10¹⁴ eV

## 1 Introduction

The earth is continuously bombarded by a stream of high energy particles which arrive uniformly from all directions. These particles are cosmic rays and were discovered in 1912 by Hess through a series of balloon flights in which he carried electrometers to over 5000 m. We now know that the cosmic ray spectrum extends from 1 GeV to above $`10^{20}`$ eV (or 100 EeV) but we have only a rudimentary understanding of where cosmic rays come from. The difficulty is that the particles are stripped nuclei of atoms: consequently the galactic magnetic fields, typically a few $`\mu `$G, are sufficiently strong to scramble their paths except at the very highest energies. In this short review we will describe the properties of cosmic rays from $`10^{14}`$ eV up to the highest energy so far found, $`3\times 10^{20}`$ eV. Below $`10^{14}`$ eV the flux of particles is sufficiently high that individual nuclei can be studied by flying complex detector packages in balloons. It is found that the majority of particles are the nuclei of the common elements and that around 1 GeV the frequency distribution is strikingly similar to that found in ordinary material in the solar system. The striking exception is the abundance of elements such as Li, Be and B which are over-abundant because of the fragmentation of heavier nuclei against inter-stellar hydrogen.

Above $`10^{14}`$ eV the techniques used to study the particles employ a phenomenon discovered by Auger and his group in 1938 . When a high energy particle enters the atmosphere it initiates a cascade or air shower which is large enough and sufficiently penetrating to reach ground level. At $`10^{15}`$ eV about $`10^6`$ particles, mainly electrons, are spread out over about a hectare. With a small number of judiciously positioned detectors it is possible to measure the direction of the incoming shower to within about 1 degree using the relative arrival times of the shower at the detectors. The size of an air shower array depends on the energy region which is being studied. To explore the region from $`10^{14}`$ to $`10^{16}`$ eV an area of $`4\times 10^4`$ m2 is typical but at the highest energies, where the rate is measured in particles per km2 per century, much large areas must be instrumented. The Pierre Auger Observatory, which will collect an unprecedented number of events above $`10^{19}`$ eV, will cover an area 30 times the size of the city of Paris.

## 2 Cosmic Rays in the Region of the Knee

The cosmic ray energy spectrum is nearly featureless lacking the lines or dips which would characterise an electromagnetic spectrum covering so many decades. It is often described in terms of a power law which fits the data over many decades. Thus the differential spectrum is of the form $`dI=kE^\gamma dE`$. One of the most prominent features is the steepening of the slope of the energy spectrum from around $`\gamma =2.7`$ to $`\gamma =3.1`$ at an energy of $`3\times 10^{15}`$ eV. This is known as the ‘knee’ of the spectrum. At an energy above $`10^{18}`$ eV the spectrum flattens at what is called the ‘ankle’. The knee in the spectrum was first deduced from observations of the shower size spectrum made in 1956 but it remains unclear as to what is the cause of this spectral steepening.

It is currently believed that cosmic rays are accelerated in a process called diffusive shock acceleration. Suitable astrophysical shocks occur in supernovae explosions and particles of the interstellar medium gain energy as they are repeatedly overtaken by the expanding shock wave. Most work (e.g. ) leads to the conclusion that the accelerated particles will have a spectrum close to $`E^{2.1}`$, considerably flatter than the measured value. The maximum energy reached in the shocks associated with supernova remnants is close to $`Z\times 10^{14}`$ eV (see also ) and at the maximum energy the spectrum of a species falls abruptly. This model can be reconciled, to some extent, with observations when the production spectrum is folded with the energy-dependence of the lifetime of cosmic rays in the galaxy. Analysis of the abundance of fragmentation nuclei with energy suggests that the lifetime varies as $`E^{0.6}`$. Thus the observed and predicted spectral slopes ($`\gamma =2.7`$) can be reconciled. However this picture cannot hold to energies very far beyond the knee as the lifetime of the particles in the galaxy is predicted to be so short that strong anisotropies should be seen above $`10^{16}`$ eV whereas the observed uniformity is within 1%. This difficulty has led Swordy  to suggest that there is a minimum propagation path length of 0.013 g cm-2 or about 3 kpc. Alternatively Hillas  has suggested that the trapping time varies as $`E^{0.33}`$ (as found with Kolmogorov turbulence) and that the energy spectrum of particles from the supernovae is much steeper than $`E^{2.1}`$ but extends to higher energies.

It would help greatly to constrain these and other theories if the energy spectrum was measured more exactly and, in particular, if the way in which the mass composition changes in the decades before and after the knee was better known. Significant progress has been made on these problems in recent years, but they are far from solved. The shower observables at ground level (sometimes mountain altitudes when observing in the knee region) are the number of muons, the number of electrons, the Cherenkov light signal produced as the electrons (mainly) propagate through the atmosphere and, but measured at only a small number of installations, the number and energy spectrum of hadrons. To go from ground parameters to the primary energy requires recourse to a Monte Carlo calculation in which the particle interactions are followed stochastically, with assumptions being made about the particle physics characteristics of the interactions. At $`10^{15}`$ eV one is well above accelerator energies and therefore important variables such as cross-sections, inelasticity and multiplicity must be inferred from extrapolation, often guided by a model. Nucleon-nucleus, nucleus-nucleus and pion-nucleus collisions are all important. Until their energy falls below about $`10^{12}`$ eV, the charged pions are more likely to interact and further feed the hadronic part of the cascade. The neutral pions, which decay almost instantaneously, fuel the electromagnetic cascade which can be calculated very exactly.

Extracting the energy is not straightforward and a model must be adopted to relate the observed numbers of electrons and muons to the primary energy. Currently the model which appears to fit much of the data in the knee region is the QGSJET model  based on the quark-gluon-string model of particle interactions. This model is required to extrapolate accelerator observations, which are largely made in the central rapidity region, to the forward region where observations are lacking but which are of most importance to air shower simulations. A number of detailed studies  find that the QGSJET model can describe much of the data on muons and electrons. However for the hadronic component, measured above 50 GeV with high accuracy in the KASCADE experiment, it is found that the model predicts more hadrons than are observed in showers produced by primaries of $`10^{16}`$ eV. Only if the primaries at this energy were heavier than Fe could the data be reconciled with the QGSJET model. Such a solution is regarded as unphysical because of the decline in the natural abundance of elements heavier than Fe. A convincing representation of the energy spectrum from the KASCADE data  is shown in figure 1. This spectrum agrees with data from other recent experiments such as CASA-MIA , HEGRA  or CASA-BLANCA  when the same model is used to interpret the ground level data. Using other models can change the intensity at a given energy by as much as 30% (see  for a discussion). Generally different models do not alter the slope before or after the knee which is close to $`3\times 10^{15}`$ eV by most estimates.

There are many approaches to determining the primary mass in the region of the knee . Here there is space only to mention one of these methods which has been developed recently and which looks rather promising. Many of the electrons in a air-shower have a speed high enough for them to radiate part of their energy as Cherenkov light and this can be detected above the night sky background on clear moonless nights. Model calculations have shown  that the Cherenkov light signal at 100 m (and further) from the axis is a good measure of primary energy while the slope of the Cherenkov lateral distribution is sensitive to the depth of shower maximum, $`X_{\text{max}}`$. Although the conversion from the observables to the energy and the depth of maximum is mass dependent, methods have been developed to circumvent this difficulty to some extent. Cherenkov light emission from showers has been studied at a number of experiments  but, for illustrative purposes, only data from CASA-BLANCA will be described. This experiment used the CASA array of scintillators  to find the shower cores and an array of 144 photomultipliers to measure the Cherenkov light parameters. Details of the analysis have been given in a series of articles  and results are shown in figure 2. What is impressive is that for a range of four models (HPDM, QGSJET, SIBYLL and VENUS) and a mass mixture of protons, nitrogen and iron, the derived values of $`X_{\text{max}}`$ are quite model independent. At $`10^{15}`$ eV where $`X_{\text{max}}`$ is about 500 g cm-2, the spread in the inferred value is only 10 g cm-2. However for a particular mass the values predicted for $`X_{\text{max}}`$ show considerable spread. Again taking $`10^{15}`$ eV as a reference, the difference in $`X_{\text{max}}`$ predicted by different models for protons is 50 g cm-2 and for iron about 30 g cm-2. This implies that the extracted mean mass is model dependent, as is seen in figure 3 where the results of Fortson *et al* , deduced from their measurements of $`X_{\text{max}}`$ as a function of energy, are shown. Here $`<\mathrm{ln}A>`$ is plotted against energy for various models. Mean $`\mathrm{ln}A`$ is an appropriate variable as at a given energy $`X_{\text{max}}`$ is known to vary with $`\mathrm{ln}A`$ (Linsley 1977).

The trends in the data are identical for the different shower models. The mean logarithmic mass becomes lighter in the knee region than at lower energies before becoming heavier again at higher energies. Unfortunately the data at balloon energies are not sufficiently accurate to guide the choice of models. At $`10^{14}`$ eV/particle the measured value of $`<\mathrm{ln}A>`$ is $`1.8\pm 0.4`$ and at $`10^{15}`$ eV (based on only 4 directly measured events) the corresponding value is $`2\pm 1`$. However the KASCADE analysis of electrons, muons and hadrons is most consistent with QGSJET which predicts the lowest mean mass in the knee region. Thus this conclusion does not support the ideas of Erlykin and Wolfendale  who favour an oxygen dominated cosmic ray beam in the knee region with iron becoming important at energies 26/8 higher. In their model most of the local cosmic ray flux is from a nearby supernova explosion. However a pattern in which the mass becomes lighter in the knee region before becoming heavier again is similar to what is predicted by Swordy  in the model mentioned above

## 3 Cosmic Rays in the Region of the Ankle and above

The first important feature in this energy range comes from the existence of radiation fields filling the universe of which the 2.7 K cosmic microwave background (CMB) is the best known. All stable particles expected to constitute the cosmic rays coming from large distances (except neutrinos) inelastically interact with those background photons above some threshold energy depending on the wavelength of the radiation and the nature of the cosmic rays: incident photons producing $`e^+e^{}`$ pairs on infra-red radiation in the TeV range, on the CMB at a few hundreds of TeV, on radio waves at a few tens of EeV; incident protons with photopion production or nuclei undergoing photodisintegration at a few tens of EeV (the so-called Greisen-Zatsepin-Kuzmin, or GZK, spectral cutoff ). The important consequence of this is that at energies between, say, 50 and several hundreds of EeV, photons, protons and nuclei have rather short attenuation lengths, of the order of a few tens of Mpc. To state it more explicitly, if we observe cosmic rays in the above energy range on earth (let us call them ultra-high-energy cosmic rays or UHECR), it is impossible for them to come from a source whose distance would exceed 100 Mpc (roughly the size of our local supercluster), unless exotic particles or interaction models are envisaged.

The second feature comes from the chemical composition studies done by the AGASA  and the Fly’s Eye  experiments (between 0.1 and 10 EeV). The Fly’s Eye analysis is based on the measurement of the depth where the shower maximum $`X_{\text{max}}`$ is reached. The primary cosmic ray identification by AGASA (or more generally by ground arrays) mainly uses the muon content of the shower at ground level. A conclusion that can be reached from both analyses that the primary composition shifts from dominantly heavy - compatible with iron nuclei - to dominantly light - compatible with protons - (see  for a critical review), even though discrepancies remain about the rate at which the change occurs.

If this interpretation is to be believed (i.e. that the highest energy cosmic rays are mainly protons) there comes to light a third important fact. Although our knowledge of the galactic and extragalactic magnetic fields is not totally sound, a generally accepted working hypothesis sets the field strengths in the $`\mu `$G range for the galactic disk (with an exponential decrease in the halo) and the nG range (with coherence lengths of about 1 Mpc) in intergalactic spaces . The trajectory of a singly charged ultra-relativistic particle through such fields and over distances limited by the GZK cutoff is then such that its direction as measured on earth would roughly point to its source. Typically the angular deviation of a 100 EeV proton coming from a source at 30 Mpc would be of 2 degrees. Above the GZK cutoff, proton astronomy becomes possible to some extent, since the number of remarkable astrophysical objects inside a box of a few degrees and within a distance of a few tens of Mpc is quite limited.

A succint statement on the status of the highest energy part of the cosmic ray spectrum would be that our understanding of the origin of these cosmic rays becomes worse and worse as we go higher in energy. Due to the exponentially decreasing incident cosmic ray flux, the data around the ‘ankle’ and above (roughly energies larger than $`10^{18}`$ eV or 1 EeV) come from a small number of large-aperture ground based detectors. Two types of detection techniques are used in this energy range. The first consists of ground arrays such as Haverah Park (United Kingdom) , Yakutsk (Russia)  and AGASA (Japan) , to which one should add the smaller Volcano Ranch (USA) array  which detected the first air shower event to reach the symbolic limit of 100 EeV. The second technique, namely that of the fluorescence telescopes, is used in the Fly’s Eye  and the more recent HiRes  detectors, both in the state of Utah (USA).

The UHECR spectrum shape obtained by grouping all the available data points in a single figure is somewhat blurred because of the normalisation problems between different experiments. However the general trends are those clearly visible on figure 4. On this figure, where the AGASA data alone are plotted, the energy spectrum is multiplied by $`E^3`$ so that the part below the EeV energies becomes flat. One can see the ‘ankle’ structure: a steepening around the EeV and then a region where the GZK cutoff is expected and shown by the dashed line which indicates the spectrum shape in a scenario where the sources are cosmologically distributed. The ultimate data points come from very few events hence their large error bars. However, the apparent deviation of the events above 100 EeV from the model with cutoff is confirmed if one includes the 13 events detected by the other experiments (of which 7 events are claimed by the HiRes detector and not yet published).

The UHECR events constitute a puzzle, if not an enigma. Many astrophysical processes have been advocated in the past as being possible acceleration mechanisms capable of imparting a macroscopic energy to a microscopic particle (the most energetic cosmic ray ever detected has an energy of 50 joules!): active galactic nuclei, lobes of powerful radio-galaxies, young neutron stars, gamma ray bursts and so on (see e.g.  for a recent review). If all parameters related to the energy and chemical composition are taken into account - acceleration, energy losses at source, propagation, detection - one has to admit that none of the proposed scenarios seems fully convincing up to now. One has to keep in mind that because of the GZK cutoff, the putative sources need to be quite close and therefore should be visible by some counterpart in the direction of the highest energy incident cosmic rays. None of the analyses with the available data shows any strong correlation with known nearby point sources, small or large scale structures (see e.g. the AGASA analysis ). However, this conclusion is challenged by a recent analysis  on the 13 highest energy cosmic rays. The authors propose a galactic wind model for the local magnetic fields and show that the observed cosmic rays can be back-traced to within 20 of the active galaxy M87 in the Virgo cluster (about 20 Mpc away). The only extra assumption they have to concede is that the two cosmic rays with the highest energies (200 and 320 EeV) are He nuclei instead of being protons. If confirmed by larger statistics from future data, this is a very exciting result and would open new windows not only in the field of astrophysics but also in particle physics: we would have a gigantic accelerator at hand reaching energies orders of magnitude higher than any conceivable man-made machine.

If it so happens that future studies exclude the “conventional” astrophysical mechanisms as being the source of the UHECR, one would then need to consider a second family of theories proposed as a possible explanation, namely the so-called “top-down” processes. Most of those study the possibility that the UHECR would be the decay products of some super-heavy X-particle whose mass is in the Grand-Unification range, i.e. around $`10^{25}`$ eV, produced during some phase-transition period of the early universe. The models differ mainly in their attempts to explain the density of the X-particles necessary to fit the observed UHECR flux and their survival from their production some $`10^{35}`$ s after the Big-Bang until recent periods when their disintegration is supposed to occur. In a short review such as the present article, it is impossible to even list the various models which tackle with these thrilling issues (for a very complete review, see ) but we should mention that such models all have quite specific features and experimental signatures (spectrum shape and chemical composition) which make them not impossible to distinguish from the astrophysical (“bottom-up”) mechanisms, provided ongoing and future experiments in the field increase the available (scarce) UHECR data by some orders of magnitude.

Actually statistics are the sinews of war in the search for answers to so many open questions in the field. This can be provided only by the next generation detectors which will provide the huge apertures needed. The next one will be the Auger Observatory  with its 14,000 km2 sr aperture over two sites (one in each hemisphere). Once completed, it is expected to detect some 60 to 100 events per year above 100 EeV, and one hundred times more above 10 EeV. Figure 5 shows the layout of the southern observatory whose construction begins this year by the installation of a “prototype” array of 55 km2 and one fluorescence telescope, near the small town of Malargüe in the province of Mendoza, Argentina. *In fine* the site will be equipped with 1600 detector stations (12 m3 tanks filled with water detecting the Cherenkov light produced by the secondary shower particles) distributed on a grid with 1.5 km spacing. Four “eyes” (a total of 33 telescopes), three of them at the periphery and one at the centre, will view the 3000 km2 of the site and detect the giant showers through the fluorescence they generate in the atmosphere during clear moonless nights. This setup will have the unique advantage of being a “hybrid” detector, combining the two aforementioned detection techniques. The surface array will detect air showers with energies in excess of 10 EeV with full efficiency and a 100% duty cycle. A sub-sample of some 10% of the total number of events will be simultaneously observed by the fluorescence telescopes, hence providing the possibility to cross-calibrate both methods and yield an unprecented quality for the identification of the primaries and the measurement of energy and direction.

If in a few years it is shown that the spectral cutoff goes even beyond the reach of the Auger Observatory (e.g. $`10^{21}`$ eV or above) the next generation detectors will no doubt be air-borne as is envisaged with the OWL/Airwatch project , fluorescence detectors installed on satellites.


text:
# Succinct quantum proofs for properties of finite groupsResearch partially supported by Canada’s NSERC.

## 1 Introduction

There are several equivalent ways to view nondeterminism in the classical setting that apparently yield inequivalent notions in the quantum setting. Two such ways are as follows.

First, we may view a nondeterministic process as a probabilistic process, and consider whether the resulting process has zero or nonzero probability of success. Along these lines, Adleman, DeMarrais, and Huang  and Fenner, Green, Homer, and Pruim  have defined QNP to be the class of languages $`L`$ for which there exist polynomial time quantum Turing machines that accept with nonzero probability if and only if the input is in $`L`$. This class coincides with the counting class $`\mathrm{co}\mathrm{C}_=\mathrm{P}`$ . This notion of quantum nondeterminism has also been investigated recently in the context of communication complexity and query complexity by de Wolf .

Second, we way view nondeterminism as it relates to verification. A common way to view NP is that NP is the class of languages consisting of those strings for which there exist polynomial-length proofs of membership that can be checked in polynomial time, and one may extend this viewpoint to the quantum setting in several ways. For instance, we may consider quantum proofs (or quantum certificates), which are quantum states that certify membership of strings in given languages, or we may consider ordinary (classical) certificates that are checked by polynomial-time quantum computers. In each case we may consider various constraints on the error allowed by the quantum checking procedure.

In this paper, we investigate the second way of viewing nondeterminism in the quantum setting. We will restrict our attention to the case where certificates may be quantum and the polynomial-time quantum verification procedure may operate with (two-sided) bounded error. Thus, this version of “quantum NP” represents the quantum generalization of the class MA (based on the Arthur-Merlin games of Babai ), and for this reason we will call the resulting class QMA. This notion of quantum nondeterminism was apparently first discussed by Knill , and was later studied by Kitaev  (who instead referred to the class we call QMA as BQNP). Kitaev proved $`\mathrm{QMA}\mathrm{P}^{\mathrm{\#}P}`$, and we claim that the technique based on GapP functions used by Fortnow and Rogers  to prove $`\mathrm{BQP}\mathrm{PP}`$ may be extended to prove $`\mathrm{QMA}\mathrm{PP}`$ (this result was obtained jointly by A. Kitaev and the present author). One may also view QMA as a class that results by considering (two-sided error) one-message quantum interactive proof systems , in which there is really no interaction since only one message is sent.

Our main focus is on the power of QMA in the context of black-box groups. Of particular interest to us is the Group Non-Membership problem, which may be stated as follows:

Group Non-Membership (GNM)

| Instance: | Group elements $`g_1,\mathrm{},g_k`$ and $`h`$ in some finite group $`G`$. |
| --- | --- |
| Question: | Is $`h`$ outside the group generated by $`g_1,\mathrm{},g_k`$ (i.e., is $`hg_1,\mathrm{},g_k`$)? |

The statement of this problem mentions neither the particular representation of group elements used nor the underlying group or groups. While it is interesting to consider this problem in the case that the group elements are represented in some natural way (e.g., by invertible matrices over a finite field), we will consider the case that group elements are uniquely represented in some arbitrary way by strings, and that we have at our disposal some oracle $`B`$ (known as a group oracle) that performs group operations for us (with each operation requiring a single step). In this setting, we assume nothing can be learned about group elements by examining their representative strings except whether or not two elements are distinct. For each $`n`$ there will correspond a group consisting of some subset of the length $`n`$ strings; this group will be denoted $`B_n`$ and is called a black-box group. Black-box groups were first considered by Babai and Szemerédi , and have since been studied in several works . Further details regarding black-box groups will be discussed in the next section.

For a given group oracle $`B`$ we let $`\mathrm{GNM}(B)`$ be the language consisting of all positive instances of the Group Non-Membership problem relative to $`B`$. By the Reachability Theorem of Babai and Szemerédi  it follows that $`\mathrm{GNM}(B)\mathrm{co}\mathrm{NP}^B`$ for any group oracle $`B`$. Furthermore, Babai  proved that $`\mathrm{GNM}(B)\mathrm{AM}^B`$ for any group oracle $`B`$, while there exists choices for the group oracle $`B`$ such that $`\mathrm{GNM}(B)\mathrm{BPP}^B`$ and $`\mathrm{GNM}(B)\mathrm{NP}^B`$. In Section 4 we extend this result slightly by constructing a group oracle $`B`$ such that $`\mathrm{GNM}(B)\mathrm{MA}^B`$.

In contrast to the fact that $`\mathrm{GNM}(B)\mathrm{MA}^B`$ for some choices of the group oracle $`B`$, we prove that $`\mathrm{GNM}(B)\mathrm{QMA}^B`$ for any group oracle $`B`$. Thus, for any black-box group $`G`$ and elements $`h,g_1\mathrm{},g_kG`$, there exists a polynomial-length quantum proof that $`h`$ is not in the group generated by $`g_1,\mathrm{},g_k`$. This fact is proved in Section 3. Naturally, a similar result holds in case group elements are represented in any way that allows the group oracle to be replaced by a polynomial-time computation, such as matrix groups over a finite field. For such groups it is not known if GNM is in MA, although Babai  conjectures that in fact $`\mathrm{GNM}\mathrm{NP}\mathrm{co}\mathrm{NP}`$ in this restricted case. This conjecture is based on presently unproved conjectures relating to the classification of finite simple groups. A polynomial-time algorithm is known for permutation groups .

In certain limited cases it is possible to solve GNM in quantum polynomial time without the help of a certificate, such as when $`k=1`$ in the statement of the GNM problem. The oracle $`B`$ we construct in Section 4 in fact puts $`\mathrm{GNM}(B)`$ outside of $`\mathrm{MA}^B`$ for this special case, and therefore gives an oracle relative to which $`\mathrm{BQP}\mathrm{MA}`$. Bernstein and Vazirani  claimed a stronger result (specifically that there exists an oracle relative to which $`\mathrm{EQP}\mathrm{MA}`$), but the proof has not yet appeared.

Quantum proofs for group non-membership may be used to devise quantum proofs for other group problems. Several such problems, include the problem of testing whether a given number divides the order of a group, testing that one group is a proper subgroup of another, and testing that a given group is not a simple group, are mentioned in Section 5.

## 2 Definitions

In this section we define the class QMA and discuss black-box groups in the context of quantum circuits. We assume the reader is familiar with the quantum circuit model, and with basic notions from complexity theory and group theory. For a detailed discussion of quantum circuits see Kitaev . (Readers not familiar with quantum computation may find the more introductory papers of Berthiaume  and Cleve  helpful as well.) See, for example, Balcázar, Díaz, and Gabarró  for background on complexity theory and, for example, Isaacs  for background on group theory.

Let us begin by making clear our assumptions regarding uniformity of quantum circuits. A family $`\{Q_x\}`$ of quantum circuits is said to be polynomial-time uniformly generated if there exists a deterministic procedure that, on input $`x`$, outputs a description of $`Q_x`$ and runs in time polynomial in $`|x|`$. (For simplicity we assume all input strings are over the alphabet $`\mathrm{\Sigma }=\{0,1\}`$.) It is assumed that the circuits in such a family are composed of gates in some reasonable, universal, finite set of quantum gates (for instance, the standard basis discussed by Kitaev  or the Shor basis discussed by Boykin, et. al. ). In addition the circuits may include oracle gates as discussed below. Furthermore, it is assumed that the size of any circuit in such a family is not more than the length of that circuit’s description (i.e., no compact descriptions of large circuits are allowed), so that $`Q_x`$ must have size polynomial in $`|x|`$. To make matters simple when dealing with oracle gates below, we define the size of a quantum circuit to be the number of gates in the circuit plus the number of qubits upon which the circuit acts.

When we describe quantum circuits, we do so in a high-level manner that may suggest that measurements are taking place at various times during the circuit’s computation; such measurements, however, do not occur and are assumed to be simulated in the sense described by Aharonov, Kitaev, and Nisan .

For each circuit $`Q_x`$, some number of the qubits upon which $`Q_x`$ acts are specified as input qubits, and all other qubits are ancilla qubits. The input qubits are assumed to be initialized in some specified input state $`|\psi `$, while all ancilla qubits are initialized to the $`|0`$ state. One of the qubits is also specified as the output qubit and is assumed to be observed after the circuit has been applied. The probability that $`Q_x`$ accepts $`|\psi `$ is defined to be the probability that an observation of the output qubit (in the $`\{|0,|1\}`$ basis) yields 1, given that the input qubits are initially set to $`|\psi `$.

We now define the class QMA as follows.

###### Definition 1

A language $`A\mathrm{\Sigma }^{}`$ is in QMA if there exists a polynomial-time uniformly generated family of quantum circuits $`\{Q_x\}_{x\mathrm{\Sigma }^{}}`$ such that (i) if $`xA`$ then there exists a quantum state $`|\psi `$ such that $`\mathrm{Pr}[Q_x\text{ accepts }|\psi ]>2/3`$, and (ii) if $`xA`$ then for all quantum states $`|\psi `$, $`\mathrm{Pr}[Q_x\text{ accepts }|\psi ]<1/3`$.

Note that the circuit $`Q_x`$ does not take $`x`$ as an input, but rather the procedure that produces the description of $`Q_x`$ takes $`x`$ as input—the input $`|\psi `$ to a given circuit $`Q_x`$ corresponds to a quantum certificate that purportedly proves the property that $`xA`$. Information regarding $`x`$ may of course be “hard-coded” into $`Q_x`$, however, which eliminates the need for inputting $`x`$. It should be noted that the class QMA would not change if the definition was such that there were just one circuit for each input length (rather than each input), with each circuit taking $`|\psi `$ and $`x`$ as input (as would be the case for the more standard notion of circuit uniformity).

Similar to classical bounded error classes, the bounds of 1/3 and 2/3 in the definition of QMA may be replaced by $`2^{p(|x|)}`$ and $`12^{p(|x|)}`$, respectively, for any polynomial $`p`$. In the other direction, the bounds of 1/3 and 2/3 may be replaced by functions $`b(|x|)`$ and $`a(|x|)`$, respectively, for $`a,b:^+[0,1]`$ such that (i) $`a`$ and $`b`$ are computable in polynomial time, and (ii) $`a(|x|)b(|x|)1/p(|x|)`$ for some polynomial $`p`$. In both cases, this follows from the fact that for any polynomial $`q`$ we may run $`q(|x|)`$ independent copies of a given verification procedure on a “compound certificate” consisting of $`q(|x|)`$ certificates for the independent copies, and make a decision to accept or reject depending on the proportion of the individual copies that accept appropriately. A simple analysis reveals that entanglement among the individual certificates can yield no increase in the probability of acceptance as compared to the situation in which the certificates are not entangled, and that the probability of error is bounded by the tail of a binomial series as expected.

Next we will discuss black-box groups. Here, we will consider a variation on black-box groups that is appropriate for the quantum circuit model. A group oracle $`B`$ is a family of bijections $`\{B_n\}`$ with each member having the form $`B_n:\mathrm{\Sigma }^{2n+2}\mathrm{\Sigma }^{2n+2}`$ and satisfying constraints to be discussed shortly. We interpret the input and output of each $`B_n`$ as consisting of four parts: a control bit, an error bit, and two $`n`$-bit strings representing group elements. This situation is pictured in Figure 1.

Associated with each $`B_n`$ is a group denoted $`G(B_n)`$ whose elements form some subset of $`\mathrm{\Sigma }^n`$ and whose group structure is determined by the function $`B_n`$. If $`x,yG(B_n)`$ then $`yx=z`$ for the unique value of $`z`$ that satisfies $`B(0,b,x,y)=(0,b,x,z)`$ for each $`b\mathrm{\Sigma }`$. Similarly, if $`x,yG(B_n)`$ then $`yx^1=z`$ for the unique value of $`z`$ that satisfies $`B(1,b,x,y)=(1,b,x,z)`$. The first input bit (the control bit) thus determines whether $`y`$ is multiplied (on the right) by $`x`$ or by $`x^1`$. Whenever we have $`xG(B_n)`$ or $`yG(B_n)`$, then it must be the case that $`B(c,b,x,y)=(c,\neg b,x,y)`$ for each $`b,c\mathrm{\Sigma }`$, i.e., the error bit $`b`$ is negated to indicate that the inputs were not valid group elements. Naturally, the constraint that must be obeyed by each $`B_n`$ in order for $`B=\{B_n\}`$ to be considered a group oracle is that there must exist a family of underlying groups $`\{G_n\}`$ along with encodings $`\{f_n\}`$ (each $`f_n:G_n\mathrm{\Sigma }^n`$ one-to-one and satisfying $`f_n(G_n)=G(B_n)`$) that yields the above structure. Each group $`G(B_n)`$, and more generally any subgroup of $`G(B_n)`$ given by a list of generators, is known as a black-box group.

For a given group oracle $`B`$ each $`B_n`$ is invertible, and may therefore be viewed as a $`(2n+2)`$-qubit quantum gate as suggested by Figure 1. When we say that a polynomial-time uniformly generated family of quantum circuits has access to group oracle $`B`$, we mean that the circuits in the family may, in addition to the standard gates mentioned previously, be composed of any of the gates in the collection $`\{B_n\}`$. Note that any quantum circuit containing a $`B_n`$ gate must have size $`\mathrm{\Omega }(n)`$.

## 3 Verification of non-membership

In this section we prove that the Group Non-Membership problem is in QMA for an arbitrary group oracle $`B`$. Before giving the technical proof, we will discuss informally the basic idea of the proof.

Suppose group elements $`g_1,\mathrm{},g_k`$ and $`h`$ are given, and let us write $`H=g_1,\mathrm{},g_k`$. Consider the state $`|H|^{1/2}_{gH}|g`$, and assume that this state is contained in a quantum register $`𝐑`$. In general, given any finite set $`A`$ we will let $`|A`$ denote the state $`|A|^{1/2}_{aA}|a`$, so that we may say that $`𝐑`$ is in state $`|H`$. In addition let $`𝐁`$ be a register consisting of a single qubit, and suppose $`𝐁`$ is initialized to state $`(|0+|1)/\sqrt{2}`$. Assuming we have a gate that performs group operations as discussed in the previous section, we may built a quantum circuit acting on $`𝐑`$ and $`𝐁`$ that effectively acts as a controlled-multiply-by-$`h`$ operation on $`𝐑`$, where $`𝐁`$ is the control. If this operation is performed, we may express the resulting state of the pair $`(𝐁,𝐑)`$ as $`(|0|H+|1|Hh)/\sqrt{2}`$. Now perform a Hadamard transform on $`𝐁`$ to yield the state

$$\frac{1}{2}|0(|H+|Hh)+\frac{1}{2}|1(|H|Hh).$$

At this point, observing $`𝐁`$ in the $`\{|0,|1\}`$ basis yields 1 with probability $`p=(|H|Hh)/2^2`$. In case $`hH`$ we have $`|H=|Hh`$, and so $`p=0`$; in case $`hH`$ we have that $`|H`$ and $`|Hh`$ are orthogonal, and so $`p=1/2`$. Thus, given several copies of the state $`|H`$ one may determine with very high probability whether or not $`hH`$.

Unfortunately, the state $`|H`$ may be difficult to construct in some cases, but it may be given as a quantum certificate. Naturally we may not assume that a given certificate $`|\psi `$ coincides with $`|H`$, so this must be verified before the above test is performed. In fact, it is not necessary to check that $`|\psi =|H`$, but only that $`|\psi `$ is invariant under right multiplication by elements of $`H`$. Our technique to do this is as follows. Consider a (classical) randomized procedure for generating elements of $`H`$ uniformly (for now we assume this is possible without error—we will take errors into account in the proof below). We may modify such a probabilistic process to make it quantum by simulating the act of choosing any random number in some given range $`\{0,\mathrm{},N1\}`$ by using a quantum transformation $`Q_N`$ satisfying $`Q_N|0=N^{1/2}_{a=0}^{N1}|a`$, and simulating the entire process reversibly. (To do this, assume all random choices are made first, and that the remaining part of the process is deterministic and hence can be simulated reversibly.) Let $`F`$ denote the resulting quantum transformation. It will not be the case that $`F`$ produces $`|H`$, but rather we will have

$$F:|0\frac{1}{\sqrt{|H|}}\underset{gH}{}|g|\mathrm{garbage}(g)$$

for $`|\mathrm{garbage}(g)`$ denoting some arbitrary unit vector representing whatever is left over from this process (for instance, copies of the simulated random numbers yielding the random choice of $`g`$ in superposition). Now, to check that the state contained in $`𝐑`$, which purportedly contains $`|H`$, is invariant under right multiplication by elements of $`H`$, we do the following: (i) apply $`F`$ to some register $`𝐒`$ that is initially in the state $`|0`$, (ii) multiply (on the right) the contents of $`𝐑`$ by the “random” group element contained in $`𝐒`$, (iii) apply $`F^{}`$ to $`𝐒`$, and (iv) observe $`𝐒`$. If $`𝐑`$ was invariant under multiplication by elements of $`H`$, then $`𝐒`$ will revert back to state $`|0`$ with certainty, while if not there will be some probability that the observation of $`𝐒`$ yields some other result (indicating that this certificate should be rejected). Under the assumption that the observation of $`𝐒`$ does yield 0, however, the state of $`𝐑`$ will in fact be changed (by quantum magic!) to one that is invariant under right multiplication by elements in $`H`$. At this point, $`𝐑`$ will be suitable for the first test that determines whether $`hH`$.

Before proceeding to the formal proof, we mention the following theorem due to Babai  that will be used in the proof. The theorem essentially states that elements in a given black-box group can be randomly generated in such a way that the resulting distribution is very close to uniform.

###### Theorem 1 (Babai)

For any group oracle $`B`$ there exists a randomized procedure $`𝒫`$ acting as follows. On input $`g_1,\mathrm{},g_kG(B_n)`$ and $`ϵ>0`$, $`𝒫`$ outputs an element of $`H=g_1,\mathrm{},g_k`$ in time polynomial in $`n+\mathrm{log}1/ϵ`$ such that each $`gH`$ is output with probability in the range $`(1/|H|ϵ,1/|H|+ϵ)`$.

This is in fact a weaker result than the one proved by Babai, but it is sufficient for our needs.

Now we are prepared to state and prove the main result of this section.

###### Theorem 2

$`\mathrm{GNM}(B)\mathrm{QMA}^B`$ for any group oracle $`B`$.

Proof. As above, given any set $`A`$, we write $`|A`$ to denote the uniform superposition over elements of $`A`$, i.e., $`|A=|A|^{1/2}_{aA}|a`$. Let $`g_1,\mathrm{},g_k`$ and $`h`$ denote input group elements of length $`n`$, let $`H=g_1,\mathrm{},g_k`$, and consider the procedure described in Figure 2.

Assume first that $`hH`$. In this case we must prove that there exists a certificate $`|\psi `$ causing the procedure to accept with high probability. The certificate will be $`|H`$. The verification procedure first performs transformation $`F`$ on $`𝐒`$, which was initialized to $`|0`$ at the start of the procedure. The state of the pair of registers $`(𝐑,𝐒)`$ is now

$$|H\underset{gH}{}\alpha _g(|g|\mathrm{garbage}(g)).$$
(1)
The contents of register $`𝐑`$ is multiplied by the group element contained in $`𝐒`$, which has no effect on the state in (1) following from the fact that $`|H`$ is invariant under multiplication by any element $`gH`$. Now the inverse of transformation $`F`$ is applied, which returns $`𝐒`$ to the state $`|0`$ with certainty. The probability that the verification procedure rejects in step 1 is therefore 0. Now step 2 is performed. After preparing register $`𝐁`$ and performing the controlled-multiply-by-$`h`$ operation, the state of the pair $`(𝐁,𝐑)`$ is $`(|0|H+|1|Hh)/\sqrt{2}`$. A Hadamard transform is performed on $`𝐁`$, producing the state

$$\frac{1}{2}|0(|H+|Hh)+\frac{1}{2}|1(|H|Hh).$$

Under the assumption $`hH`$, we have that $`|H`$ and $`|Hh`$ are orthogonal, and consequently the probability of acceptance is $`(|H|Hh)/2^2=1/2`$.

Now suppose $`hH`$ and let $`|\psi `$ denote the initial state of register $`𝐑`$. In this case our goal is to bound the probability of acceptance. Let us write

$$|\psi =\underset{xG(B_n)}{}\beta _x|x+|\gamma $$

for $`|\gamma \mathrm{span}\{|x:xG(B_n)\}`$ denoting the “invalid” portion of $`|\psi `$. The verification procedure first checks that $`𝐑`$ contains a superposition over valid elements of $`G(B_n)`$, which has the effect of projecting the state of $`𝐑`$ to $`_{xG(B_n)}\beta _x|x`$ (renormalized) in case this test does not result in rejection. As we are interested in bounding the overall (unconditional) probability of accepting, however, we need not renormalize this state. Transformation $`F`$ is performed on $`𝐒`$, and the group element contained in $`𝐒`$ is multiplied to the contents of $`𝐑`$, producing state

$$\underset{xG(B_n)}{}\underset{gH}{}\alpha _g\beta _x|xg|g|\mathrm{garbage}(g)$$

in registers $`(𝐑,𝐒)`$. Now $`F^{}`$ is applied to $`𝐒`$ and the verification procedure rejects if $`𝐒`$ has not been returned to it’s initial 0 value. Under the assumption that an observation of $`𝐒`$ reveals 0 (which is necessary if the procedure accepts), the state of register $`𝐑`$ becomes

$$\underset{xG(B_n)}{}\underset{gH}{}\alpha _g\beta _x|xg0|F^{}(|g|\mathrm{garbage}(g))=\underset{xG(B_n)}{}\underset{gH}{}|\alpha _g|^2\beta _x|xg$$

(where again we do not renormalize in order to calculate the unconditional probability of acceptance). Now step 2 is performed. After the controlled-multiply-by-$`h`$ and Hadamard operations have been performed, the state of the pair $`(𝐁,𝐑)`$ will be

$$\frac{1}{2}|0\underset{xG(B_n)}{}\underset{gH}{}\left(|\alpha _g|^2\beta _x|xg+|\alpha _g|^2\beta _x|xgh\right)+\frac{1}{2}|1\underset{xG(B_n)}{}\underset{gH}{}\left(|\alpha _g|^2\beta _x|xg|\alpha _g|^2\beta _x|xgh\right).$$

The probability of acceptance is therefore

$$\frac{1}{4}\underset{xG(B_n)}{}\underset{gH}{}\left(|\alpha _g|^2\beta _x|xg|\alpha _g|^2\beta _x|xgh\right)^2.$$
(2)
Under the assumption that $`hH`$, we have that $`xgh`$ and $`xg`$ range over the same set as $`g`$ ranges over $`H`$. Thus we may rewrite (2) as

$$\frac{1}{4}\underset{xG(B_n)}{}\underset{gH}{}\beta _x\left(|\alpha _g|^2|\alpha _{gh^1}|^2\right)|xg^2.$$
(3)
By the triangle inequality, we see that (3) is at most

$$\frac{1}{4}\left(\underset{gH}{}\left(|\alpha _g|^2|\alpha _{gh^1}|^2\right)\underset{xG(B_n)}{}\beta _x|xg\right)^22^{2n}.$$

Thus we have that the verification procedure accepts with exponentially small probability.

The definition of QMA requires that positive instances be accepted with probability at least 2/3 and negative instances to be accepted with probability at most 1/3. Thus, we must address the fact that although our verification procedure accepts with exponentially small probability for all certificates on negative instances, the probability of acceptance is only guaranteed to be 1/2 for positive instances. As discussed in Section 2, this may be remedied by running several copies of the verification procedure in parallel and deciding to accept or reject depending on the number of parallel executions that accept. In the present case we may achieve exponentially small probability of error by running a polynomial number of copies of the above verification procedure on a compound certificate and accepting if and only if at least one of the copies accepts.

## 4 Oracle separations

In this section we discuss oracle separations regarding MA, QMA, and BQP. First, we prove that there exists a group oracle $`B`$ relative to which the Group Non-Membership problem is not contained in $`\mathrm{MA}`$, and thus $`\mathrm{MA}^B\mathrm{QMA}^B`$. Our proof follows the same general ideas used by Babai  to prove $`\mathrm{GNM}\mathrm{NP}`$ and $`\mathrm{GNM}\mathrm{BPP}`$ for some group oracles. We then identify a restricted version of the Group Non-Membership problem, which we call the 2-Element Group Non-Membership problem, that in fact is contained in BQP but still lies outside of MA relative to the group oracle $`B`$. Thus we have an oracle separating BQP and MA. A stronger result was claimed by Bernstein and Vazirani , but their proof has not yet appeared—they claimed the existence of an oracle relative to which $`\mathrm{EQP}`$ is not contained in $`\mathrm{MA}`$.

The oracle separations we prove rely on a strong amplification property possessed by MA, which is that the probability of error can be made much smaller than the reciprocal of the number of possible certificates for each input length. With this in mind, we take the following as our definition of $`\mathrm{MA}^B`$:

###### Definition 2

For a given group oracle $`B`$, a language $`A`$ is in $`\mathrm{MA}^B`$ if there exists a predicate $`R`$, computable in polynomial time by a deterministic Turing machine with access to the group oracle $`B`$, and polynomials $`q`$ and $`r`$, such that for every $`x\mathrm{\Sigma }^{}`$ we have:

* If $`xA`$, then there exists $`y\mathrm{\Sigma }^{q(|x|)}`$ such that

$$\left|\left\{z\mathrm{\Sigma }^{r(|x|)}\right|R(x,y,z)=1\}\right|=\mathrm{\hspace{0.25em}2}^{r(|x|)}.$$
* If $`xA`$, then for all $`y\mathrm{\Sigma }^{q(|x|)}`$,

$$\left|\left\{z\mathrm{\Sigma }^{r(|x|)}\right|R(x,y,z)=1\}\right|<\mathrm{\hspace{0.25em}2}^{2q(|x|)}2^{r(|x|)}.$$

This definition also includes the fact that the error can be made one-sided without changing the resulting class (see, for instance, Zachos )—a property that we do not know holds for QMA. This fact is not essential in our proof, but has the advantage of simplifying our analysis.

###### Theorem 3

There exists a group oracle $`B`$ for which we have $`\mathrm{GNM}(B)\mathrm{MA}^B`$.

Proof. For each $`n4`$, let $`p(n)`$ be a prime number satisfying $`2^{n2}<p(n)^2<2^n`$. Existence of such a sequence of primes follows from Bertrand’s Postulate, first proved by Chebyshev (see, for instance, Rosser and Schoenfeld ). Let $`[p(n)^2]`$ denote the set $`\{1,\mathrm{},p(n)^2\}`$, and for fixed $`n`$ identify each element of $`[p(n)^2]`$ with its representation as an $`n`$-bit string in binary. Let $`(n)`$ denote the set of one-to-one functions of the form $`f:[p(n)^2]_{p(n)}\times _{p(n)}`$, and define

$`_1(n)`$ $`=`$ $`\left\{f(n)\right|f(1)=(1,0)\text{and}f(2)=(0,1)\},`$
$`_0(n)`$ $`=`$ $`\{f(n)|f(1)=(1,0)\text{and}f(2)=(a,0)\text{for some }a\{2,\mathrm{},p(n)1\}\}.`$
We have $`|_0(n)|=(p(n)2)|_1(n)|`$. Associated with each $`f(n)`$ is a black-box group isomorphic to $`_{p(n)}\times _{p(n)}`$ that labels each $`(\alpha ,\beta )_{p(n)}\times _{p(n)}`$ with the $`n`$-bit string $`f^1(\alpha ,\beta )`$. When $`n`$ is fixed, or understood from context, we will simply write $`p`$, $`_0`$, $`_1`$, etc., to mean $`p(n)`$, $`_0(n)`$, $`_1(n)`$, etc.

We will restrict our attention to the case where the input to the GNM problem consists of the pair of $`n`$-bit strings representing labels $`1`$ and $`2`$ in binary for some $`n`$—we will write this pair as $`(1,2)_n`$ in order to stress the dependence on $`n`$. Furthermore, we also restrict our attention to the case that the group oracle is associated with some $`f_1(n)_0(n)`$ for each $`n`$ as described previously. For fixed $`n`$, if the group in question is associated with $`f_1`$, then $`f(2)f(1)`$, and so $`(1,2)_n`$ is a positive instance of GNM. If the group is associated with $`f_0`$, then $`f(2)f(1)`$, and so $`(1,2)_n`$ is a negative instance of GNM.

Below we will diagonalize over all polynomial time oracle Turing machines in order to prove the existence of $`B`$ as in the statement of the theorem. First, let us consider an arbitrary polynomial-time deterministic oracle Turing machine $`M`$, and let $`q`$, $`r`$, and $`t`$ be strictly increasing polynomials such that the following holds: for any $`x\mathrm{\Sigma }^{}`$, $`y\mathrm{\Sigma }^{q(|x|)}`$, and $`z\mathrm{\Sigma }^{r(|x|)}`$, $`M`$ runs in time $`t(|x|)`$ on input $`(x,y,z)`$ and any group oracle $`B`$. (Here, $`x`$, $`y`$, and $`z`$ are as in the definition of MA, i.e., $`x`$ corresponds to the input, $`y`$ is a certificate, and $`z`$ is treated as a sequence of random bits.) As mentioned above, we are interested in the case where $`x=(1,2)_n`$ for some $`n`$. Write $`m=|x|`$ for such a choice of $`x`$, and for simplicity assume our encoding of pairs of strings is such that $`2nm4n`$. At this point we will fix $`n`$ sufficiently large such that $`8t(4n)^2<2^{n/2}`$ (and thus $`t(m)^2/p(n)<1/4`$). Let $`B`$ be an arbitrary group oracle, and for any $`f`$ let us write $`B_f`$ to denote the new group oracle obtained by changing the behavior of $`B`$ on elements of length $`n`$ to be in accordance with $`f`$, as described above. Finally, let $`M(B_f,y,z)`$ denote 1 if $`M`$ accepts $`(x,y,z)`$ given oracle $`B_f`$, and let $`M(B_f,y,z)`$ denote 0 otherwise. We claim that the following inequality holds for every $`y\mathrm{\Sigma }^{q(m)}`$ and $`z\mathrm{\Sigma }^{r(m)}`$:

$$\left|\left\{g_0\right|M(B_g,y,z)=1\}\right|\left(pt(m)^2\right)\left|\left\{f_1\right|M(B_f,y,z)=1\}\right|.$$
(4)
The proof of this inequality is the main technical part of the proof of Theorem 3, and so we postpone this part momentarily—for now assume that it is proved.

Suppose now that for every $`f_1`$ there exists a certificate $`y\mathrm{\Sigma }^{q(m)}`$ such that $`M(B_f,y,z)=1`$ for every $`z\mathrm{\Sigma }^{r(m)}`$ (which must be the case if $`M`$ is really a valid machine for solving the Group Non-Membership problem with respect to an arbitrary oracle). Since there are only $`2^{q(m)}`$ possible certificates, we conclude that one of the certificates must work for many different oracles, i.e., there exists some fixed $`y`$ such that for at least $`2^{q(m)}|_1|`$ choices of $`f_1`$ we have $`M(B_f,y,z)=1`$ for every $`z\mathrm{\Sigma }^{r(m)}`$. This implies

$$\underset{z\mathrm{\Sigma }^{r(m)}}{}\left|\left\{f_1\right|M(B_f,y,z)=1\}\right|\mathrm{\hspace{0.25em}2}^{q(m)}|_1|\mathrm{\hspace{0.17em}2}^{r(m)}.$$

By (4) we therefore have

$`{\displaystyle \underset{g_0}{}}\left|\left\{z\mathrm{\Sigma }^{r(m)}\right|M(B_g,y,z)=1\}\right|`$ $`=`$ $`{\displaystyle \underset{z\mathrm{\Sigma }^{r(m)}}{}}\left|\left\{g_0\right|M(B_g,y,z)=1\}\right|`$
$``$ $`(pt(m)^2)\mathrm{\hspace{0.17em}2}^{q(m)}|_1|\mathrm{\hspace{0.17em}2}^{r(m)}.`$
Therefore, there must exist $`g_0`$ such that

$`\left|\left\{z\mathrm{\Sigma }^{r(m)}\right|M(B_g,y,z)=1\}\right|`$ $``$ $`{\displaystyle \frac{(pt(m)^2)\mathrm{\hspace{0.17em}2}^{q(m)}|_1|\mathrm{\hspace{0.17em}2}^{r(m)}}{|_0|}}`$
$`>`$ $`2^{2q(m)}2^{r(m)}.`$
From this we conclude that for any polynomial time oracle Turing machine $`M`$ and group oracle $`B`$, there exists an integer $`n`$ such that by modifying $`B`$ only on elements of length $`n`$ it is possible to make $`M`$ an invalid machine for the GNM problem; either there exists $`f_1(n)`$ such that no certificate causes $`M`$ to accept $`(1,2)_n`$ given group oracle $`B_f`$ with certainty, or there exists $`g_0(n)`$ such that some certificate causes $`M`$ to accept $`(1,2)_n`$ given group oracle $`B_g`$ with too high a probability.

Now it is routine to prove there exists $`B`$ as in the statement of the theorem by a diagonalization argument. Let $`(M_1,q_1,r_1),(M_2,q_2,r_2),\mathrm{}`$, be an enumeration of all triples consisting of a polynomial-time deterministic oracle Turing machine and a pair of strictly increasing polynomials. Let $`t_1,t_2,\mathrm{}`$ be a sequence of polynomials such that $`M_i`$ runs in time $`t_i(|x|)`$ on each input $`(x,y,z)`$ and any group oracle $`B`$, assuming $`|y|=q_i(|x|)`$ and $`|z|=r_i(|x|)`$, for each $`i`$. Without loss of generality we may assume $`t_{i+1}(m)>t_i(m)`$ for all $`i`$ and $`m`$. We define $`B`$ using a stage construction as follows:

* Set $`B^{(0)}`$ to be an arbitrarily chosen group oracle, and set $`n_0=4`$.
* Choose $`n_i`$ be the smallest integer satisfying $`2n_i>t_{i1}(4n_{i1})`$ and $`8t_i(4n_i)^2<2^{n_i/2}`$, and let $`m_i`$ be the length of the encoding of the pair $`(1,2)_{n_i}`$.

If there exists $`f_1(n_i)`$ such that for all $`y\mathrm{\Sigma }^{q_i(m_i)}`$ we have

$$\left|\left\{z\mathrm{\Sigma }^{r(m_i)}\right|M_i(B_f^{(i1)},y,z)=1\}\right|<\mathrm{\hspace{0.25em}2}^{r(m_i)}$$

then let $`B^{(i)}=B_f^{(i1)}`$ for any such $`f`$. Otherwise, as proved previously, there exists $`g_0(n_i)`$ and $`y\mathrm{\Sigma }^{q_i(m_i)}`$ such that

$$\left|\left\{z\mathrm{\Sigma }^{r(m_i)}\right|M_i(B_g^{(i1)},y,z)=1\}\right|>\mathrm{\hspace{0.25em}2}^{2q(m_i)}2^{r(m_i)}.$$

Set $`B^{(i)}=B_g^{(i1)}`$ for any such $`g`$.

Finally, let $`B`$ be the group oracle that, for each $`i`$, agrees with $`B^{(i)}`$ on all queries regarding elements of length less than $`n_{i+1}`$. (This group oracle is well-defined, since all changes to the oracle on stages subsequent to stage $`i`$ involve only elements of length at least $`n_{i+1}`$.) It is now straightforward to verify that $`\mathrm{GNM}(B)\mathrm{MA}^B`$ by the construction of $`B`$, since no triple $`(M_i,q_i,r_i)`$ can be valid according to Definition 2.

It remains to prove the inequality (4). Define an equivalence relation $`_{y,z}`$ on $`\times `$ for each $`y\mathrm{\Sigma }^{q(m)}`$ and $`z\mathrm{\Sigma }^{r(m)}`$ as follows: $`f_{y,z}g`$ if and only if $`f`$ and $`g`$ induce identical executions of $`M`$ for $`x=(1,2)_n`$, certificate $`y`$, and random bits $`z`$ (i.e., on input $`((1,2)_n,y,z)`$).

Let $`f_1`$, and consider the computation of $`M`$ on input $`((1,2)_n,y,z)`$ given a group oracle specified by $`f`$ on length $`n`$ elements. During this computation, there will be some number $`k`$ of queries to the oracle regarding length $`n`$ elements, which we may express as

$`u_1\pm v_1`$ $`=`$ $`w_1,`$ (5)
$`\mathrm{}`$
$`u_k\pm v_k`$ $`=`$ $`w_k`$
(that is, the $`i`$-th query asks for $`u_i+v_i`$ or $`u_iv_i`$, and the answer given by the oracle is $`w_i`$). Let $`L`$ denote the set $`\{u_1,v_1,w_1,\mathrm{},u_k,v_k,w_k\}`$ (i.e., the distinct length-$`n`$ labels of group elements that either appear in a query or a response), and let $`l`$ denote the size of $`L`$. Without loss of generality assume the labels 1 and 2 are in $`L`$. The above equations specify a $`k\times l`$ matrix $`A`$ with entries in $`\{1,0,1\}`$ in the following straightforward way: the columns of $`A`$ are indexed by the labels in the set $`L`$, and for each $`i=1,\mathrm{},k`$, the $`i`$-th row of $`A`$ only has nonzero entries corresponding to labels $`u_i`$, $`v_i`$, and $`w_i`$. In case the $`i`$th query was $`u_i+v_i=w_i`$, the entries for the columns indexed by $`u_i`$, $`v_i`$, and $`w_i`$ will be $`1`$, $`1`$, and $`1`$, respectively, and in case the $`i`$th query was $`u_iv_i=w_i`$, the entries will be $`1`$, $`1`$, and $`1`$, respectively.

At this point it will be convenient to view $`_p\times _p`$ as being the additive group of the field $`𝔽=GF(p^2)`$ in order to easily apply well-known theorems from linear algebra to our analysis. (Here the specific correspondence between $`_p\times _p`$ and $`𝔽`$ is arbitrary, so long as the additive group structure is preserved.) Note that for any $`g`$ satisfying $`f_{y,z}g`$, we must have that the values $`g`$ assigns to the labels in $`L`$ form a vector in the nullspace of $`A`$ (viewing $`A`$ as a matrix over $`𝔽`$).

Let $`d`$ be the dimension of the nullspace of $`A`$. We claim that

$$\left|\left\{g_0\right|f_{y,z}g\}\right|\left(p1\left(\genfrac{}{}{0pt}{}{l}{2}\right)\right)\left(p^{2d4}\left(\genfrac{}{}{0pt}{}{l}{2}\right)p^{2d6}\right)(p^2l)!$$
(6)
and

$$\left|\left\{g_1\right|f_{y,z}g\}\right|p^{2d4}(p^2l)!.$$
(7)
This suffices to prove (4), since by (6) and (7) we determine that for all $`f_1`$ we have

$$\left|\left\{g_0\right|f_{y,z}g\}\right|(pt(n)^2)\left|\left\{g_1\right|f_{y,z}g\}\right|,$$

and summing over those equivalence classes for which $`M(B_f,y,z)=1`$ yields (4).

The inequality (7) is immediate since the collection of vectors in the nullspace of $`A`$ that assign values $`(1,0)`$ and $`(0,1)`$ to the labels $`1`$ and $`2`$, respectively, is a hyperplane of dimension $`d2`$, and each vector in this hyperplane can be extended to yield at most $`(p^2l)!`$ distinct $`g_1`$ with $`g_{y,z}f`$.

To prove (6), let us define

$$H_a=\{h𝔽^l|Ah=0,h[1]=(1,0),\text{and}h[2]=(a,0)\}$$

for each $`a\{2,\mathrm{},p1\}`$, and define

$$T=\{h𝔽^l|h[i]h[j]\text{for}ij\}.$$

We will prove that there are at least $`p1\left(\genfrac{}{}{0pt}{}{l}{2}\right)`$ values of $`a`$ for which $`H_aT`$ contains at least $`p^{2d4}\left(\genfrac{}{}{0pt}{}{l}{2}\right)p^{2d6}`$ elements. As each $`hH_aT`$ may be extended to yield $`(p^2l)!`$ distinct $`g_0`$ with $`g_{y,z}f`$, we will have proved (6).

Suppose $`H_aT`$ is nonempty for $`a\{2,\mathrm{},p1\}`$. Then of course $`H_a`$ is nonempty, and is therefore a hyperplane of dimension $`d2`$. We may also conclude that for each pair $`ijL`$, the intersection of $`H_a`$ with the subspace $`J_{i,j}=\{h𝔽^l|h[i]=h[j]\}`$ is properly contained in $`H_a`$, and is therefore a hyperplane of dimension at most $`d3`$. Since $`T=𝔽^l\backslash \left(_{ij}J_{i,j}\right)`$, there must therefore be at least $`p^{2(d2)}\left(\genfrac{}{}{0pt}{}{l}{2}\right)p^{2(d3)}`$ elements in $`H_aT`$ as required.

Thus, it remains to prove that $`H_aT`$ is nonempty for at least $`p1\left(\genfrac{}{}{0pt}{}{l}{2}\right)`$ values of $`a\{2,\mathrm{},p1\}`$. In order to prove this, define a mapping $`\phi _a:_p\times _p_p\times _p`$ for each $`a\{2,\mathrm{},p1\}`$ as $`\phi _a(\alpha ,\beta )=(\alpha +a\beta ,0)`$. Let $`h_f𝔽^l`$ denote the vector corresponding to the values assigned to the labels in $`L`$ by $`f`$, and let $`\phi _a(h_f)`$ denote the vector obtained by applying $`\phi _a`$ to each entry of $`h_f`$ individually. Following from the fact that each $`\phi _a`$ is a homomorphism, we must have that $`\phi _a(h_f)`$ is in the nullspace of $`A`$, and therefore $`\phi _a(h_f)H_a`$. Write $`h_f[i]=(\alpha _i,\beta _i)`$ for each $`i`$, and suppose we have $`\phi _a(h_f[i])=\phi _a(h_f[j])`$ for some pair $`ij`$. Then $`\alpha _i+a\beta _i\alpha _j+a\beta _j(modp)`$, and so $`a(\beta _i\beta _j)\alpha _j\alpha _i(modp)`$. Since $`h_f[i]h_f[j]`$ (as $`f`$ assigns distinct values to each label), it is impossible that $`\beta _i=\beta _j`$, and so $`a(\beta _i\beta _j)^1(\alpha _j\alpha _i)(modp)`$. It follows that there are at most $`\left(\genfrac{}{}{0pt}{}{l}{2}\right)`$ nonzero values of $`a`$ such that $`\phi _a(h_f)H_aT`$, which completes the proof.

Finally, we consider a restricted case of the Group Non-Membership problem where there are only two input group elements (i.e., $`k=1`$ in the statement of the GNM problem).

2-Element Group Non-Membership (2-GNM)

| Instance: | Group elements $`g`$ and $`h`$ in some group $`G`$. |
| --- | --- |
| Question: | Is $`h`$ outside the group generated by $`g`$ (i.e., is $`hg`$)? |

We note that this problem can be solved in BQP for any group oracle $`B`$ using Shor’s algorithm.

###### Proposition 4

$`2\mathrm{GNM}(B)\mathrm{BQP}^B`$ for any group oracle $`B`$.

As this problem is not contained in (classical) MA relative to the group oracle $`B`$ constructed in the proof of Theorem 3, we have obtained the relation $`\mathrm{BQP}^B\mathrm{MA}^B`$.

###### Corollary 5

There exists an oracle $`B`$ such that $`\mathrm{BQP}^B\mathrm{MA}^B`$.

## 5 Other problems having succinct quantum proofs

Quantum certificates for group non-membership may be used in conjunction with classical certificates for other group properties to obtain succinct quantum certificates for various problems regarding finite groups. A few examples are given in this section.

Consider the following problems:

Proper Subgroup

| Instance: | Elements $`g_1,\mathrm{},g_k`$ and $`h_1,\mathrm{},h_l`$ in some group $`G`$. |
| --- | --- |
| Question: | Is $`h_1,\mathrm{},h_l`$ a proper subgroup of $`g_1,\mathrm{},g_k`$? |

Divisor of Order

| Instance: | Elements $`g_1,\mathrm{},g_k`$ in some group $`G`$ and an integer $`N`$. |
| --- | --- |
| Question: | Does $`N`$ divide the order of $`g_1,\mathrm{},g_k`$? |

Simple Group

| Instance: | Elements $`g_1,\mathrm{},g_k`$ in some group $`G`$. |
| --- | --- |
| Question: | Is $`g_1,\mathrm{},g_k`$ a simple group? |

Intersection

| Instance: | Elements $`g_1,\mathrm{},g_k`$, $`h_1,\mathrm{},h_l`$, and $`a_1,\mathrm{},a_t`$ in some group $`G`$. |
| --- | --- |
| Question: | Is $`a_1,\mathrm{},a_t`$ equal to the intersection of $`g_1,\mathrm{},g_k`$ and $`h_1,\mathrm{},h_l`$? |

Centralizer

| Instance: | Elements $`g_1,\mathrm{},g_k`$, $`h_1,\mathrm{},h_l`$ and $`a`$ in some group $`G`$. |
| --- | --- |
| Question: | Is $`h_1,\mathrm{},h_l`$ equal to the centralizer of $`a`$ in $`g_1,\mathrm{},g_k`$? |

Maximal Normal Subgroup

| Instance: | Elements $`g_1,\mathrm{},g_k`$ and $`h_1,\mathrm{},h_l`$ in some group $`G`$. |
| --- | --- |
| Question: | Is $`h_1,\mathrm{},h_l`$ a maximal normal subgroup of $`g_1,\mathrm{},g_k`$? |

The first two problems, Proper Subgroup and Divisor of Order, are in $`\mathrm{QMA}^B`$ for any group oracle $`B`$, while neither is in $`\mathrm{MA}^B`$ for appropriate choice of $`B`$. Quantum certificates for these problems may be obtained by combining quantum certificates for non-membership with classical certificates for other properties.

In the case of Proper Subgroup this is straightforward: a quantum proof that $`h_1,\mathrm{},h_l`$ is properly contained in $`g_1,\mathrm{},g_k`$ may consist of a classical portion that certifies that each $`h_i`$ may be generated from $`g_1,\mathrm{},g_k`$ and identifies an element $`ag_1,\mathrm{},g_k`$ that purportedly lies outside of $`h_1,\mathrm{},h_l`$, while the quantum portion certifies that $`ah_1,\mathrm{},h_l`$.

In the case of Divisor of Order, the quantum proof is slightly more complicated: for each prime power $`p^l`$ dividing $`N`$, the quantum proof identifies a tower of $`p`$-subgroups

$$h_1h_1,h_2\mathrm{}h_1,\mathrm{},h_l$$

of $`g_1,\mathrm{},g_k`$ having the property $`h_ih_1,\mathrm{},h_{i1}`$ for each $`i`$ (so that $`h_1,\mathrm{},h_l`$ has order at least $`p^l`$). The $`p`$-subgroup property may be certified classically , while each $`h_ih_1,\mathrm{},h_{i1}`$ may be certified with a quantum proof of non-membership.

The remaining four problems, Simple Group, Intersection, Centralizer, and Maximal Normal Subgroup, are in $`\mathrm{co}\mathrm{QMA}^B`$ for any group oracle $`B`$. For the complements of each of these problems, quantum proofs may be obtained from quantum proofs for non-membership along with classical proofs for various properties as above. For the case of Simple Group and Maximal Normal Subgroup, we rely on the fact that there exist classical certificates for the property of one group being normal in another . We leave the details for the reader.

## 6 Open Problems

We conclude by mentioning some open problems relating to quantum proofs and the class QMA.

* Is Graph Non-Isomorphism in QMA?
* Is Group Order in QMA? (That is, given group elements $`g_1,\mathrm{},g_k`$ and an integer $`N`$, are there succinct quantum proofs for the property $`N=|g_1,\mathrm{},g_k|`$?)
* Is co-NP contained in QMA? Do unexpected consequences result from such a containment?
* We have claimed that $`\mathrm{QMA}\mathrm{PP}`$; can a better upper-bound be placed on the power of QMA? What other relations among QMA and other classes can be proved?