text:
# Tunable Resonant Optical MicroCavities by Self-Assembled Templating

## Abstract

Micron-scale optical cavities are produced using a combination of template sphere self-assembly and electrochemical growth. Transmission measurements of the tunable microcavities show sharp resonant modes with a $`Q`$-factor$`>`$300, and 25-fold local enhancement of light intensity. The presence of transverse optical modes confirms the lateral confinement of photons. Calculations show sub-micron mode volumes are feasible. The small mode volume of these microcavities promises to lead to a wide range of applications in microlasers, atom optics, quantum information, biophotonics and single molecule detection.

The operation of every type of laser, as well as many varieties of atomic traps and optical sensors, depend on the formation of an optical cavity. The resonant optical modes inside this cavity determine the spatial field distribution and spectral performance of the device. The most common optical designs use spherical mirrors to form a confocal cavity that is insensitive to misalignment and confines the optical mode to the smallest lateral dimensions. The length of this cavity is on the order of the radius of curvature of the mirrors. There has been much interest in the problem of reducing the dimensions of such cavities: planar microcavities have been widely used as a way to control spontaneous emission and to enhance the interaction of light with matter, as in quantum wells or quantum dots  but these structures only confine photons in one dimension. Confinement in lateral dimensions such as in photonic crystals or microcavity mesas can inhibit spontaneous emission altogether, but involve complex and expensive fabrication strategies. Here we present a simpler approach utilising confocal microcavities. While traditional lasers built from discrete components use macroscopic spherical mirrors, so far microcavity lasers do not. Preliminary theoretical work on the mode structure in parabolic dome and spherical cavities highlight the promise of such 0D microcavities, but confirm that fabrication is nontrivial. Similarly glass or polymer microspheres show high Q-factors in whispering gallery modes but it is generally hard to control them and to couple light into and out of them.

To construct cavities with the smallest possible mode volume requires small radius-of-curvature mirrors. Using our recently devised route to simple fabrication of such spherical micro-mirrors, we demonstrate here the formation of stable microcavities on size-scales below 10 microns. Comparable vertical-cavity surface-emitting semiconductor lasers use planar mirror stacks integrated into the layered semiconductor growth, and then require sensitive lateral fabrication to produce small volume devices. Comparable whispering gallery modes in micro-spheres or micro-disks have larger mode volumes and broadband tuning of the resonant cavity wavelengths is a severe problem. By robustly embedding our spherical micro-mirrors in thin metal films, we obtain simple voltage tuning by piezo-electric translation of a top planar mirror. We thus show that at length-scales approaching the wavelength of light, the electric field distribution in such microcavities can be controlled by nanoscale tuning of the mirror, and can still be interpreted using Gaussian beam optics.

Until recently, making curved mirrors in the size range required has been difficult, but advances in electrochemistry and directed self-assembly of colloidal templates now offer a cheap and simple way to produce an array of well-ordered spherical reflecting surfaces. For the purposes of constructing microcavities, we combine spherical micro-mirrors of Au with radii $`R<10\mu `$m embedded in a thin film, with a planar top Au mirror coated on a cleaved single-mode optical fibre. The guided mode of the fibre is then also used to efficiently couple light out of the cavity. Briefly, we use a template prepared through sedimentation of a confined colloidal solution of latex spheres on an indium-tin-oxide (ITO) coated substrate electrode to leave a self-assembled arrangement. Either close-packed arrays or isolated sphere templates can be obtained by adjusting the sphere concentration or by pre-patterning. The substrate is then placed in an electrochemical cell with a solution of aqueous metal complex ions which are deposited through reduction in the interstitial spaces of the template. The resulting film thickness can be controlled precisely through measurement of the total charge, yielding cavity shapes that range from shallow dishes to nearly-complete spherical voids. The latex spheres are removed by dissolving in tetrahydrofuran, leaving a porous metallic ‘cast’ with the ordering and size of the original template. Both electron and optical microscopy (Figs.1a,b) give an indication of the mirror quality, discussed elsewhere.

By growing the micro-mirrors on semi-transparent substrates, we take advantage of the negligibly thin Au coating at the base of the mirror in order to couple light into the cavity. The results shown here use radius-of-curvature mirrors, $`R`$=5 and 10$`\mu `$m grown up to a Au thickness of around 2$`\mu `$m to form dish-like spherical reflectors between 5$`\mu `$m and 15$`\mu `$m across. However we have also successfully grown spherical reflectors down to $`R`$=100nm radius-of-curvature. The upper cavity mirrors are formed by evaporating a 28nm thick Au film (80$`\%`$ reflectivity at $`\lambda `$=750nm) on a perpendicularly-cleaved stripped single-mode optical fibre (SM660) of 100$`\mu `$m outer diameter, which is mounted in an XYZ piezoelectric (PZT) translation stage and aligned normally to the micro-mirror film (Fig.1c). A white-light source is focussed to a 10$`\mu `$m spot on the rear side of the micro-mirror film, and co-linear imaging allows us to back-illuminate individual spherical mirrors. As the fibre approaches the film, optimising the collected transmission signal brings it into correct alignment with the micro-mirror, forming the microcavity. The detected light emerging from the fibre is the product of the cavity transmission and the coupling strength to the fundamental fibre mode. Using the fibre as the top mirror thus allows a self-aligned detection geometry. We record the spectra by directly coupling the output end of the fibre to a 0.5m monochromator and CCD of combined 0.05nm resolution.

Spectral characterisation of the optical transmission through the device allows us to compare the microcavities with simple models based on Gaussian beam optics. We also produce similar 28nm-thick plane Au reflectors to directly compare our results to the plane-plane microcavity geometry using the same top fibre mirror. Typical experimental results for the transmitted modes are seen in Fig.1d, and are stable and reproducible, and similar in most well-formed spherical micro-reflectors. As expected, the spacing of longitudinal modes becomes closer together as the cavity length increases. The absolute transmission is only low here because the input coupling through the sub-micron aperture is very small for the incident incoherent white light source. Equivalent scans on a plane mirror reveal similar longitudinal modes but with a much lower finesse. A direct comparison between the plane-plane mirrors (a ‘planar’ cavity) and plane-spherical mirrors (termed ‘confocal’) is shown in Fig.2a for a cavity length, $`L`$7.9$`\mu `$m, with $`R`$=10$`\mu `$m. The general formula for the resonant frequency, $`\omega _{npl}`$, that produces zero net optical phase after one round trip is given by

$$\omega _{npl}=\frac{c}{L}\{\pi n\theta _{Au}+(2p+l+1)\mathrm{tan}^1\sqrt{\frac{L}{RL}}\}$$
(1)
where $`n,p,l`$ are positive integers describing the longitudinal, transverse radial and azimuthal mode numbers of the resonance, the second term represents the phase shift on reflection from the metal film ($`\theta _{Au}180^{}24^{}`$ is the non-ideal phase shift on reflection for Au at these wavelengths), and the third term is the Gouy phase shift arising from the range of propagation angles contained in the Gaussian mode. From this paraxial approximation, the separation of the longitudinal modes yields the cavity length directly. Plotting the experimental and theoretical longitudinal mode splitting, $`\mathrm{\Delta }\omega _L`$, as a function of the cavity length derived from the calibration of the PZT $`Z`$ translation gives an excellent fit for both types of cavity (Fig.2c).

The difference between the planar and confocal microcavities becomes clearer when the transmission peak heights and linewidths are compared. At cavity lengths $`L<R`$=10$`\mu `$m, the finesse of the confocal microcavity approaches 10, while the quality-factor, $`Q>300`$. On the other hand, the finesse of the planar microcavity does not exceed 4 due to the diffraction losses of the optical modes. This improvement can be directly seen from the peak transmission intensity vs. cavity length (Fig.2d), which is strongly enhanced for mirror separations $`<R`$.

To prove that the spherical mirror is acting to localise the optical modes in the transverse direction, the core of the optical fibre is laterally scanned in the XY-plane across the top opening of the spherical micro-mirror at a fixed cavity length. Typical spectra are shown in Fig.2b, and resolve a number of new optical modes. These modes always appear on the short wavelength side of the original longitudinal mode and thus can be identified as transverse modes formed by the lateral optical confinement of the spherical micro-mirror. They are never seen in plane-plane microcavities. To further study the spatial dependence of the spectral transmission, we systematically collect spectra at different $`X`$ positions and plot the resulting images. Scanning across the centre of the microcavity (Fig.3a, $`Y`$=0) clearly shows the emergence of the transverse modes away from the cavity axis. The higher transverse modes dominate the spectra for scans across a chord of the circular opening (Fig.3b, $`Y`$=2$`\mu `$m). Up to 6 transverse modes with similar linewidths make up each longitudinal mode. Scanning in the orthogonal direction gives similar results, indicating a near-cylindrical symmetry of the micro-resonator.

These results thus allow one to directly image the different spatial mode distributions inside the microcavity, and show that the mode spectrum consists of discrete frequencies. An emitter inside a planar microcavity can always emit in some particular direction - equation (1) is valid only for normal incidence, and at different angles of incidence the resonance frequency gradually shifts to shorter wavelengths. In fundamental contrast to this behaviour, an emitter in the confocal microcavity does not have this flexibility and can only emit in the appropriate field mode, $`\omega _{npl}`$. The transverse mode separation, $`\mathrm{\Delta }\omega _T`$, also decreases as the cavity length increases (Fig.3c), as expected from different values of $`(2p+l)`$ in equation (1). However the predicted separations (Fig.3c, lines) only account reasonably for the data if the radius-of-curvature, $`R_{fit}`$, of the spherical micro-mirror is $``$45$`\mu `$m (as discussed below). Less pronounced transverse modes are also seen in $`R`$=5$`\mu `$m microcavities, with similar transverse splittings, $`\mathrm{\Delta }\omega _T`$=12meV at $`L`$=8$`\mu `$m. The transverse spectral separation produces a corresponding lateral mode spatial separation on the order of a few hundred nanometres, providing a potentially effective way to couple into specific cavity modes.

The finesse of the different spectral modes is shown in Fig.3d as a function of the cavity length. Whereas the finesse of the planar structure is $``$4, independent of the spacing between the mirrors, the confocal microcavity performs best at small cavity separations. The maximum finesse of 15 is achieved for the lowest of the transverse modes. This agrees well with the theoretical finesse of $`\pi \sqrt{r}/(1r)`$14, where $`r`$=0.8 is the product of the amplitude reflectivity coefficients of the two mirrors. The corresponding intensity concentrated within the cavity is $`(1r)^2`$25 times greater than that of the incident light at the resonant wavelength. However, as the cavity length increases beyond the mirror curvature $`R`$, the finesse drops. This is due to the increasing diameter of the transverse field profile on the spherical micro-mirror, eventually leading to it being clipped when $`L>R`$.

In this cylindrically symmetric micro-resonator, the field modes in the paraxial approximation are given by Laguerre-Gauss functions, plotted in Fig.(4a) at the position of the top fibre mirror. This demonstrates how the microcavity dimensions here are nearly optimal to couple cavity modes into the lowest guided modes in the fibre. Higher order transverse modes have a larger diameter on the cavity mirrors hence they suffer extra loss and exhibit lower finesse, as seen in Fig.(3d). However asymmetric modes possess a field null on axis that is useful for the optical trapping of dark field species.

To understand the expected spatial patterns collected by the fibre core (with its field distribution also illustrated in Fig.4a), we convolve the cavity and fibre modes to calculate the mode overlap as a function of lateral fibre position. The higher transverse modes are generally not seen for on-axial alignment due to the averaging of the oscillating electric field by the larger extent of the fibre mode. This is even more pronounced in the smaller ($`R<`$5$`\mu `$m) spherical microcavities which give correspondingly smaller mode diameters. The calculated lateral offsets which optimise collection of the different transverse modes are plotted as white crosses in Fig.3a for $`R`$=45$`\mu `$m, giving excellent agreement with the experimental data. This concurs with the need for a larger $`R_{fit}`$ that is required to account for the transverse mode spectral separation, and suggests that the spherical geometry of our micro-mirrors is imperfect. In fact, as is visible on both the micrographs of Fig.1a,b and in scanning force microscopy images (not shown), the central portion of the micro-mirrors is completely flat ($`R=\mathrm{}`$) where the electrochemical growth appears to be screened under the template spheres. The area of the flat region is about 10$`\%`$ of the total mirror area, a ratio which remains approximately the same for spherical mirrors of radius down to 100nm. Thus an effective cavity radius-of-curvature determined by both the curved and flat sections is appropriate for the theory, in accord with the experimental results. More detailed calculations based on realistic micro-mirror shapes cannot rely on the formalism for Gaussian mode propagation. However, the close match between experimental and theoretical finesse proves that this non-spherical mirror does not degrade the phase front of the lowest cavity mode, and that the mirror flatness is not a serious problem.

In 5$`\mu `$m radius-of-curvature cavities, the tight transverse field profiles (radius $`w`$) imply diffraction angles $`\theta \lambda /\pi w>`$ 0.50 radians in the cavity, leading to significant errors of order 5$`\%`$ in the paraxial approximation, $`\mathrm{sin}\theta =\theta `$. As the size of such cavities is further reduced, these errors rapidly make conventional optical models inappropriate. Theoretical modelling to demonstrate the size scaling of these microcavities should therefore be carried out using a full solution of Maxwells’ equations in these wavelength-scale geometries. The ultimate aim is to create the smallest optical cavities ($`L\lambda /2`$) with the highest finesse. A typical electric field distribution is shown in Fig.4b for $`R`$=880nm, $`L`$=704nm, and $`\lambda `$=750nm with metallic reflectors (of conductivity 200$`/\mathrm{\Omega }m`$ hence 80$`\%`$ reflectivity), corresponding to a mode volume below (1$`\mu `$m)3. This shows that our templating scheme is suitable for sub-micron optical devices. For example, sub-picosecond optical modulators using resonant cavity enhancement of nonlinearities require short cavity lifetimes and hence short cavity lengths.

To summarise our key results, we have been able to fabricate near-spherical micro-mirror optical cavities with mode volumes below (5$`\mu `$m)3, a $`Q>300`$ and finesse $`>`$10, and an intensity enhancement $`>`$25. Both longitudinal and transverse optical modes are observed, and can be simply wavelength-tuned by PZT translation of the planar top mirror which also extracts light from the cavity. In addition, this top fibre mirror can be replaced by high-reflectivity multilayers supporting luminescent nano-particles, such as semiconductor quantum dots, for enhanced emission and microlasing. The new route this opens for cavity enhancement of light-matter coupling can be further developed by reducing still further the cavity volume (we routinely produce sub-micron reflectors) and improving the finesse (using Ag or multilayer dielectric coatings), both now in progress. We note that metal mirror cavities with similar finesse have already been shown to be sufficient for attaining strong light-matter coupling in organic chromaphores. Our preliminary measurements already suggest that these micro-mirror cavities are useful for optical-dipole force trapping, for enhanced collection of micro-photoluminescence from the focal region, or for incorporation in experiments involving cold atom interactions on integrated chips.

We gratefully thank Ed Hinds and Tim Freegarde for helpful discussions of resonator design, and Oliver Wright and Dave Hanna for critical comments. We acknowledge financial support from JSPS, EPSRC GR/N37261, GR/R54194, GR/S02662 and GR/N18598.


format: text

text:
# Sodium atoms and clusters on graphite: a density functional study

## I Introduction

Graphite is a semimetal that is widely utilized in experimental surface physics. The planar geometry and weak van der Waals -type interlayer interaction make it possible to split flat, chemically inert, and clean graphite (0001) surfaces (highly oriented pyrolytic graphite, HOPG), which are ideal for studying adsorption layers and clusters. The electronic 2D semimetal properties of graphite are well-known both experimentally and theoretically. For instance, density functional theory (DFT) has provided information about the valence charge density, electronic density of states, band structure, elastic constants, and equation of state. Cha91 ; Cha92 ; Boe97 ; Kga03

An interesting research field considers alkali metal atoms and clusters on graphite. Reactivity and metallic properties make alkali metals exciting both for nanotechnological applications and basic science, and the properties of adsorbed alkali metal atoms on HOPG evolve as a function of coverage. Initially, a dispersed and highly polarized phase (“correlated liquid”) is found where alkali atoms maintain a maximum distance between each other. After a critical density of adatoms is reached, a nucleation to more closely packed configurations (islands) occurs. Hun98  Alkali metals seem to have a higher charge transfer to HOPG with lower coverage, and an increase in adatom density tends to re-organize the charge into the alkali metal layer forming a two-dimensional metallic state that has a small surface corrugation and is almost decoupled from the substrate. Hun98 ; Whi94 ; Anc93 ; Lam98 ; Bre02  It has been proposed that alkali-metal-plated graphite could have practical applications as a substrate in studying normal and superfluid He films. Whi94 ; Che91

Despite the similar electronic structure of alkali metals, deviations in island formation and interaction with HOPG are observed as the atomic number increases. While lithium atoms either intercalate between the graphene layers Kga03  or form a planar incommensurate hcp superstructure on HOPG, Hu84  it has been suggested that sodium nucleates only in buckled (110) bcc overlayers. Bre01 ; Bre03  The larger alkali atoms (K,Ru,Cs) are found to intercalate via surface defects Whi94 ; Bre02  or to adsorb in a ($`2\times 2`$) phase occupying hollow sites of the hexagonal substrate. Whi94 ; Bre02 ; Hu86 ; Hun96  In addition, cesium can exist in an incommensurate hexagonal or a more sparse ($`\sqrt{7}\times \sqrt{7}`$)R19.11 phase, Whi94 ; Hu86 ; Hun96  and a dense $`(\sqrt{3}\times \sqrt{3})`$R30 structure has been proposed for potassium. Wu82  Obviously, the above observations are related to the atomic radius and ionization potential of the alkali atom in question, which affect both the adatom-adatom and adatom-surface interactions.

The first experimental studies considered metal islands and metal-layers on graphite. A more controlled treatment of adsorbates is challenging, and it is difficult to study separated atoms and size-selected small clusters. Contemporary experimental techniques are able to deal with the practical difficulties such as the substrate temperature, surface defects, kinetic energy of cluster deposition (“soft-landing”), and cluster aggregation. Pal03  Theoretical studies concern mostly single atoms Lou00 ; Duf98a ; Duf98b ; Gal03  or atomic layers on graphite formed by periodic boundary conditions. Anc93 ; Hjo98 ; Lam98  However, research on supported clusters is needed because they form a bridge between isolated atoms and ordered nanolayers, and they may have nanotechnological importance (quantum dots, catalysis). Several attempts to model small clusters and molecules on HOPG have been made, Duf98a ; Duf98b ; Lam98 ; Mou95 ; Hag00 ; Hag01 ; Sor01 ; Gia03 ; Fer02  but the large number of substrate atoms and the semimetallic nature of graphite (k-points) make reliable calculations very demanding.

Various theoretical methods are capable of studying metal atoms and clusters on graphite (0001). In addition to deciding which theoretical tools to use, a crucial question is how to model a graphite surface, i.e., how many graphene layers are needed, how large should the substrate be, and does the adsorbate change the surface geometry? One approach is to place the metal cluster under study onto an isolated hydrogen-terminated piece of graphite (“cluster”) that mimics a continuous surface. Lou00 ; Duf98a ; Duf98b ; Fer02  The question then is how large should the graphite cluster be in order to get realistic results? On the other hand, there is a problem in optimizing the geometry of the substrate if several graphene layers are involved. This is due to the fact that the layers are interlocked, and the system (Bernal graphite, stacking ABAB) is not fully symmetric at the substrate edges. With periodic boundary conditions one can describe, in principle, a continuous infinite system (“slab”) in the lateral dimensions. In this case, the problem is the distance between adsorbate replicas, which should be large enough to exclude charge density overlap. The large substrate that must be used increases the computational cost greatly.

In the present work, a DFT method with periodic boundary conditions has been used to model Na atoms and clusters ($`N5`$) on HOPG. The substrate consisted of three graphene layers with 32 (60) carbon atoms each. It was found that the HOPG potential energy surface (PES) is very flat with the hollow site of the carbon hexagonal structure being preferred. Although alkali metal atoms tend to be more weakly bound to the surface when the coverage increases, this tendency is not so clear in small Na clusters. The calculated cluster energetics favor clustering processes on HOPG, and the stability of open shell clusters (Na3 and Na5) is increased.

## II Simulation methods

The calculations have been performed using the Car-Parrinello molecular dynamics (CPMD) package, CPMD  which is based on density functional theory. The electron-ion interaction is described by ionic pseudopotentials having the non-local, norm-conserving, and separable form suggested by Troullier and Martins. TM91  Periodic boundary conditions are employed, and the plane wave basis has a kinetic energy cut-off of 70 Ry. The generalized gradient-corrected approximation of Perdew, Burke and Ernzerhof (PBE) PBE96  is adopted for the exchange-correlation energy density. The electronic Hamiltonian is rediagonalized after each geometry optimization step, and a finite temperature functional ($`T=1000`$ K) is used for the Kohn-Sham (KS) orbital occupancies due to the small energy gap between the occupied and unoccupied states (band gap). The ionic positions are optimized using a conjugate gradient method until all the components of nuclear gradient are below 1$`\times `$$`10^4`$ a.u.

We model two periodic substrates of Bernal graphite which consist of three graphene layers (stacking ABA) in orthorhombic supershells of 9.84$`\times `$8.53$`\times `$16.70 (96 C atoms) and 12.30$`\times `$12.79$`\times `$16.70 Å3 (180 C atoms). The smaller substrate with Na3 is shown in Fig. 1 from two perspectives. Our tests for different numbers of graphene layers have shown that at least three layers are needed in order to reach a convergence in Na adsorption. Gr3  The spacing between the layers is fixed to the experimental value 3.35 Å, since the PBE functional used has problems in describing weak van der Waals-type interactions. Kga03  The choice of $`z`$-dimension keeps the slab replica 10 Å apart, which is sufficient for most applications. However, a weak binding of Na2 (and large separation from the surface) forced us to use 2 Å larger spacing in this case. For Na4 and Na5 the interaction between cluster replicas becomes significant in the smaller box, and a larger substrate in $`x`$\- and $`y`$-dimensions is needed, where the minimum distance between the clusters is now 7.62 and 6.53 Å, respectively.

Extensive tests for different numbers of k-points have shown that the simple $`\mathrm{\Gamma }`$-point approximation is not reliable for the systems studied. This is manifested by an artificial planar elongation of the graphite hexagons during geometry optimization, and is probably related to a strong downward dispersion of the upper $`\sigma `$ bands at the $`\mathrm{\Gamma }`$-point. Cha91 ; Cha92  The problem does not occur with a 2$`\times `$2$`\times `$1 Monkhorst-Pack k-point mesh, and a variation of lateral dimension results in a value 1.421 Å for the C-C nearest neighbor distance (experimental value 1.420 Å). The Na adsorption energies obtained show that a 5$`\times `$5$`\times `$1 mesh is adequate (see also Table 1), whereas the forces are already well converged for the 2$`\times `$2$`\times `$1 mesh. We have also tested whether it is possible to use a smaller kinetic energy cutoff: In comparison with 70 Ry, a calculation with 50 Ry yielded 0.17 eV (33 %) weaker binding of Na, and the related perpendicular distance from the surface increased by 0.19 Å (7.8 %). This shows that the computational cost cannot be reduced without losing accuracy.

The effect of substrate relaxation has been studied by releasing the six nearest C atoms and reoptimizing the Na-HOPG system geometry. The changes are small (e.g. the C-C distance 1.424 Å) which validates the use of fixed substrate in real applications. A bench mark calculation for Na-HOPG shows that the local spin density (LSD) approximation does not improve the results because of the large number of KS states involved and the nonmagnetic nature of the system. The calculations below are done with spin-degenerate KS orbitals except for isolated Na atom and Na clusters.

## III Results

In order to map the potential energy surface of a Na-HOPG system, we have optimized the Na atom position for different locations along the surface (see Fig. 2). The results for adsorption energy ($`\mathrm{\Delta }E_{}`$), separation from the surface ($`d_{}`$), nearest carbon atom distances (Na-C), and carbon coordination numbers ($`N_C`$) are presented in Table 1. Here, we do not approach the real zero-density limit of Na, but the atoms are distributed in 9.84$`\times `$8.53 Å intervals due to the periodic boundary conditions applied. Orth  Inclusion of more k-points enhances binding in a systematic way yielding to an estimate of 0.51 eV for the energy minimum (point 0, 5$`\times `$5$`\times `$1 mesh). Comparison with other locations shows only small deviations in $`\mathrm{\Delta }E_{}`$ and $`d_{}`$, indicating a flat potential energy surface with a maximum variation of 0.07 eV. The points 2 and 4 above Cα and Cβ (Fig. 2) give similar results, which causes increased symmetry in the PES. These findings resemble the results by Lamoen and Persson Lam98  who obtained $`\mathrm{\Delta }E_{}=0.52`$ eV for a K-HOPG system and a small diffusion barrier (variation 0.05 eV). No k-points were used in these calculations, but we expect a systematic shift in $`\mathrm{\Delta }E_{}`$ similar to the one we found.

Table 2 shows the formation energetics of Na atoms and clusters. The formation energy $`\mathrm{\Delta }E`$ is divided into two components: the binding energy of a free cluster or a separated monolayer ($`\mathrm{\Delta }E_b`$), and a term ($`\mathrm{\Delta }E_{}`$) describing the adsorption energy. Three phases of Na-HOPG are included in Table 2, where Na(I) refers to the initial sparse system, Na(II) is a commensurate periodic structure with twice as many Na atoms per unit shell as Na(I) (Na-Na separation 6.51 Å), and Na(III) corresponds to the (2$`\times `$2) Na monolayer with four times the coverage of Na(I) and hexagonal symmetry. The phase Na(II) was encountered as a byproduct of Na2 stretching, and it corresponds to the maximal separation of Na atoms allowed by the smaller supershell used. The effect of nearby Na atoms becomes clear in Na(III), where the separation from the surface is 0.76 Å greater. The loss in surface binding is compensated by the interaction with other Na atoms, and the resulting $`\mathrm{\Delta }E`$ per atom is slightly larger than for Na(I). A similar (2$`\times `$2) structure is stable for potassium, Bre02  and theoretical studies have shown that K forms a metallic state on HOPG. Whi94 ; Anc93 ; Lam98  Our results corroborate this finding, but – in the case of Na monolayer – the spacing between Na atoms (4.92 Å) does not match typical Na-Na distances (see Na clusters in Table 3), and the energy difference with the lower coverage phase Na(I) is relatively small.

The cluster formation energies in Table 2 reveal significant differences between individual clusters. Na2 binds only very weakly due to its closed valence electron shell, and the dimer separation from the surface is 1 Å larger than for Na3 and Na4. The same effect is apparent in the $`\mathrm{\Delta }E_{}`$ values. It is interesting that the deviation of $`\mathrm{\Delta }E`$ for 2$`\times `$2$`\times `$1 and 5$`\times `$5$`\times `$1 k-point meshes becomes smaller as the distance between Na atoms and surface increases (see e.g. Na3). This implies changes in charge transfer. The larger substrate used for Na4 and Na5 requires fewer k-points to converge the formation energy, which can be seen as nearly identical $`\mathrm{\Delta }E`$ values. The $`\mathrm{\Delta }E`$ values of Na3, Na4, and Na5 are larger than for the (2$`\times `$2) Na monolayer, which shows that the clustering of Na atoms is preferred.

The optimized cluster structures are related to the ground state geometries of free Na clusters. For Na3, Na4, and Na5 the corresponding isomers are an isosceles triangle, a rhombus, and a planar C2v isomer. The clusters are placed on HOPG in a way that assumes that the hollow site (point 0) is energetically favorable for each Na atom. The related bond distances, angles, torsional angles, and distances from the surface are given in Table 3. As mentioned above, Na2 binds weakly, and this can also be seen in the very small change in dimer bond length (0.02 Å). For the other clusters changes are more obvious: Na3 adopts a geometry close to an equilateral triangle with significant changes in bond lengths and angles. Na4 bends away from planarity (torsional angle 8.7), and the bond lengths increase systematically, but the angles remain close to the initial values. For Na3 all atoms occupy similar sites on top of point 5 (see Figs. 1, 2), not far from hexagon centers. The atoms of Na4 are coordinated with HOPG in two ways: the two corners of the rhombus are above C atoms and bent towards the substrate (a result contradictory to the PES of Na(I)), whereas the other two Na atoms are close to the hexagon centers. The geometry and position of Na4 is shown in an electron density isosurface plot in Fig. 3.

The adsorption of Na5 leads to a significant distortion from planarity, with the central Na atom being much farther from the surface (0.69 Å) than the other atoms. Simultaneously, the longest Na-Na bond is broken (4.11 Å, see Table 3), and the resulting Cs structure (Fig. 4) comprises two identical triangles connected via their apices. As for the other clusters, changes in bond lengths are considerable, and there are also changes in bond angles. The Na atoms are coordinated with the surface in three ways: the central atom is on a hollow site, the two atoms that initially comprised the broken Na-Na bond sit on top of C-C bonds, and the two corner atoms are directly above C atoms. Here, we have optimized the cluster geometry with respect to a substrate consisting of two graphene layers alone (120 C atoms). Gr2  The obvious changes are an increased separation of the middle Na atom from the surface (0.20 Å) and a further elongation of the longest (broken) Na-Na bond (0.11 Å). The other bond distances and the formation energy $`\mathrm{\Delta }E`$ are unchanged.

The electron density isosurface plot of Na5-HOPG in Fig. 4 illustrates how the density is distributed within the Na5 cluster. The largest values are obtained inside the two remaining triangles, but there is a component also in the interstitial region next to the broken (or elongated) Na-Na bond. The Na atom in the middle has a pronounced hole in the density, but an atom-centered integration of charge density within a small spherical volume ($`R=1.5`$ Å) gives similar results (charges) for each Na atom. This is explained by the fact that the most coordinated Na atom has density contributions from both triangles. Presumably, this atom prefers a larger distance from the surface and a hollow site because of its higher Na coordination, whereas the lower coordinated Na atoms tend to acquire positions closer to carbons and C-C bonds. The same applies to Na4 but on a smaller scale (see Fig. 3).

We have listed on Table 4 formation energies for different cluster/atom products on top of the HOPG substrate, calculated assuming an initial state of $`N`$ free Na atoms in the gas phase. The most obvious feature is the small formation energy of Na2 containing products. This is caused by the full valence electron shell of Na2 that reduces binding with the substrate. Even two separated Na atoms are more stable on graphite than a dimer. For larger systems Na3, Na4, and Na5 are favored, indicating clustering processes, and the product Na3+Na is slightly higher in formation energy than Na4. The unpaired electron on the outermost shell of Na3 (and Na) increases binding with HOPG as seen in Table 2. A similar conclusion can be made about the high stability of Na5. This indicates that open shell clusters can be more abundant on graphite than in the gas phase.

The weak binding of Na2 compared to two separated atoms has suggested to us to investigate the breaking of this bond. For this purpose the Na2 bond distance has been increased gradually up to a point where the periodic Na(II) phase is obtained. Each configuration has been optimized with respect to the surface, and the total energy is calculated with the 5$`\times `$5$`\times `$1 $`𝐤`$-point mesh. Our results show a monotonic increase up to Na(II), which is the upper limit of Na-Na distance (6.51 Å) in the supershell chosen. At this point, the energy is 0.30 eV higher, which should be considered as the lower bound of the Na2 dissociation energy on HOPG. This is still significantly less than the gas phase value 0.68 eV, but the substrate now causes the interaction between Na atoms to be long-ranged. On the other hand, Na2 stretches readily; as the Na-Na separation is increased to 4.26 Å where both atoms sit on a hollow site (second nearest hexagons) the total energy change is only 0.09 eV, but the distance $`d_{}`$=3.09 Å is 0.86 Å less. This suggests that Na2 on graphite has very low frequency vibrational modes in both lateral and perpendicular directions.

Charge transfer between the adsorbate and the substrate is studied in detail in the case of Na-HOPG and Na3-HOPG, Cha  and the laterally averaged charge density differences ($`\mathrm{\Delta }\rho `$) are presented in Fig. 5. In both cases, the oscillating profile of $`\mathrm{\Delta }\rho `$ shows that the presence of adsorbate affects the whole system including the lowermost (third) graphene layer. The negative node close to the Na/Na3 indicates a charge transfer to the substrate that is partially counterbalanced by the strong positive peak next to the first graphene layer (GR1, see Table 5). The location and shape of the negative node is different for Na and Na3: for a single atom the charge is depleted throughout the whole atomic volume causing a broad minimum in $`\mathrm{\Delta }\rho `$, whereas for Na3 the minimum is deeper and biased to the lower side of the cluster. Integration over this area gives values $`\mathrm{\Delta }q=0.47`$ e and $`\mathrm{\Delta }q=0.48`$ e for Na and Na3, respectively. The similar $`\mathrm{\Delta }q`$ values indicate that the substrate does not support more excess charge, and it explains the increased $`d_{}`$ for Na3, Na4, Na5 and (2$`\times `$2) Na monolayer.

A layer-by-layer analysis of the graphite substrate in Table 5 shows that the charge transferred is distributed over the three layers. In comparison with the middle layer (GR2), $`\mathrm{\Delta }q`$ is slightly larger for the lowermost layer (GR3). This is probably a finite-size effect, a conclusion that is supported by the $`\mathrm{\Delta }\rho `$ profile. The inclusion of k-points leads to more pronounced oscillations near GR2 and GR3, whereas GR1 has more accumulated charge in the $`\mathrm{\Gamma }`$-point approximation. This shows that the charge transferred becomes more delocalized as k-points are introduced in the lateral dimension. The $`\mathrm{\Gamma }`$-point approximation underestimates the amount of charge transfer also for Na, whereas for Na3 the values are similar. Lamoen and Persson Lam98  found $`\mathrm{\Delta }q=0.40`$ e for a (4$`\times `$4) K monolayer, which agrees with our result $`\mathrm{\Delta }q=0.39`$ for a corresponding density of Na using a single $`\mathrm{\Gamma }`$-point (Table 5).

The electronic densities of valence states (DOS) of Na5-HOPG and HOPG are plotted in Fig. 6. The calculations were done using a 5$`\times `$5$`\times `$1 Monkhorst-Pack $`𝐤`$-point mesh, and the KS eigenvalues obtained are interpolated to correspond a 9$`\times `$9$`\times `$1 mesh (this resembles the common tetrahedron method) Lam84 . The DOS of graphite substrate shows typical features, Cha91 ; Cha92  including a steep rise at $`20`$ eV due to the 2D character of graphite, a dip at $`13`$ eV after the first two $`\sigma `$ bands, a large peak at $`6.5`$ eV followed by a shoulder in the decreasing profile with zero weight and zero gap at the Fermi energy. Our substrate model then captures the relevant properties of graphite, although the system is finite in the perpendicular direction.

A very small effect is observed due to the Na5 adsorption, and the characteristic features of graphite substrate are clearly visible. The conduction band is now being filled by the Na5 valence electrons, which can be seen as a small peak at the Fermi energy. The band structure of the three (spin-degenerate) Na5-HOPG conduction states reveals that the dispersion of the first does not correspond to its graphite counterparts ($`\pi ^{}`$ bands), but resembles more the valence states ($`\pi `$ bands). This is not true for the two other conduction states, where the lower one shows only minor variation as a function of $`𝐤`$, and the higher one resembles closely the graphite conduction bands. The two uppermost valence states are also affected by the presence of Na5, which can be seen as smaller dispersion. Together with the lowest conduction state, this results in a small hump in the DOS next to the minimum separating conduction and valence bands.

## IV Conclusion

We have studied Na atoms and small Na clusters ($`N5`$) on graphite using a DFT method that uses pseudopotentials and periodic boundary conditions. In order to obtain reliable results the simulated slab of graphite consists of three graphene layers, and is sufficiently large to yield an appropriate separation between the adsorbate replica in lateral dimension. In addition, a high kinetic energy cutoff (70 Ry) for the plane wave basis set and k-points make the calculations very demanding in terms of CPU time and memory.

For a dispersed phase, an Na atom has an adsorption energy of 0.51 eV at the hollow site 2.45 Å above the surface. The small diffusion barrier of 0.06 eV shows that the potential energy surface of the Na atom is flat. These results are similar to the recent results for NaC60 compounds, where an adsorption energy of 0.65 eV and a diffusion barrier of 0.07 eV were observed at the hexagonal site. Roq03  A higher Na coverage leads to a decreased interaction with the substrate as shown for the (2$`\times `$2) monolayer ($`d_{}=3.21`$ Å). The dispersed phase and (2$`\times `$2) monolayer differ little energetically, and neither is found to be stable experimentally. Instead, the calculated cluster formation energies favor clustering processes (island formation) in agreement with experiment. Whi94 ; Bre01 ; Bre03  The formation energies of the open shell systems Na, Na3, and Na5 are larger than those of closed shell cases Na2 and Na4. This is related to the spin-degeneracy of the highest molecular orbital (odd-even staggering) and, in contrast to free metal clusters, gives rise to increased stability of odd cluster sizes on HOPG.

A charge density analysis for Na and Na3 shows that approximately 0.5 electrons are transferred to the substrate in both cases, indicating that HOPG does not support much excess charge, and that polarization effects weaken as the Na coverage is increased. As shown before for K, Anc93 ; Whi94 ; Lam98  this leads to decoupling between the adsorbate and substrate, and a two-dimensional metallic film on HOPG results. In the case of Na clusters, the partial loss in electron density is evident in significant changes in cluster geometries. For example, Na3 is more like a closed shell Na$`{}_{}{}^{+}{}_{3}{}^{}`$ ion, and consequently, the geometry is closer to an equilateral triangle than that of a free Na3. An interesting observation is that the planarity of Na4 and Na5 is broken as the atoms having more Na-Na bonds move farther from the surface. Whether this is related to the experimentally observed buckling of Na overlayers remains an open question. Bre01 ; Bre02

## V Acknowledgments

This work has been supported by the Academy of Finland under the Finnish Centre of Excellence Programme 2000-2005 (Project No. 44875, Nuclear and Condensed Matter Programme at JYFL). The calculations were performed on the IBM-SP4 computers at the Center for Scientific Computing, Espoo, Finland. J.A. has been supported by the Bundesministerium für Bildung und Forschung (BMBF), Bonn, within the Kompetenzzentrum Materialsimulation, 03N6015. We thank R.O. Jones for valuable discussions and critical reading of the manuscript.


text:
# Metric Diophantine approximation and ‘absolutely friendly’ measures

## 1 Introduction

### 1.1 The problem and results

The classical result of Dirichlet in the theory of Diophantine approximation states that for any point $`𝐱=(x_1,\mathrm{},x_d)R^d`$, there exist infinitely many $`(𝐩,q)Z^d\times N`$ such that

$$\underset{1id}{\mathrm{max}}|x_ip_i/q|q^{(d+1)/d}.$$

Given a real, positive decreasing function $`\psi :R^+R^+`$, a point $`𝐱R^d`$ is said to be $`\psi `$–well approximable if the above inequality remains valid with the right hand side replaced with $`\psi (q)`$. We will denote by $`W(\psi )`$ the set of all such points; that is

$$W(\psi ):=\{𝐱R^d:\underset{1id}{\mathrm{max}}|x_ip_i/q|\psi (q)\mathrm{for}\mathrm{infinitely}\mathrm{many}(𝐩,q)Z^d\times N\}.$$

A straightforward application of the Borel-Cantelli lemma from probability theory yields the following statement.

###### Lemma 1

$$|W(\psi )|_d=0\mathrm{if}\underset{r=1}{\overset{\mathrm{}}{}}(r\psi (r))^d<\mathrm{}.$$

Thus, if the above sum converges then almost every (with respect to $`d`$-dimensional Lebesgue measure) point $`𝐱R^d`$ is not $`\psi `$–well approximable. For $`\tau 0`$, consider the function $`\psi _\tau :rr^\tau `$ and write $`W(\tau )`$ for $`W(\psi _\tau )`$. In view of Dirichlet’s result, $`W(\tau )=R^d`$ for $`\tau \left(d+1\right)/d\text{ }`$. However, in view of the above lemma we have that $`|W(\tau )|_d=0`$ for $`\tau >\left(d+1\right)/d\text{ }`$.

Now, let $`K`$ be a compact subset of $`R^d`$ which supports a non-atomic, finite measure $`\mu `$ and let

$$W_K(\psi ):=KW(\psi ).$$

In short, the problem is to determine conditions on $`\mu `$ and $`\psi `$ under which $`\mu (W_K(\psi ))=0`$; i.e. $`\mu `$-almost every point $`𝐱R^d`$ is not $`\psi `$–well approximable. Note that $`\mu (W_K(\psi ))=\mu (W(\psi ))`$ since $`\mu `$ is supported on $`K`$. For the motivation behind the problem we refer the reader to .

In , Kleinbock, Lindenstrauss and Weiss introduce the notion of a ‘friendly’ measure and show that if $`\mu `$ is friendly then $`\mu (W_K(\tau ))=0`$ for $`\tau >\left(d+1\right)/d\text{ }`$333They actually prove their result in the multiplicative framework.. They also show that the class of friendly measures include (i) volume measures on non-degenerate manifolds and (ii) measures supported on self similar sets satisfying the open set condition. In full generality, the definition of friendly is rather technical and will not be reproduce here – see §2 of .

Our aim is to obtain a statement more in line with Lemma 1 which also implies that $`\mu (W_K(\tau ))=0`$ for $`\tau >\left(d+1\right)/d\text{ }`$. To achieve this we impose conditions on $`\mu `$ which are stronger than those of friendly. Nevertheless, measures supported on self similar sets satisfying the open set condition are still included – see §1.2. Unfortunately, volume measures on non-degenerate manifolds and not included.

Let $`B(x,r)`$ be a ball in $`R^d`$ with centre $`x`$ and radius $`r`$. The measure $`\mu `$ is said to be doubling if there exist strictly positive constants $`D`$ and $`r_0`$ such that

$$\mu (B(x,2r))D\mu (B(x,r))xKr<r_0.$$

The following notion of ‘absolutely decaying’ is essentially taken from . Let $`\mathrm{L}`$ denote a generic $`(d1)`$–dimensional hyperplane of $`R^d`$ and let $`\mathrm{L}^{(ϵ)}`$ denote its $`ϵ`$-neighborhood. We say that $`\mu `$ is absolutely $`\alpha `$-decaying if there exist strictly positive constants $`C,\alpha ,r_0`$ such that for any hyperplane $`\mathrm{L}`$ and any $`ϵ>0`$

$$\mu \left(B(x,r)\mathrm{L}^{(ϵ)}\right)C\left(\frac{ϵ}{r}\right)^\alpha \mu (B(x,r))xKr<r_0.$$

In the case $`d=1`$, the hyperplane $`\mathrm{L}`$ is simply a point $`aR`$ and $`\mathrm{L}^{(ϵ)}`$ is the ball $`B(a,ϵ)`$ centred at $`a`$ of radius $`ϵ`$.

Remark.  Let $`B(a,r)`$ be a ball in $`R^d`$. A straightforward geometric argument shows that if $`\mu `$ is absolutely $`\alpha `$-decaying, then for any $`ϵ<1/4`$

$$\mu \left(B(a,ϵr)\right)C\mathrm{\hspace{0.17em}2}^\alpha ϵ^\alpha \mu (B(a,r))aR^dr<r_0.$$
(1)
This essentially corresponds to the condition on $`\mu `$ imposed in . Note that in the case $`d=1`$, condition (1) is equivalent to absolutely $`\alpha `$-decay.

Definition  A measure $`\mu `$ is said to be absolutely $`\alpha `$–friendly if it is doubling and absolutely $`\alpha `$-decaying.

We prove the following analogue of Lemma 1.

###### Theorem 1

Let $`K`$ be a compact subset of $`R^d`$ equipped with an absolutely $`\alpha `$–friendly measure $`\mu `$. Then

$$\mu (W_K(\psi ))=0\mathrm{if}\underset{r=1}{\overset{\mathrm{}}{}}r^{\alpha \frac{d+1}{d}1}\psi (r)^\alpha <\mathrm{}.$$

Remark.  In the case when $`d=1`$, it is possible to remove the condition that $`\mu `$ is doubling from the definition of absolutely $`\alpha `$–friendly; i.e. all that is required is that $`\mu `$ is absolutely $`\alpha `$–decaying – see §4.1. With this in mind, the above theorem restricted to $`d=1`$ is identical to that established in . Thus, Theorem 1 constitutes the natural higher dimensional analogue of . The above theorem should also be compared with Theorem 9 of .

Note that in the case that $`\psi _\tau :rr^\tau `$ and $`\tau >\frac{d+1}{d}`$,

$$\underset{r=1}{\overset{\mathrm{}}{}}r^{\alpha \frac{d+1}{d}1}\psi _\tau (r)^\alpha :=\underset{r=1}{\overset{\mathrm{}}{}}r^{1\alpha (\tau {\scriptscriptstyle \frac{d+1}{d}})}<\mathrm{}$$

and so Theorem 1 implies that $`\mu (W_K(\tau ))=0`$ whenever $`\mu `$ is absolutely $`\alpha `$–friendly. More to the point, consider the function $`\psi :rr^{{\scriptscriptstyle \frac{d+1}{d}}}(\mathrm{log}r)^\beta `$ where $`\beta >1/\alpha `$. Then

$$\underset{r=1}{\overset{\mathrm{}}{}}r^{\alpha \frac{d+1}{d}1}\psi (r)^\alpha :=\underset{r=1}{\overset{\mathrm{}}{}}r^1(\mathrm{log}r)^{\alpha \beta }<\mathrm{},$$

and Theorem 1 implies that $`\mu (W_K(\psi ))=0`$ whenever $`\mu `$ is absolutely $`\alpha `$–friendly.

It will be evident from the proof that all that is actually required in establishing the theorem is that the doubling and absolutely $`\alpha `$-decaying inequalities are satisfied at $`\mu `$–almost every point in $`K`$. Also the relevance of hyperplanes in the definition of absolutely $`\alpha `$-decaying will become crystal clear from our proof of the theorem. Essentially, on the real line $`R`$ an interval $`I_n`$ of length $`1/4n^2`$ can contain at most one rational $`p/q`$ with $`nq<2n`$. This follows from the trivial observation that if $`nq,q^{}<2n`$ then $`|p/qp^{}/q^{}|1/qq^{}>1/4n^2`$; i.e. the distance between two such rationals is strictly greater than the length of $`I_n`$. The higher dimension analogue of this is the following. Let $`B_n`$ be a ball in $`R^d`$ of radius $`c/n^{(d+1)/d}`$ where $`c`$ is a sufficiently small constant dependent only on $`d`$. Then any rational points $`𝐩/q`$ lying within $`B_n`$ with $`nq<2n`$ must lie on a single $`(d1)`$–dimensional hyperplane $`\mathrm{L}`$. This is the key observation on which the proofs of Theorems 1 and 2 hinge.

We now turn our attention to determining an upper bound for $`dimW_K(\psi )`$ – the Hausdorff dimension of $`W_K(\psi )`$. For $`s0`$, let $`^s`$ denote the $`s`$–dimensional Hausdorff measure - see §2.

###### Theorem 2

Let $`K`$ be a compact subset of $`R^d`$ equipped with an absolutely $`\alpha `$–friendly measure $`\mu `$. Furthermore, suppose there exist positive constants $`a,b,\delta `$ and $`r_o`$ such that

$$ar^\delta \mu (B(x,r))br^\delta xKr<r_0.$$
(2)
Then, for $`s\delta `$

$$^s(W_K(\psi ))=0\mathrm{if}\underset{r=1}{\overset{\mathrm{}}{}}r^{\alpha \frac{d+1}{d}1}\psi (r)^{\alpha +s\delta }<\mathrm{}.$$

Remark 1:  Note that (2) imposed on $`\mu `$ trivially implies that $`\mu `$ is doubling. Furthermore, if $`\delta >d1`$ then (2) together with a straightforward geometric argument implies that $`\mu `$ is absolutely $`\alpha `$–decaying with $`\alpha :=\delta (d1)>0`$. Thus, if $`\delta >d1`$ the hypothesis that $`\mu `$ is absolutely $`\alpha `$–friendly is in fact redundant from the statement of Theorem 2.

Remark 2: If $`K`$ supports a measure $`\mu `$ satisfying (2), then $`dimK=\delta `$ and moreover that $`0<^\delta (K)<\mathrm{}`$ – see  for the details. Now, since $`W_K(\psi )`$ is a subset of $`K`$ we have that $`dimW_K(\psi )\delta `$ and so $`^s(W_K(\psi ))=0`$ for any $`s>\delta `$. Thus, the condition $`s\delta `$ in the statement of the theorem can be assumed without any loss of generality.

Given a real, positive decreasing function $`\psi `$, the lower order $`\lambda _\psi `$ of $`1/\psi `$ is defined by

$$\lambda _\psi :=\underset{r\mathrm{}}{lim\; inf}\frac{\mathrm{log}\psi (r)}{\mathrm{log}r},$$

and indicates the growth of the function $`1/\psi `$ ‘near’ infinity. Note that $`\lambda _\psi `$ is non-negative since $`\psi `$ is a decreasing function. A simple consequence of Theorem 2 is the following statement.

###### Corollary 1

Let $`K`$ be a compact subset of $`R^d`$ equipped with an absolutely $`\alpha `$–friendly measure $`\mu `$ satisfying (2). Then, for $`\lambda _\psi \left(d+1\right)/d\text{ }`$

$$dimW_K(\psi )\delta \alpha \left(1\frac{d+1}{\lambda _\psi d}\right).$$

As a special case we obtain the following statement.

###### Corollary 2

Let $`K`$ be a compact subset of $`R^d`$ equipped with an absolutely $`\alpha `$–friendly measure $`\mu `$ satisfying (2). Then, for $`\tau \left(d+1\right)/d\text{ }`$

$$dimW_K(\tau )\delta \alpha \left(1\frac{d+1}{\tau d}\right).$$

Note that for $`\tau >\left(d+1\right)/d\text{ }`$ we have that $`dimW_K(\tau )<\delta `$. Since $`\mu `$ is comparable to $`^\delta `$ restricted to $`K`$, it follows that $`\mu (W_K(\tau ))=0`$.

A general remark: For $`d2`$, it is highly unlikely that either Theorem 1 or Theorem 2 are ever sharp. For instance, take the case that $`K:=[0,1]^d`$ and $`\mu `$ is $`d`$–dimensional Lebesgue measure. It is easily verified that $`\mu `$ is absolutely $`\alpha `$–friendly with $`\alpha =1`$. Thus, Theorem 1 implies that $`|W_K(\psi )|_d=0`$ whenever

$$\underset{r=1}{\overset{\mathrm{}}{}}r^{{\scriptscriptstyle \frac{d+1}{d}}1}\psi (r)<\mathrm{}.$$

So when $`d=1`$ this coincides with the Lemma 1. However, for $`d2`$ the above statement is weaker than that of the lemma. In view of Khintchines theorem one knows that the lemma is sharp; that is to say that if the sum in the lemma diverges then not only is $`|W_K(\psi )|_d>0`$ but it is of full measure. It is probable that the theorems of this paper are sharp in the case $`d=1`$.

### 1.2 The main example

The following statement which combines Theorems 2.2 and 8.1 of , shows that a large class of fractal measures are absolutely $`\alpha `$–friendly and satisfy (2).

###### Theorem KLW

Let $`\{𝐒_1,\mathrm{},𝐒_k\}`$ be an irreducible family of contracting self similarity maps of $`R^d`$ satisfying the open set condition and let $`\mu `$ be the restriction of $`^\delta `$ to its attractor $`K`$ where $`\delta :=dimK`$. Then $`\mu `$ is absolutely $`\alpha `$–friendly and satisfies (2).

Thus for the natural measures associated with self similar sets satisfying the open set condition, Theorems 1 and 2 are applicable. The simpliest examples of such sets include regular Cantor sets, the Sierpi$`\stackrel{´}{\mathrm{n}}`$ski gasket and the von Kock curve. All the terminology except for ‘irreducible’ is pretty much standard – see for example \[1, Chp.9\]. The notion of irreducible introduced in \[2, §2\] avoids the natural obstruction that there is a finite collection of proper affine subspaces of $`R^d`$ which is invariant under $`\{𝐒_1,\mathrm{},𝐒_k\}`$.

## 2 Hausdorff measures and dimension

In this short section we define Hausdorff measure and dimension for completeness and in order to establish some notation. For $`\rho >0`$, a countable collection $`\left\{B_i\right\}`$ of Euclidean balls in $`R^d`$ of radii $`r_i\rho `$ for each $`i`$ such that $`X_iB_i`$ is called a $`\rho `$-cover for $`X`$. Let $`s`$ be a non-negative number and define

$$_\rho ^s(X)=inf\{\underset{i}{}r_i^s:\{B_i\}\mathrm{is}\mathrm{a}\rho \mathrm{cover}\mathrm{of}X\},$$

where the infimum is taken over all possible $`\rho `$-covers of $`X`$. The s-dimensional Hausdorff measure $`^s(X)`$ of $`X`$ is defined by

$$^s(X)=\underset{\rho 0}{lim}_\rho ^s(X)=\underset{\rho >0}{sup}_\rho ^s(X)$$

and the Hausdorff dimension dim $`X`$ of $`X`$ by

$$dimX=inf\{s:^s(X)=0\}=sup\{s:^s(X)=\mathrm{}\}.$$

Further details and alternative definitions of Hausdorff measure and dimension can be found in .

## 3 A covering lemma

The following rather simple covering result will be used at various stages during the proof of our theorems.

###### Covering Lemma

Let $`(\mathrm{\Omega },d)`$ be a metric space and $``$ be a finite collection of balls with common radius $`r>0`$. Then there exists a disjoint sub-collection $`\{B_i\}`$ such that

$$\underset{B}{}B\underset{i}{}3B_i.$$

Proof : Let $`S`$ denote the set of centres of the balls in $``$. Choose $`c_1S`$ and for $`k1`$,

$$c_{k+1}S\backslash \underset{i=1}{\overset{k}{}}B(c_i,2r)$$

as long as $`S\backslash _{i=1}^kB(c_i,2r)\mathrm{}`$. Since $`\mathrm{\#}S`$ is finite, there exists $`k_1\mathrm{\#}S`$ such that

$$S\underset{i=1}{\overset{k_1}{}}B(c_i,2r).$$

By construction, any ball $`B(c,r)`$ in the original collection $``$ is contained in some ball $`B(c_i,3r)`$ and since $`d(c_i,c_j)>2r`$ the chosen balls $`B(c_i,r)`$ are clearly disjoint.

$`\mathrm{}`$

## 4 Proof of Theorem 1

Step 1: Preliminaries. We are assuming that $`r^{\alpha \frac{d+1}{d}1}\psi (r)^\alpha `$ converges and since $`\psi `$ is monotonic, it follows that

$$\underset{n=1}{\overset{\mathrm{}}{}}\left(2^{n\frac{d+1}{d}}\psi (2^n)\right)^\alpha <\mathrm{}.$$
(3)
Next notice, that without loss of generality we can assume that

$$\psi (2^n)<c\mathrm{\hspace{0.17em}2}^{n\frac{d+1}{d}}$$
(4)
for any $`c>0`$ and $`n`$ sufficiently large. This is easy to see. Suppose on the contrary that there exists a sequence $`\{n_i\}`$ such that $`\psi (2^{n_i})c\mathrm{\hspace{0.17em}2}^{n_i\frac{d+1}{d}}`$. Then

$$\underset{n=1}{\overset{\mathrm{}}{}}\left(2^{n\frac{d+1}{d}}\psi (2^n)\right)^\alpha \underset{i=1}{\overset{\mathrm{}}{}}\left(2^{n_i\frac{d+1}{d}}\psi (2^{n_i})\right)^\alpha c^\alpha \underset{n=1}{\overset{\mathrm{}}{}}1=\mathrm{},$$

and this contradicts (3).

Step 2: The balls $`\mathrm{D}_n`$. For $`nN`$, let $`\mathrm{D}_n`$ denote a generic ball with centre in $`K`$ and of radius

$$r_n:=\frac{1}{6}\left(\frac{1}{\kappa d!}\right)^{\frac{1}{d}}2^{\frac{d+1}{d}(n+1)}.$$

Here $`\kappa :=\kappa (d)`$ is the volume ($`d`$–dimensional Lebesgue measure) of a ball of radius one in $`R^d`$. In view of the covering lemma and the fact that $`K`$ is compact, there exists a finite, disjoint collection $`𝒟_n`$ of balls $`\mathrm{D}_n`$ with centers in $`K`$ such that

$$\underset{𝒟_n}{}3\mathrm{D}_nK.$$

Note that since $`\mu `$ is doubling, we have that

$$\underset{𝒟_n}{}\mu (3\mathrm{D}_n)\underset{𝒟_n}{}\mu (4\mathrm{D}_n)D^2\underset{𝒟_n}{}\mu (\mathrm{D}_n)=D^2\mu \left(\underset{𝒟_n}{\overset{}{}}\mathrm{D}_n\right)D^2\mu (K).$$
(5)
Next, consider a ball $`3\mathrm{D}_n`$ where $`\mathrm{D}_n𝒟_n`$. Suppose there is a rational point $`𝐩/q:=(p^{(1)}/q,\mathrm{},p^{(d)}/q)`$ such that

$$B(𝐩/q,\sqrt{d}\psi (q))3\mathrm{D}_n\mathrm{}\mathrm{and}2^nq<2^{n+1}.$$
(6)
By (4) and using the fact that $`\psi `$ is decreasing, it follows that for $`n`$ sufficiently large $`𝐩/q6\mathrm{D}_n`$. Now assume that there are $`d+1`$ or more such rational points satisfying (6). Take any $`d+1`$ such rationals; $`𝐩_\genfrac{}{}{0pt}{}{}{0}/q_\genfrac{}{}{0pt}{}{}{0},𝐩_\genfrac{}{}{0pt}{}{}{1}/q_\genfrac{}{}{0pt}{}{}{1},\mathrm{},𝐩_\genfrac{}{}{0pt}{}{}{d}/q_\genfrac{}{}{0pt}{}{}{d}`$. In view of the denominator constraint, the rational points are necessarily distinct. Suppose for the moment that they do not lie on a $`(d1)`$–dimensional hyperplane and form the $`d`$–dimensional simplex $`\mathrm{\Delta }`$ sub-tended by them; i.e. an interval when $`d=1`$, a triangle when $`d=2`$ and a tetrahedron when $`d=3`$. The volume ($`d`$–dimensional Lebesgue measure) of the simplex $`\mathrm{\Delta }`$ times $`d`$ factorial is equal to the absolute value of the determinant

$$det:=\left|\begin{array}{ccccc}1& p_\genfrac{}{}{0pt}{}{}{0}^{\text{(1)}}/q_\genfrac{}{}{0pt}{}{}{0}& \mathrm{}& p_\genfrac{}{}{0pt}{}{}{0}^{\text{(d)}}/q_\genfrac{}{}{0pt}{}{}{0}& \\ & & & & \\ 1& p_\genfrac{}{}{0pt}{}{}{1}^{\text{(1)}}/q_\genfrac{}{}{0pt}{}{}{1}& \mathrm{}& p_\genfrac{}{}{0pt}{}{}{1}^{\text{(d)}}/q_\genfrac{}{}{0pt}{}{}{1}& \\ & & & & \\ \mathrm{}& & & & \\ & & & & \\ 1& p_\genfrac{}{}{0pt}{}{}{d}^{\text{(1)}}/q_\genfrac{}{}{0pt}{}{}{d}& \mathrm{}& p_\genfrac{}{}{0pt}{}{}{d}^{\text{(d)}}/q_\genfrac{}{}{0pt}{}{}{d}& \end{array}\right|.$$

Then, by (6)

$$d!\times |\mathrm{\Delta }|_d\frac{1}{q_\genfrac{}{}{0pt}{}{}{0}q_\genfrac{}{}{0pt}{}{}{1}\mathrm{}q_\genfrac{}{}{0pt}{}{}{d}}>2^{(d+1)(n+1)}.$$

Trivially,

$$|\mathrm{\hspace{0.17em}6}\mathrm{D}_n|_d=\kappa (6r_n)^d:=\frac{1}{d!}2^{(d+1)(n+1)}.$$

Thus $`|\mathrm{\Delta }|_d>|6\mathrm{D}_n|_d`$ and this is impossible since $`\mathrm{\Delta }6\mathrm{D}_n`$. The upshot of this is that the $`d`$–dimensional simplex $`\mathrm{\Delta }`$ can not exist and so if there are $`d+1`$ or more rational points satisfying (6) then they must lie on a $`(d1)`$–dimensional hyperplane $`\mathrm{L}:=\mathrm{L}(\mathrm{D}_n)`$ passing through the ball $`3\mathrm{D}_n`$. In the event that there are no more than $`d`$ rational points satisfying (6), the existence of such a hyperplane is obvious – of course it is not unique if the number of rational points is less than $`d`$. Thus, associated with each ball $`\mathrm{D}_n𝒟_n`$ there is a $`(d1)`$–dimensional hyperplane $`\mathrm{L}:=\mathrm{L}(\mathrm{D}_n)`$ containing all rational points satisfying (6). Note that in the case $`d=1`$, any hyperplane $`\mathrm{L}`$ is simply a point.

Step 3: The finale. For $`nN`$, let

$$A_n:=\underset{2^nq<2^{n+1}}{}\underset{𝐩Z^d}{}B(𝐩/q,\sqrt{d}\psi (q)).$$

By definition, $`W_K(\psi )lim\; sup_n\mathrm{}A_nK`$. It follows via Step 2 and the fact that $`\psi `$ is decreasing, that for $`n`$ sufficiently large

$`\mu (A_n):=\mu (A_nK)`$ $`=`$ $`\mu \left(A_n{\displaystyle \underset{𝒟_n}{}}3\mathrm{D}_n\right)`$
$``$ $`{\displaystyle \underset{𝒟_n}{}}\mu \left(3\mathrm{D}_n\mathrm{L}^{(ϵ)}\right)ϵ:=\sqrt{d}\psi (2^n)\mathrm{L}:=\mathrm{L}(\mathrm{D}_n)`$
$``$ $`\left(2^{n\frac{d+1}{d}}\psi (2^n)\right)^\alpha {\displaystyle \underset{𝒟_n}{}}\mu (3\mathrm{D}_n)\mu \text{ is absolutely }\alpha \text{–decaying}`$
$``$ $`\left(2^{n\frac{d+1}{d}}\psi (2^n)\right)^\alpha \mu (K)\mathrm{by}(\text{5}).`$
Hence, by (3)

$$\mu (A_nK)=\mu (A_n)\left(2^{n\frac{d+1}{d}}\psi (2^n)\right)^\alpha <\mathrm{}$$

and the Borel-Cantelli lemma implies that $`\mu (lim\; sup_n\mathrm{}A_n)=0`$. Thus, $`\mu (W_K(\psi ))`$ is zero as required.

$`\mathrm{}`$

### 4.1 The case when $`d=1`$ revisited

Clearly the above proof contains the case when $`d=1`$. However, it is possible to give a more direct proof of a stronger statement which does not assume that $`\mu `$ is doubling – see the remark straight after the statement of Theorem 1. Although the proof below is basically the same as that in , we have decided to include a sketch in order to bring out the true nature of the ‘simplex/determinate’ argument and the role of hyperplanes when $`d2`$ in the proof above. In the $`d=1`$ case, the ‘simplex/determinate’ argument reduces to the following. Consider rationals $`p/q`$ with $`2^nq<2^{n+1}`$. For any two such rationals, notice that

$$\left|\frac{p}{q}\frac{p^{}}{q^{}}\right|\frac{1}{qq^{}}>2^{2(n+1)}:=2r_n.$$

Thus, any interval of length $`2r_n`$ can contain at most one rational. In particular, the intervals $`B(p/q,r_n)`$ are disjoint.

Now let $`A_n`$ be as in Step 3. By definition, $`W_K(\psi )=lim\; sup_n\mathrm{}A_nK`$. Then, in view of (4) and the fact that $`\psi `$ is decreasing we have that for $`n`$ sufficiently large

$`\mu (A_n)`$ $``$ $`{\displaystyle \underset{2^nq<2^{n+1}}{}}{\displaystyle \underset{pZ}{}}\mu (B(p/q,ϵr_n))ϵr_n:=\psi (2^n)`$
$``$ $`\left(2^{2n}\psi (2^n)\right)^\alpha {\displaystyle \underset{2^nq<2^{n+1}}{}}{\displaystyle \underset{pZ}{}}\mu (B(p/q,r_n))\mathrm{by}(\text{1})`$
$``$ $`\left(2^{2n}\psi (2^n)\right)^\alpha \mu (K)\mathrm{by}\mathrm{disjointness}.`$
The Borel-Cantelli lemma implies the desired statement. $`\mathrm{}`$

## 5 Proof of Theorem 2

To a certain extent the proof of Theorem 2 is similar to that of Theorem 1.

Step 1: Preliminaries. Without loss of generality we can assume that $`\psi (r)0`$ as $`r\mathrm{}`$. Suppose that this was not the case. Then $`W_K(\psi )=K`$ by Dirichlet’s theorem and so $`^s(W_K(\psi ))>0`$ for any $`s\delta `$ \- see Remark 2 straight after the statement of Theorem 2.

Without loss of generality we can assume that $`s>\delta \alpha `$. If this where not the case then the sum in the statement of the theorem cannot possibly converge.

Since $`\psi `$ is monotonic, the convergence of the sum in the statement of the theorem is equivalent to

$$\underset{n=1}{\overset{\mathrm{}}{}}2^{n\alpha \frac{d+1}{d}}\psi (2^n)^{\alpha +s\delta }<\mathrm{}.$$
(7)
Finally, notice that since $`s>\delta \alpha `$, we can assume (4) without any loss of generality. Otherwise, (7) would be contradicted.

Step 2: A good $`\rho `$–cover for $`W_K(\psi )`$. For $`nN`$, let $`𝒟_n`$ be the disjoint collection of balls $`\mathrm{D}_n`$ as defined in Step 2 of §4. Since the collection is disjoint and $`\mu `$ satisfies (2), we have that for $`n`$ sufficiently large

$$\mathrm{\#}𝒟_n\times 2^{{\scriptscriptstyle \frac{d+1}{d}}(n+1)\delta }\underset{𝒟_n}{}\mu (\mathrm{D}_n)=\mu \left(\underset{𝒟_n}{\overset{}{}}\mathrm{D}_n\right)\mu (K).$$

Thus, for $`n`$ sufficiently large

$$\mathrm{\#}𝒟_n2^{{\scriptscriptstyle \frac{d+1}{d}}(n+1)\delta }.$$
(8)
Now put $`ϵ:=\sqrt{d}\psi (2^n)`$ and fix some ball $`\mathrm{D}_n𝒟_n`$. Let $`\mathrm{L}:=\mathrm{L}(\mathrm{D}_n)`$ be the $`(d1)`$–dimensional hyperplane associated with $`\mathrm{D}_n`$ – see Step 2 of §4. In view of the covering lemma, there exists a finite disjoint collection $`𝒞(\mathrm{D}_n)`$ of balls $`B_n(\psi )`$ with centers in $`K`$ and common radius $`\psi (2^n)`$ such that

$$\underset{𝒞(\mathrm{D}_n)}{}3B_n(\psi )3\mathrm{D}_n\mathrm{L}^{(ϵ)}K$$
(9)
and

$$\underset{𝒞(\mathrm{D}_n)}{\overset{}{}}B_n(\psi )6\mathrm{D}_n\mathrm{L}^{(2ϵ)}$$

The latter together with the fact that $`\mu `$ is absolutely $`\alpha `$–decaying implies that

$`\mathrm{\#}𝒞(\mathrm{D}_n)\times \psi (2^n)^\delta `$ $``$ $`{\displaystyle \underset{𝒞(\mathrm{D}_n)}{}}\mu (B_n(\psi ))=\mu \left({\displaystyle \underset{𝒞(\mathrm{D}_n)}{\overset{}{}}}B_n(\psi )\right)`$
$``$ $`\mu (6\mathrm{D}_n\mathrm{L}^{(2ϵ)})\left(2^{{\scriptscriptstyle \frac{d+1}{d}}(n+1)}\psi (2^n)\right)^\alpha 2^{{\scriptscriptstyle \frac{d+1}{d}}(n+1)\delta }.`$
Thus, for $`n`$ sufficiently large

$$\mathrm{\#}𝒞(\mathrm{D}_n)\left(2^{{\scriptscriptstyle \frac{d+1}{d}}(n+1)}\psi (2^n)\right)^{\alpha \delta }.$$
(10)
Now with $`A_n`$ defined as in Step 3 of §4, it follows via (9) that

$`A_nK`$ $`=`$ $`{\displaystyle \underset{\mathrm{D}_n𝒟_n}{}}3\mathrm{D}_nA_nK{\displaystyle \underset{\mathrm{D}_n𝒟_n}{}}3\mathrm{D}_n\mathrm{L}^{(ϵ)}K`$
$``$ $`{\displaystyle \underset{\mathrm{D}_n𝒟_n}{}}{\displaystyle \underset{B_n(\psi )𝒞(\mathrm{D}_n)}{}}3B_n(\psi ).`$
In particular, for each $`kN`$ the collection

$$\{3B_n(\psi ):B_n(\psi )𝒞(\mathrm{D}_n),\mathrm{D}_n𝒟_n\mathrm{and}n=k,k+1,\mathrm{}\},$$

is a $`\rho `$–cover for $`W_K(\psi )`$ with $`\rho =\rho (k):=3\psi (2^k)`$.

Step 3: The finale. Let $`\rho =\rho (k):=3\psi (2^k)`$. Step 2 together with the definition of $`s`$–dimensional Hausdorff measure implies that

$$_\rho ^s(W_K(\psi ))\underset{n=k}{\overset{\mathrm{}}{}}\underset{\mathrm{D}_n𝒟_n}{}\underset{B_n(\psi )𝒞(\mathrm{D}_n)}{}(3\psi (2^n))^s.$$

Thus, in view of (8) and (10), it follows that for $`k`$ sufficiently large

$$_\rho ^s(W_K(\psi ))\underset{n=k}{\overset{\mathrm{}}{}}2^{n\alpha \frac{d+1}{d}}\psi (2^n)^{\alpha +s\delta }.$$

This together with (7) implies that

$$_\rho ^s(W_K(\psi ))0\mathrm{as}\rho 0(k\mathrm{}),$$

and so $`^s(W_K(\psi ))=0`$ as required.

$`\mathrm{}`$

Acknowledgements:  SV would like to thank Barak Weiss for sending him the pre-print  from which this work has materialized and for numerous e-mail conversations. Also, thanks to Brent Everitt for the engaging conversations regarding the $`d`$–simplex. He would also like to thank Ayesha and Iona for making 2003 such a fulfilling year – may there be many more. Much appreciated and thanks again girls. Finally he would like to thank the wonderful staff at ‘Bright Beginnings’ who have been absolutely fantastic with Ayesha and Iona – in particular their best friend Claire Kerner and Angela Foley for taking them back.

Andy Pollington: Department of Mathematics, Brigham Young University,

Provo, UT 84602, USA.

e-mail: : andy@math.byu.edu

Sanju L. Velani: Department of Mathematics, University of York,

Heslington, York, YO10 5DD, England.

e-mail: slv3@york.ac.uk


text:
# 1 Introduction

## 1 Introduction

One-way functions are functions $`f`$ such that, for each $`x`$, $`f(x)`$ is efficiently computable but, only for a negligible fraction of $`y`$, $`f^1(y)`$ is computationally tractable. While the modern cryptography depends heavily on one-way functions, the existence of one-way functions is one of the most important open problems in theoretical computer science. On the other hand, Shor  showed that famous candidates of one-way functions such as the RSA function or the discrete logarithm function are no longer one-way in the quantum computation model. Nonetheless, some cryptographic applications based on quantum one-way functions have been considered (see, e.g., ).

As a cryptographic primitive other than one-way functions, pseudorandom generators have been studied well. Blum and Micali  proposed how to construct pseudorandom generators from one-way permutations and introduced the next bit test for pseudorandom generators. (They actually constructed a pseudorandom generator assuming the hardness of the discrete logarithm problem.) Since Yao  proved that the next bit test is a universal test for pseudorandom generators, the Blum–Micali’s construction paradigm of pseudorandom generators from one-way permutations was accomplished. In the case of pseudorandom generators based on one-way permutations, the next bit unpredictability can be proved by using the hard-core predicates for one-way permutations. After that, Goldreich and Levin  showed that there exists a hard-core predicate for any one-way function (and also permutation) and Håstad et al.  showed that the existence of pseudorandom generators is equivalent to that of one-way functions.

Yao’s result on the universality of the next bit test assumes that any bits appeared in pseudorandom bits are computationally unbiased. Schrift and Shamir  extended Yao’s result to the biased case and proposed universal tests for nonuniform distributions. On the other hand, no universal test for the one-wayness of a function (or a permutation) is known, although pseudorandom generators and one-way functions (or permutations) are closely related.

In the quantum computation model, Kashefi, Nishimura and Vedral  gave a necessary and sufficient condition for the existence of worst-case quantum one-way permutations. They also considered the cryptographic (i.e., average-case) quantum one-way permutations and gave a sufficient condition of (cryptographic) quantum one-way permutations. They also conjectured that the condition would be necessary. Their conditions are based on the efficient implementability of reflection operators about some class of quantum states. Note that the reflection operators are successfully used in the Grover’s algorithm  and the quantum amplitude amplification technique . To obtain a sufficient condition of cryptographic quantum one-way permutations, a notion of “pseudo identity” operators was introduced . Since the worst-case hardness of reflection operators is concerned with the worst-case hardness of the inversion of the permutation $`f`$, we need some technical tool with which the inversion process of $`f`$ becomes tolerant of some computational errors in order to obtain a sufficient condition of cryptographic quantum one-way permutations. Actually, pseudo identity operators permit of exponentially small errors during the inversion process .

In this paper, we complete a necessary and sufficient condition of cryptographic quantum one-way permutations conjectured in . We incorporate their basic ideas with a probabilistic argument in order to obtain a technical tool to permit of polynomially small errors during the inversion process. Roughly saying, pseudo identity operators are close to the identity operator in a sense. The similarity is defined by an intermediate notion between the statistical distance and the computational distance. In , it is “by upper-bounding the similarity” that the sufficient condition of cryptographic quantum one-way permutations was obtained. By using a probabilistic argument, we can estimate the expectation of the similarity and then handle polynomially small errors during the inversion of the permutation $`f`$.

Moreover, the necessary and sufficient condition of quantum one-way permutations can be regard as a universal test for the quantum one-wayness of permutations. To discuss universal tests for the one-wayness of permutations, we briefly review the universality of the next bit test for pseudorandom generators. Let $`g(x)`$ be a length-regular deterministic function such that $`g(x)`$ is of length $`\mathrm{}(n)`$ for any $`x`$ of length $`n`$. The universality of the next bit test says that we have only to check a collection of stepwise polynomial-time tests $`T_1,\mathrm{},T_{\mathrm{}(n)}`$ instead of considering all the polynomial-time tests that try to distinguish the truly random bits from output bits from $`g`$, where each $`T_i`$ is the test whether, given the $`(i1)`$-bits prefix of $`g(x)`$ (and the value of $`\mathrm{}(|x|)`$), the $`i`$-th bit of $`g(x)`$ is predictable or not with probability non-negligibly higher than 1/2. Our necessary and sufficient condition of quantum one-way permutations says that the quantum one-wayness of a given permutation $`f`$ can be checked by a collection of stepwise tests $`T_1^{},\mathrm{},T_n^{}`$ instead of considering all the tests of polynomial-size quantum circuit, where each $`T_i^{}`$ is the test whether, given some quantum state $`q_{i1}`$ that can be defined by using the $`(i1)`$-bits prefix of $`f(x)`$, some other quantity $`t_i`$ is computable with polynomial-size quantum circuit or not and the next state $`q_i`$ can be determined from $`q_{i1}`$ and $`t_i`$. In this sense, our universal test for quantum one-way permutations is analogous to the universal test (i.e., the next bit test) for pseudorandom generators.

## 2 Preliminaries

We say that a unitary operator (on $`n`$ qubits) is easy if there exists a quantum circuit implementing $`U`$ with polynomial size in $`n`$ and a set $``$ of unitary operators is easy if every $`U`$ is easy. Throughout this paper, we assume that $`f:\{0,1\}^{}\{0,1\}^{}`$ is a length-preserving permutation unless otherwise stated. Namely, for any $`x\{0,1\}^n`$, $`f(x)`$ is an $`n`$-bits string and the set $`\{f(x):x\{0,1\}^n\}`$ is of cardinality $`2^n`$ for every $`n`$. First, we mention some useful operators in describing the previous and our results. The tagging operators $`O_j`$ are defined as follows:

$$O_j|x|y=\{\begin{array}{cc}|x|y\hfill & \mathrm{if}f(y)_{(2j,2j+1)}=x_{(2j,2j+1)}\hfill \\ |x|y\hfill & \mathrm{if}f(y)_{(2j,2j+1)}x_{(2j,2j+1)}\hfill \end{array}$$

where $`y_{(i,j)}`$ denotes the substring from the $`i`$-th bit to the $`j`$-th bit of the bit string $`y`$. Note that these unitary operators $`O_j`$ are easy. Next, we consider the reflection operators $`Q_j(f)`$ as follows:

$$Q_j(f)=\underset{x\{0,1\}^n}{}|xx|(2|\psi _{j,x}\psi _{j,x}|I)$$

where

$$|\psi _{j,x}=\frac{1}{\sqrt{2^{n2j}}}\underset{y:f(y)_{(1,2j)}=x_{(1,2j)}}{}|y.$$

(See Fig. 1 for the reflection operator.) We sometimes use the notation $`Q_j`$ instead of $`Q_j(f)`$.

Fig. 1: Reflection operator

Actually, these reflection operators are somewhat special for our purpose. In general, reflection operators are commonly and successfully used in the Grover’s algorithm  and the quantum amplitude amplification technique .

###### Theorem 2.1

(Kashefi, Nishimura and Vedral ) Let $`f:\{0,1\}^n\{0,1\}^n`$ be a permutation. Then $`f`$ is worst-case quantum one-way if and only if the set $`_n=\{Q_j(f)\}_{j=0,1,\mathrm{},\frac{n}{2}1}`$ of unitary operators is not easy.

As a part of the proof of Theorem 2.1, Kashefi, Nishimura and Vedral  give a quantum algorithm (we call Algorithm INV in what follows) computing $`f^1`$ by using unitary operators $`O_j`$ and $`Q_j`$. The initial input state to INV is assumed to be

$$\frac{1}{\sqrt{2^n}}|x\underset{y\{0,1\}^n}{}|y,$$

where INV trys to compute $`f^1(x)`$. Then INV performs the following steps:

> foreach $`j=0`$ to $`\frac{n}{2}1`$
> (step W.j.1) Apply $`O_j`$ to the first and the second registers;
> (step W.j.2) Apply $`Q_j`$ to the first and the second registers.

After each step, we have the following:

(the state after step W.j.1) $`=`$ $`{\displaystyle \frac{2^j}{\sqrt{2^n}}}|x\left(\sqrt{2^{n2j}}|\psi _{j,x}2{\displaystyle \underset{y:f(y)_{(1,2j+2)}=x_{(1,2j+2)}}{}}|y\right).`$
(the state after step W.j.2) $`=`$ $`{\displaystyle \frac{2^{j+1}}{\sqrt{2^n}}}|x{\displaystyle \underset{y:f(y)_{(1,2j+2)}=x_{(1,2j+2)}}{}}|y.`$
Before reviewing a known sufficient condition of cryptographic quantum one-way permutations, we define two types of cryptographic “one-wayness” in the quantum computational setting.

###### Definition 2.1

A permutation $`f`$ is weakly quantum one-way if the following conditions are satisfied:

1. $`f`$ can be computed by a polynomial size quantum circuit (and whenever inputs are classical the corresponding outputs must be classical).
2. There exists a polynomial $`p()`$ such that for every polynomial size quantum circuit $`A`$ and all sufficiently large $`n`$’s,

$$\mathrm{Pr}[A(f(U_n))U_n]>\frac{1}{p(n)},$$

where $`U_n`$ is the uniform distribution over $`\{0,1\}^n`$.

###### Definition 2.2

A permutation $`f`$ is strongly quantum one-way if the following conditions are satisfied:

1. $`f`$ can be computed by a polynomial size quantum circuit (and whenever inputs are classical the corresponding outputs must be classical).
2. For every polynomial size quantum circuit $`A`$ and every polynomial $`p()`$ and all sufficiently large $`n`$’s,

$$\mathrm{Pr}[A(f(U_n))=U_n]<\frac{1}{p(n)}.$$

As in the classical one-way permutations, we can show that the existence of weakly quantum one-way permutations is equivalent to that of strongly quantum one-way permutations (see, e.g., ). Thus, we consider the weakly quantum one-way permutations in this paper. While Theorem 2.1 is a necessary and sufficient condition of worst-case quantum one-way permutations, Kashefi, Nishimura and Vedral  also gave a sufficient condition of cryptographic quantum one-way permutations by using the following notion.

###### Definition 2.3

Let $`d(n)n`$ be a polynomial in $`n`$ and $`J_n`$ be a $`d(n)`$-qubit unitary operator. $`J_n`$ is called $`(a(n),b(n))`$-pseudo identity if there exists a set $`X_n\{0,1\}^n`$ such that $`|X_n|/2^nb(n)`$ and for any $`z\{0,1\}^nX_n`$

$$|1(z|_10|_2)J_n(|z_1|0_2)|a(n),$$

where $`|z_1`$ is the $`n`$-qubit basis state for each $`z`$ and $`|0_2`$ corresponds to the ancillae of $`d(n)n`$ qubits.

The closeness between a pseudo identity operator and the identity operator is measured by a pair of parameters $`a(n)`$ and $`b(n)`$. The first parameter $`a(n)`$ is a measure of a statistical property and the second one $`b(n)`$ is a measure of a computational property. Note that we do not care where each $`zX_n`$ is mapped by the pseudo identity operator $`J_n`$. While we will give a necessary and sufficient condition of quantum one-way permutations by using the notion of pseudo identity, we introduce a new notion, which may be helpful to understand intuitions of our and previous conditions, in the following.

###### Definition 2.4

Let $`d^{}(n)n`$ be a polynomial in $`n`$ and $`P_n`$ be a $`d^{}(n)`$-qubit unitary operator. $`P_n`$ is called $`(a(n),b(n))`$-pseudo reflection (with respect to $`|\psi (z)`$) if there exists a set $`X_n\{0,1\}^n`$ such that $`|X_n|/2^nb(n)`$ and for any $`z\{0,1\}^nX_n`$

$$\left|1\left(z|_1w|_2\left(\underset{y\{0,1\}^n}{}|yy|_1(2|\psi (y)\psi (y)|I)_2\right)0|_3\right)P_n(|z_1|w_2|0_3)\right|a(n).$$

The above definition of pseudo reflection operators is somewhat complicated. Since Fig. 2 illustrates a geometrical intuition, it may be helpful to understand the idea of pseudo reflection operators. Let $`J_n`$ be a $`d(n)`$-qubit $`(a(n),b(n))`$-pseudo identity operator. Then $`(I_nJ_n)^{}(Q_jI_{d(n)n})(I_nJ_n)`$ is a $`(d(n)+n)`$-qubit $`(a^{}(n),b^{}(n))`$-pseudo reflection operator with respect to $`|\psi _{j,x}`$, where $`a^{}(n)2a(n)`$ and $`b^{}(n)2b(n)`$. These estimations of $`a^{}(n)`$ and $`b^{}(n)`$ are too rough to obtain a necessary and sufficient condition. Rigorously estimating these parameters is a main technical issue in this paper.

###### Theorem 2.2

(Kashefi, Nishimura and Vedral ) Let $`f`$ be a permutation that can be computed by a polynomial-size quantum circuit. If $`f`$ is not (weakly) quantum one-way, then for any polynomial $`p`$ and infinitely many $`n`$, there exist a polynomial $`r_p(n)`$ and a $`r_p(n)`$-qubit $`(1/2^{p(n)},1/p(n))`$-pseudo identity operator $`J_n`$ such that the family of pseudo reflection operators

$$_{p,n}(f)=\{(I_nJ_n)^{}(Q_j(f)I_{r_p(n)n})(I_nJ_n)\}_{j=0,1,\mathrm{},\frac{n}{2}1}$$

is easy.

Kashefi, Nishimura and Vedral  conjectured that the converse of Theorem 2.2 should still hold and proved a weaker version of the converse as follows.

###### Theorem 2.3

(Kashefi, Nishimura and Vedral ) Let $`f`$ be a permutation that can be computed by a polynomial-size quantum circuit. If for any polynomial $`p`$ and infinitely many $`n`$ there exist a polynomial $`r_p(n)`$ and a $`r_p(n)`$-qubit $`(1/2^{p(n)},p(n)/2^n)`$-pseudo identity operator $`J_n`$ such that the family of pseudo reflection operators

$$_{p,n}(f)=\{(I_nJ_n)^{}(Q_j(f)I_{r_p(n)n})(I_nJ_n)\}_{j=0,1,\mathrm{},\frac{n}{2}1}$$

is easy, then $`f`$ is not (weakly) quantum one-way.

Fig. 2: Pseudo reflection operator

We mention why it is difficult to show the converse of Theorem 2.2. To prove it by contradiction, all we can assume is the existence of a pseudo identity operator. This means that we cannot know how the pseudo identity operator is close to the identity operator. To overcome this difficulty, we introduce a probabilistic technique and estimate the expected behavior of the pseudo identity operator. Eventually, we give a necessary and sufficient condition of the existence of quantum one-way permutations in terms of reflection operators. This says that we affirmatively settle their conjecture.

## 3 Necessary and Sufficient Condition of Quantum One-way Permutations

We have a necessary and sufficient condition of cryptographic quantum one-way permutations as follows.

###### Theorem 3.1

The following statements are equivalent.

1. There exists a weakly quantum one-way permutation.
2. There exists a polynomial-time computable function $`f`$ satisfying that there exists a polynomial $`p`$ such that for all sufficiently large $`n`$’s, any polynomial $`r_p(n)`$ and any $`r_p(n)`$-qubit $`(1/2^{p(n)},1/p(n))`$-pseudo identity operator $`J_n`$ such that the family of pseudo reflection operators

$$_{n,p}(f)=\{(I_nJ_n)^{}(Q_j(f)I_{r_p(n)n})(I_nJ_n)\}_{j=0,1,\mathrm{},\frac{n}{2}1}$$

is not easy.

To grasp the intuition of Theorem 3.1, Fig 3. may be helpful. Theorem 3.1 can be proved as the combination of Theorem 2.2 and the following theorem.

###### Theorem 3.2

Let $`f`$ be a permutation that can be computed by a polynomial-size quantum circuit. If for any polynomial $`p`$ and infinitely many $`n`$ there exist a polynomial $`r_p(n)`$ and a $`r_p(n)`$-qubit $`(1/2^{p(n)},1/p(n))`$-pseudo identity operator $`J_n`$ such that the family of pseudo reflection operators

$$_{n,p}(f)=\{\stackrel{~}{Q}_j(f)\}=\{(I_nJ_n)^{}(Q_j(f)I_{r_p(n)n})(I_nJ_n)\}_{j=0,1,\mathrm{},\frac{n}{2}1}$$

is easy, then $`f`$ is not (weakly) quantum one-way.

Fig. 3: Basic operations for the inversion

Proof.  Suppose that for any polynomial $`p(n)`$, infinitely many $`n`$, and some $`(1/2^{p(n)},1/p(n))`$-pseudo identity operator $`J_n`$, the family $`_{p,n}`$ of unitary operators is easy. Moreover, let $`f`$ be a weakly quantum one-way permutation. By a probabilistic argument, we show that a contradiction follows from this assumption. For more detail, we construct an efficient inverter for $`f`$ using $`_{p,n}`$ and then, if we choose a polynomial $`p(n)`$ appropriately, this efficient inverter can compute $`x`$ from $`f(x)`$ for a large fraction of inputs, which violates the assumption that $`f`$ is a weakly quantum one-way permutation.

We first construct a polynomial-size algorithm av-INV to invert $`f`$ by using unitary operations in $`_{p,n}`$. Algorithm av-INV is almost similar to Algorithm INV except the following change: the operator $`Q_j`$ is now replaced with $`\stackrel{~}{Q}_j`$. The initial input state to av-INV is also assumed to be

$$\frac{1}{\sqrt{2^n}}|x_1\underset{y\{0,1\}^n}{}|y_2|0_3,$$

where $`|z_1`$ (resp., $`|z_2`$ and $`|z_3`$) denotes the first $`n`$-qubit (resp., the second $`n`$-qubit and the last $`(r_p(n)n)`$-qubit) register.

Algorithm av-INV performs the following steps:

> foreach $`j=0`$ to $`\frac{n}{2}1`$
> (step j.1) Apply $`O_j`$ to the first and the second registers;
> (step j.2) Apply $`\stackrel{~}{Q}_j`$ to all the registers.

For analysis of Algorithm av-INV, we use the following functionally equivalent description. (Note that the following procedure may not be efficient though the behavior is equivalent to Algorithm av-INV.)

> foreach $`j=0`$ to $`\frac{n}{2}1`$
> (step A.j.1) Apply $`O_j`$ to the first and the second registers;
> (step A.j.2) Apply $`J_n`$ to the second and third registers;
> (step A.j.3) Apply $`Q_j`$ to the first and the second registers;
> (step A.j.4) Apply $`J_n^{}`$ to the second and third registers.

Then, we can prove the following two claims.

###### Claim 3.1

Suppose that $`f`$ is a weakly quantum one-way permutation, i.e., there exists a polynomial $`r(n)1`$ such that for every polynomial size quantum circuit $`A`$ and all sufficiently large $`n`$’s, $`\mathrm{Pr}[A(f(U_n))U_n]>1/r(n)`$. Then, there are at least $`2^n(1/r(n)1/q^2(n))/(11/q^2(n))`$ $`x`$’s such that $`A`$ cannot compute $`x`$ from $`f(x)`$ with probability at least $`11/q^2(n)`$.

###### Claim 3.2

Let $`q(n)=p^{1/4}(n)/\sqrt{2n}`$. There are at most $`2^n/q(n)`$ $`x`$’s such that Algorithm av-INV cannot compute $`x`$ from $`f(x)`$ with probability at least $`11/q^2(n)`$.

The proof of Claim 3.2 is delayed and that of Claim 3.1 follows immediately from the definition of a weakly quantum one-way permutation by a counting argument.

Recall that we assume that $`f`$ is a weakly quantum one-way permutation at the beginning of this proof. Now, we can set $`p(n)=4n^2(r(n)+1)^4`$, that is, $`q(n)=r(n)+12`$. It follows that $`(1/r(n)1/q^2(n))/(11/q^2(n))>1/q(n)`$, which is a contradiction since av-INV is an inverter violating the assumption of a weakly quantum one-way permutation $`f`$. This implies that $`f`$ is not weakly quantum one-way.

In what follows, we present a proof of Claim 3.2 to complete the proof of this theorem.

Proof of Claim 3.2.  From the definition of pseudo identity operators, there exists a set $`X_n\{0,1\}^n`$ with $`|X_n|2^n/p(n)`$ such that for any $`yY_n=\{0,1\}^nX_n`$,

$$J_n|y_2|0_3=\alpha _y|y_2|0_3+|\psi _y_{23},$$

where $`|\psi _y_{23}|y_2|0_3`$ and $`|1\alpha _y|\frac{1}{2^{p(n)}}`$.

In Algorithm av-INV, we apply $`J_n`$ before and after step A.j.3 for each $`j`$. The application of $`J_n`$ makes an error in computation of $`f^1`$. We call the vector $`J_n|\psi |\psi `$ the error associated to $`|\psi `$. To measure the effect of this error, we use the following lemmas. (Lemma 3.2 itself was stated in .) We note, in the sequel, the norm over vectors is Euclidean.

###### Lemma 3.1

Assume that $`TS\{0,1\}^n`$. Then length $`l(S,T)`$ of the error associated to the state

$$|\psi (S,T)=\frac{1}{\sqrt{|S|}}\left(\underset{yST}{}|y|0\underset{yT}{}|y|0\right)$$

satisfies that

$$l(S,T)2\sqrt{\frac{|SX_n|}{|S|}}+\gamma (n),$$

where $`\gamma (n)`$ is a negligible function in $`n`$.

Proof.  First, we restate the property of the length of the error associated to the state $`|y|0`$ which was shown in . The property is that the length is at most $`\frac{2}{2^{p(n)/2}}`$ if $`yY_n`$ and at most 2 if $`yX_n`$. Using this property more carefully, we have a more tight bound of $`l(S,T)`$ as follows:

$`l(S,T)`$ $`=`$ $`|J_n|\psi (S,T)|\psi (S,T)|`$
$`=`$ $`{\displaystyle \frac{1}{\sqrt{|S|}}}\left|(J_nI)\left({\displaystyle \underset{yY_n(ST)}{}}|y|0{\displaystyle \underset{yY_nT}{}}|y|0+{\displaystyle \underset{yX_n(ST)}{}}|y|0{\displaystyle \underset{yX_nT}{}}|y|0\right)\right|`$
$``$ $`{\displaystyle \frac{1}{\sqrt{|S|}}}\left|(J_nI)\left({\displaystyle \underset{yY_n(ST)}{}}|y|0{\displaystyle \underset{yY_nT}{}}|y|0\right)\right|`$
$`+{\displaystyle \frac{1}{\sqrt{|S|}}}\left|(J_nI)\left({\displaystyle \underset{yX_n(ST)}{}}|y|0{\displaystyle \underset{yX_nT}{}}|y|0\right)\right|`$
$``$ $`{\displaystyle \frac{1}{\sqrt{|S|}}}\left({\displaystyle \underset{yY_n(ST)}{}}|J_n|y|0|y|0|+{\displaystyle \underset{yY_nT}{}}|J_n|y|0|y|0|\right)`$
$`+{\displaystyle \frac{1}{\sqrt{|S|}}}\left(\left|J_n\left({\displaystyle \underset{yX_n(ST)}{}}|y|0{\displaystyle \underset{yX_nT}{}}|y|0\right)\right|+\left|{\displaystyle \underset{yX_n(ST)}{}}|y|0{\displaystyle \underset{yX_nT}{}}|y|0\right|\right)`$
$``$ $`{\displaystyle \frac{2}{2^{p(n)/2}}}{\displaystyle \frac{|SY_n|}{\sqrt{|S|}}}+{\displaystyle \frac{2}{\sqrt{|S|}}}\sqrt{(|X_n(ST)|+|X_nT|)}`$
$`=`$ $`{\displaystyle \frac{2}{2^{p(n)/2}}}{\displaystyle \frac{|SY_n|}{\sqrt{|S|}}}+2\sqrt{{\displaystyle \frac{|SX_n|}{|S|}}}.`$
Let $`\gamma (n)`$ be the former term in the above inequality. Then

$$\gamma (n)=\frac{2}{2^{p(n)/2}}\frac{|SY_n|}{\sqrt{|S|}}<\frac{2^{n+1}}{2^{p(n)/2}}<\frac{1}{2^n}$$

and is negligible. $`\mathrm{}`$

###### Lemma 3.2

Let $`J_n|\psi (S,T)=\alpha |\psi (S,T)+|\psi (S,T)^{}`$, where $`|\psi (S,T)|\psi (S,T)^{}`$. Then, $`||\psi (S,T)^{}|l(S,T)`$.

By using Lemma 3.1 and Lemma 3.2, we consider the effect of the additional applications of pseudo identity operators to INV in order to analyze Algorithm av-INV.

For each $`j`$, we let $`S_{x,j}=\{y:f(y)_{(1,2j)}=x_{(1,2j)}\}`$ and $`T_{x,j}=\{y:f(y)_{(1,2j+2)}=x_{(1,2j+2)}\}`$. We assume that the state before step A.j.2 is

$$|x_1|\psi (S_{x,j},T_{x,j})_{23}=|x_1\frac{2^j}{\sqrt{2^n}}\left(\underset{yS_{x,j}T_{x,j}}{}|y_2\underset{yT_{x,j}}{}|y_2\right)|0_3.$$

Note that the above state is the same as the one before W.$`j`$.2 in Algorithm INV.

In step A.j.2, $`J_n`$ is applied to the state. From Lemma 3.1 and a probabilistic argument, we have the following.

###### Lemma 3.3

For each $`j`$,

$$𝐄[l(S_{x,j},T_{x,j})]\frac{2}{\sqrt{p(n)}}+\gamma (n),$$

where the expectation is over $`x\{0,1\}^n`$ and $`\gamma (n)`$ is a negligible function in $`n`$.

Proof.  Since $`f`$ is a permutation, by the definition of $`S_{x,j}`$, $`|S_{x,j}|=2^{n2j}`$. Also, $`yS_{x,j}`$ for some $`x`$ if and only if $`y_{(1,2j)}=x_{(1,2j)}`$. Then,

$$\mathrm{Pr}\left[yS_{x,j}\right]=\frac{2^{n2j}}{2^n}=\frac{1}{2^{2j}},$$

where the probability is taken over $`x\{0,1\}^n`$ uniformly. Since, for any $`(1/2^{p(n)},1/p(n))`$-pseudo identity,

$$𝐄[|X_nS_{x,j}|]=\frac{|X_n|}{2^{2j}},|S_{x,j}|=2^{n2j},\text{and}\frac{|X_n|}{2^n}=\frac{1}{p(n)},$$

it holds that

$$𝐄\left[\frac{|X_nS_{x,j}|}{|S_{x,j}|}\right]=\frac{1}{p(n)},$$

where the expectation is over $`x\{0,1\}^n`$. By Lemma 3.1,

$$𝐄\left[l(S_{x,j},T_{x,j})\right]2𝐄\left[\sqrt{\frac{|X_nS_{x,j}|}{|S_{x,j}|}}\right]+\gamma (n)2\sqrt{𝐄\left[\frac{|X_nS_{x,j}|}{|S_{x,j}|}\right]}+\gamma (n)=\frac{2}{\sqrt{p(n)}}+\gamma (n)$$

for some negligible function $`\gamma `$. $`\mathrm{}`$

From Lemma 3.2 and Lemma 3.3, we obtain a vector $`v=v_1+v_2`$ where $`v_1/|v_1|`$ is the unit vector corresponding to the state before step W.j.2 in Algorithm INV and $`v_2`$ is a vector of expected length at most $`2/\sqrt{p(n)}`$ orthogonal to $`v_1`$. (For simplicity, we neglect a negligible term $`\gamma (n)`$.) The vector $`v_2`$ corresponds to an error that happens when $`J_n`$ is applied before step A.j.3.

Next, we consider the state after step A.j.3. We assume that the state after step A.j.3 is

$$|x_1|\psi (S_{j+1},\mathrm{})_{23}=|x_1\frac{2^j}{\sqrt{2^n}}\left(\underset{yS_{x,j+1}}{}|y_2\right)|0_3.$$

Note that the above state is the same as the one after step W.j.2 in Algorithm INV. In order to analyze the effect of the application of $`J_n^{}`$ after step A.j.3, we need another lemma similar to Lemma 3.3. (The proof is omitted since its proof is also similar.)

###### Lemma 3.4

For each $`j`$,

$$𝐄[l(S_{x,j+1},\mathrm{})]\frac{2}{\sqrt{p(n)}}+\gamma (n),$$

where the expectation is over $`x\{0,1\}^n`$ and $`\gamma (n)`$ is a negligible function in $`n`$.

By a similar argument to the above, we obtain a vector $`v=v_1+v_2`$ where $`v_1/|v_1|`$ is the unit vector corresponding to the state after step W.j.2 in Algorithm INV and $`v_2`$ is a vector of expected length at most $`2/\sqrt{p(n)}`$ orthogonal to $`v_1`$. (For simplicity, we neglect a negligible term $`\gamma (n)`$.) The vector $`v_2`$ corresponds to an error that happens when $`J_n^{}`$ is applied after step A.j.3.

From the above analysis, we can see that after the completion of Algorithm av-INV on input $`x`$ the final state become $`v(x)=v_1(x)+v_2(x)`$ where $`v_1(x)`$ is parallel to

$$|x_1|f^1(x)_2|0_3$$

and $`v_2(x)`$ is a vector orthogonal to $`v_1`$. By Lemma 3.4 and the linearity of expectation, we have

$$𝐄[|v_2(x)|]2\frac{n}{2}\frac{2}{\sqrt{p(n)}}=\frac{2n}{\sqrt{p(n)}}\frac{1}{q^2(n)}$$

for $`q(n)=p^{1/4}(n)/\sqrt{2n}`$, where the expectation is over $`x\{0,1\}^n`$. It follows that the number of $`x`$ such that $`|v_2(x)|>1/q(n)`$ is at most $`2^n/q(n)`$, i.e., av-INV can invert $`f(x)`$ for at least $`2^n(11/q(n))`$ $`x`$’s with probability at least $`11/q^2(n)`$. $`\mathrm{}`$

$`\mathrm{}`$

## 4 Conclusion

By giving a proof of the conjecture left by Kashefi, Nishimura and Vedral , we have completed a necessary and sufficient condition of cryptographic quantum one-way permutations in terms of pseudo-identity and reflection operator in this paper.

The necessary and sufficient condition of quantum one-way permutations can be regard as a universal test for the quantum one-wayness of permutations. As long as the authors know, this is, classical or quantum, the first result on the universality for one-way permutations, though the next bit test is a universal test for pseudorandom generators in the classical computation. We believe that our universal test for quantum one-way permutations may help to find good candidates for them, which are currently not known.

### Acknowledgments.

We are grateful for valuable comments from anonymous referees. AK would like to acknowledge the financial support of the 21st COE for Research and Education of Fundamental Technologies in Electrical and Electronic Engineering, Kyoto University.