Use exact quantum phase estimation with control qubits initially and one target quantum register prepared in the given eigenvector . Apply Hadamard gates to the control qubits. If control bit has significance , apply a controlled unitary gate from that qubit to the target. The target stays in , while quantum phase kickback produces
Since , this is . The inverse quantum Fourier transform on the control quantum register therefore gives . The quantum measurement in the computational basis returns with certainty, so
The quantum circuit below reads left to right. The upper wires are control qubits, with least significant; the vertical ellipsis represents the intervening control wires and powers. The inverse quantum Fourier transform acts on the entire control quantum register, including any bit-order permutations.
A supplied controlled- can implement controlled- by repetitions with the same control. Hence this exact quantum circuit uses calls to the supplied controlled-, unless controlled powers are additionally available cheaply. The cost of exact phase estimation on a dyadic spectrum is not automatically polynomial in ; the question asks for an exact algorithm, not that stronger complexity guarantee. Exactness also uses the promised dyadic eigenphase, ideal gates, and the supplied inverse quantum Fourier transform.
Interpret a function collision as two distinct inputs with equal outputs. Without distinctness the request is vacuous, since an input paired with itself always qualifies. Set (handling small by direct queries), choose a known set of size , and query all its inputs. Store a classical table of their outputs and corresponding inputs. If this table contains a function collision, return it immediately.
Otherwise the table contains distinct outputs. Because is exactly two-to-one, each has exactly one partner in , the known complement of . None lies in , and different table outputs have different partners. Thus exactly inputs in , of size , satisfy the known-table membership predicate
Build a marked-state phase oracle for this predicate by a compute-phase-uncompute construction: use on a clean answer quantum register, reversibly compare its output against the classical table, apply the conditional minus sign, undo the comparison, and apply again. Since the answer operation is bitwise exclusive or, . All workspace returns to zero, and each phase query costs two calls to .
Perform known-subset Grover search in the span of the computational basis states labelled by , starting in their uniform superposition state. Reflection about this known state uses no queries; choosing as an initial interval makes a known interval that can also be encoded by its own labels. Its marked fraction is , so the previous Grover rotation angle analysis uses phase queries. On measuring , one further query checks the output and retrieves its partner from the table. The inputs are distinct because the two sets are disjoint.
Consequently the quantum query complexity is
For large , rounding the optimal Grover search algorithm iteration count gives success at least . An internal table function collision already gives certain success. The balance explains the cube-root choice. This is the Brassard–Høyer–Tapp collision algorithm: its table uses classical bits. The bound counts calls to , as requested; it does not charge table lookup and its reversible implementation as constant-time gates, or claim an overall polynomial time in .
Assume first . Define the orthonormal quantum states
and by . The relevant invariant subspace is the two-dimensional span of these quantum states, not the entire Hilbert space. The uniform quantum superposition is .
In the ordered orthonormal basis , the marked-state phase oracle is the reflection operator . Since , conjugation by the Walsh-Hadamard transform gives the Grover diffusion operator
It is the reflection in the line through . The product of these two reflection operators is a rotation matrix by toward the marked quantum state:
Thus the Born rule gives . Choose a nonnegative integer nearest to . Rounding changes the angle from by at most , so
Each Grover search algorithm iteration uses one marked-state phase oracle query; all other gates are known. A final quantum measurement in the computational basis therefore produces a uniformly chosen marked item, conditional on success, with probability better than one half when . This uses the supplied marked count to select the stopping time; an unknown needs an additional search schedule or counting procedure. If , no oracle query is needed; if , no marked item exists, so a successful search is impossible.
Use the positive-exponent quantum Fourier transform convention . The period of a function here is the least positive translation leaving the function unchanged on the cyclic group . The injective promise means exactly when . In particular : the subgroup of period translations is generated by , and wrapping the argument by preserves its value. This is exact quantum period finding on a finite cyclic group, rather than the truncated, nondividing-period version requiring continued fractions.
Prepare a uniform superposition state in the first quantum register using , and perform a reversible computation of the function into a second quantum register, cleaning its workspace by uncomputation:
A quantum measurement in the computational basis of the second quantum register leaves a periodic coset state in the first:
For the quantum Fourier transform of this periodic coset state, the finite geometric series vanishes unless the measured label is . On those labels its normalized amplitude is . Thus has the uniform distribution on a finite set on , irrespective of .
Compute the greatest common divisor by the Euclidean algorithm, and set , with . Since ,
The exact period recovery from a Fourier sample is therefore certified by testing . Every candidate divides and lies between and , so the injective promise makes that equality equivalent to . This includes , where the test uses input , and , which always succeeds. The test does not assert that an arbitrary equality of function values certifies an arbitrary period; the Fourier-derived divisor restriction is essential.
The concise result is
Here is the Euler totient function, with . The totient lower bound from the Mertens product gives for . Each trial uses polynomial time quantum Fourier transforms, function evaluations and Euclidean algorithm arithmetic in . Repeating independent trials gives constant success probability; the herald accepts only correct answers.
The printed asymptotic bound has the wrong direction for this argument. In Big O notation, the stated upper bound on the number of coprime integers supplies no success lower bound and is itself false uniformly: for prime , , not . Likewise the single-trial success need not be , since it tends to one for prime. The meaningful corrected guarantee is the lower bound above. If an upper-bounded success rate is literally required, one may deliberately retain an accepted result with an independent probability proportional to ; this discards useful successes and is unnecessary for efficient recovery.
The common-age conditional probabilities give
Here includes both possible component orders. Hence the binary star fractions have the concise ratio
As a check on the role of shared age, rather than . This is covariance induced by a shared latent variable: the red giant indicator random variables have covariance equal to the variance of , namely .
For a starburst galaxy with age , put . There is no age averaging. The component masses remain independent, so the fraction of systems with two red giants is
The last comparison is ambiguous in the printed question. Literally, the fraction of individual red giants in the first galaxy is . Since , no allowed starburst age satisfies that literal comparison. If the intended comparison is instead between systems containing two red giants in the two galaxies, compare with ; the answer is
For completeness, the individual red giant fraction in the burst is , which exceeds precisely for . This is a third, different comparison; it does not change the computed fraction of two-giant systems.
Use conditional independence at the common age . A system with a red giant and a second evolved component is either a pair of red giants, with conditional probability , or a red giant and a white dwarf, with conditional probability . The factor two counts which component is the white dwarf; a pair of red giants is counted only once. Since , the unconditional probability of this event is
This event is contained in the event of at least one red giant. Therefore the requested conditional probability, among systems selected for containing a red giant, is
In particular the denominator is a fraction of systems, not the individual-star fraction .
For this stellar population, let denote initial mass in units of the solar mass, and let denote present stellar age. Constant formation of equal numbers of stars per unit time makes the stellar age a uniform distribution on Gyr, so is uniform on . The normalized initial mass function has probability density function for , since . Consequently
These formulae have the stated age and mass domains; outside them the relevant cumulative fractions saturate at zero or one. The probability integral transform makes uniform on : gives . The time-independent initial mass function and constant number formation rate give independence of and . All fractions here count objects, including white dwarfs, using the stipulated stellar evolution law.
A red giant has
Thus the mass boundaries are and for positive . Equivalently, for the red giant region runs from to the age cap , and for it runs from to . There are no red giants with . Boundaries have zero probability and their endpoint convention does not affect the fractions. In the uniform square the red giant region is , with triangle vertices , and . The white dwarf region is the triangle .
Figure 1.
Mass-age regions and their uniform-coordinate images
. The right panel magnifies the evolved part of the unit square. All of the remaining region at larger X is main sequence. Details.
At fixed , define the conditional probabilities of a red giant, white dwarf and main sequence star by , and . Their interval widths are
Integration over the uniform distribution of age gives the individual-star fractions
The systems form a coeval binary population: the two binary star components have the same age. Their masses are independent, so has uniform probability density function on and their states have conditional independence given . Unconditional independence of their states would be incorrect: older systems make both evolved states more likely. The law of total probability now gives
The subtraction removes the double counting of systems containing two red giants.
Eliminate pressure by multiplying the radial equation by and subtracting times the vertical equation. For , incompressibility gives , and the pressure-free relation is . Substitution in the azimuthal equation yields
Thus the vertical shear instability occurs when , or for . Otherwise the nonzero modes oscillate; equality is marginal in the exponential-growth sense. With , growing disturbances have and are strongly inclined in wavevector space.
Put . Maximizing gives . For , the unstable maximizing root is
More precisely its bracket is , and . This is the maximum growth rate of the vertical shear instability. For negative , the maximum uses the corresponding negative root and is asymptotically . At there is no exponentially growing mode. The undivided formula handles : , not an exponential instability; an allowed vertical velocity can instead force a secular azimuthal change. The excluded is a spatially uniform disturbance and does not belong to the stipulated nonconstant one-phase family.
Set . Incompressibility gives . Since is nonconstant and differentiable, it follows that ; therefore
The background has no advection of a -independent perturbation. Its only remaining cross-advection term is . The velocity/time terms have spatial factor , while . For nonzero pressure amplitude, must therefore be a constant multiple of ; absorbing that multiple into gives . An additive spatial constant in is a pressure gauge. If , there is no such restriction on the unused pressure profile.
Matching coefficients gives
Because the quadratic perturbation term vanishes identically, these amplitudes give an exact single-phase incompressible perturbation of a shear flow, not merely a first-order truncation. Any sufficiently differentiable profile with works locally; boundary conditions may restrict the profiles in a particular domain.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact