Search

Rejection sampling is a well-known method to sample from a target distribution, given the ability to sample from a given distribution. The method has been first formalized by von Neumann [1951] and has many applications in classical computing. We define a quantum analogue of rejection sampling: given a black box producing a coherent superposition of (possibly unknown) quantum states with some amplitudes, the problem is to prepare a coherent superposition of the same states, albeit with different target amplitudes. The main result of this article is a tight characterization of the query complexity of this quantum state generation problem. We exhibit an algorithm, which we call quantum rejection sampling, and analyze its cost using semidefinite programming. Our proof of a matching lower bound is based on the automorphism principle that allows to symmetrize any algorithm over the automorphism group of the problem. Our main technical innovation is an extension of the automorphism principle to continuous groups that arise for quantum state generation problems where the oracle encodes unknown quantum states, instead of just classical data. Furthermore, we illustrate how quantum rejection sampling may be used as a primitive in designing quantum algorithms, by providing three different applications. We first show that it was implicitly used in the quantum algorithm for linear systems of equations by Harrow et al. [2009]. Second we show that it can be used to speed up the main step in the quantum Metropolis sampling algorithm by Temme et al. [2011]. Finally, we derive a new quantum algorithm for the hidden shift problem of an arbitrary Boolean function and relate its query complexity to “water-filling” of the Fourier spectrum.

A newly developed portable multi-channel photoplethysmography (PPG) device has been used for comparative studies of 20 healthy control subjects and 45 patients with diagnosed arterial stenosis in a leg. The peripheral blood pulsations were detected simultaneously at four body sites-the same fingers and toes of both arms and legs. The PPG pulses recorded at the periphery of the stenotic leg, if compared with those of the healthy leg, were much weaker, with delayed arrival as a consequence of increased pulse wave transit time (PWTT) due to higher vascular resistance. The specific PWTT delays for the occluded legs were in the range of 20-80 ms, while in the case of healthy subjects the leg PPG signals arrived without delays or with smaller time-shifts not exceeding 14 ms. The reference bilateral PPG signals detected at the fingertips did not show any notable PWTT delays in both groups. Parallel measurements of local blood pressures by means of the oscillometry method with subsequent calculation of the ankle-brachial index were performed. Convincing correlation between the bilateral differences in the local blood pressure (a routine tool for diagnostics of leg stenosis) and in the corresponding PWTT delay (Pearson's coefficient r= 0.93), as well as between the PWTT delay and the ankle-brachial index (r= ?0.96) has been established. From the point of view of PWTT delay, the average value of leg stenosis diagnostic threshold was established to be in the range of 23 ± 9 ms, with full reliability above 32 ms. The obtained data may find further applications in alternative methodologies for detection and/or assessment of arterial occlusions in human extremities.

The purpose of this paper is to enumerate the polynomial functions inn variables over a finite soluble group with chief factors of mutually coprime orders. For metabelian groups with chief factors of mutually coprime orders the term functions are also enumerated. The main technique employed is a decomposition of these groups of functions using the free differential calculus.

A portable multi-spectral photoplethysmography device has been used for studies of 40 subjects. Multi-spectral monitoring was performed by means of a four - wavelengths (465 nm, 530 nm, 630 nm and 870 nm) light emitted diodes (LED) and a single photodiode with multi-channel signal output processing. The proposed methodology and potential clinical applications are discussed.