A bipartite unitary operator is an entangling gate if it maps at least one product state to an entangled state. It need not entangle every product input. For example, the controlled-NOT gate entangles but leaves as a product. A gate that preserves every product input is not entangling, even if it exchanges the two subsystems.
A normalized bipartite pure state is entangled when it cannot be written as a product state . Equivalently, its Schmidt rank exceeds one. This definition concerns the specified partition into systems A and B; the mixed-state definition of separability requires a different convex-mixture condition.
At the last step, and . Ignoring the recorded outcome, the final density matrix is
For large , the Taylor expansion gives
Thus , and the final state tends to , or as a pure-state representative. In fact , and its trace distance from is exactly . With records retained, the final conditional state is with probability tending to one. These are compatible descriptions, not a coherent sum of the two outcome branches. This quantum Zeno effect guides a known preparation through slowly rotating measurement bases; it is not a unitary Pauli X gate acting coherently on an arbitrary unknown input.
Figure 1.
Total probability of the final target outcome versus the uninterrupted measurement record, and the asymptotic target-error probability in measurement-guided Zeno transfer
. Details.
Put . Between successive measurement bases, the squared overlap is for retaining the same label and for changing label. The first step obeys the same rule if we regard the initial state as label 0 at angle zero. Thus the recorded labels form a Markov chain with transition matrix .
Let be the probability of label 0 after step . Then and
Since , iteration yields
This is the total final-outcome probability, including histories that change label an even number of times. The smaller quantity counts only the history with label 0 at every step and is not the requested total. For example, at the total is , whereas the uninterrupted history has probability . At , the final basis is up to signs, so the total probability of label 0 is zero, as the formula also gives. This distinguishes nonselective measurement-guided Zeno transfer from postselection on one record.
Prepare the uniform pure state
Every permutation matrix fixes this vector, so RandomPermute returns with certainty. Choose an orthonormal basis with first vector , for example the quantum Fourier transform basis. Under RandomReset, the returned state is , which gives each of the measurement labels probability .
Guess RandomPermute on label 0 and RandomReset on every other label. Then
This is invariant-pure-state discrimination against a maximally mixed reset. It also agrees with the Holevo–Helstrom theorem: the eigenvalues of are once and with multiplicity , giving optimal equal-prior success . This confirms optimal discrimination of these returned states, in addition to constructing the requested strategy.[ref] For , the actions coincide and the formula correctly gives random-guessing success .
Use the preparation and measurement from part (i). RandomReset returns the density matrix , a maximally mixed state. In the basis its two outcomes each have probability . In contrast, RandomFlip always gives outcome 0.
Guess RandomFlip after 0 and RandomReset after 1. With the supplied equal priors,
An outcome 1 identifies the reset action, but outcome 0 does not identify the flip action with certainty. For example, Bayes' theorem gives posterior probability for the flip action after 0. The total success rate already accounts for the reset runs that also produce 0.
Choose and its orthogonal companion . Since , either branch of RandomFlip returns the same pure state. Alice therefore obtains label 0 with certainty, and
The alternative choice also works: its sign change under is only a global phase. The useful property is being a Pauli eigenstate of the Pauli X gate.
Set and . They are self-adjoint operators and satisfy , because the original factors are both self-adjoint and unitary. They also commute: each acts on a different tensor factor. Hence
The same calculation in the opposite order gives . Thus is a unitary matrix for every allowed pair of factors. Commutation cancels the cross terms, while their relative imaginary coefficient supplies the opposite signs. This is the commuting-involution unitary combination.
The Pauli Y gate satisfies and . With and , the given matrix is Hermitian, and
Therefore is not a unitary matrix. Its eigenvalues are and , neither of which has modulus one. An expression would behave differently, but the printed matrix has no such factor of .
The columns are and . Their norms are one and their inner product is zero, since are orthonormal. Thus is a unitary matrix. Equivalently,
using the Hadamard gate and Pauli Z gate. The different column phases do not destroy orthonormality.
The optimum radius is a distance from some city to a selected city, so it belongs to
Sort the distinct values of , try them in increasing order, and run part (i)'s greedy procedure with each trial value . Declare a trial successful when all cities are covered using at most centers; stop a failed trial as soon as a st center would be selected. The trial must succeed by part (i), so the first successful value satisfies . Its output has
There are candidate distances and work per trial, giving a polynomial-time algorithm with running time , plus sorting. Success at need not mean that radius itself is feasible; only the radius- guarantee is used.
A faster alternative is the farthest-first traversal. Choose any first center, then repeatedly choose a city farthest from its nearest current center until have been chosen. Let be the resulting radius. If , adjoin a city attaining that distance. At every earlier selection, the maximum distance to the then-current center set was at least , so all pairs among these cities are at distance at least . Two belong to the same optimal radius- closed ball, giving by the triangle inequality. If , the guarantee is immediate. Maintaining nearest-center distances gives distance evaluations without knowing .
Assume the standard nonempty instance convention , and set . Start with no centers. Pick any city still farther than from every selected center, add it as a center, and mark every city within distance of it as covered. Stop when all cities are covered.
Distinct chosen centers have pairwise distance greater than . Fix an optimal set of centers and assign each city to one optimal center within distance . Two cities assigned to the same center have distance at most by the triangle inequality. Thus no two chosen centers can be assigned to that same optimal center. The pigeonhole principle shows that the greedy procedure selects at most centers and has radius at most . If fewer than are selected, add arbitrary distinct cities; this cannot worsen the radius.
With the supplied radius, a straightforward implementation updates coverage in time per selected center, hence takes distance tests. The argument also handles . It is the packing bound underlying the metric k-center problem.
First discard duplicate input sets, and let . If , reject by part (i); this rejection can be encoded as the fixed no-instance , , of the set basis problem. Otherwise, represent each ground element by its incidence column
Keep one element from each class of equal columns. By repeatedly applying part (ii), this preserves the answer. The reduced number of elements satisfies
Relabel these representatives and store their reduced incidence matrix. Its membership bits, the dimensions and have encoded length bounded solely by a computable function of ; the leading incidence bound is . Thus this is a kernelization, even though it is not a polynomial kernel. Forming columns and grouping identical ones takes polynomial time in the original explicit input length. To test , compare bit lengths or truncate exponentiation at ; never construct an enormous merely to perform this preprocessing comparison.
For completeness, the bounded instance can be solved explicitly. Enumerate all ordered lists of subsets of the -element ground set, allowing empty members to pad shorter bases. There are at most such lists. For a candidate basis and each reduced input set , form the union of every candidate basis set contained in . If this union equals , a representation exists; if it does not, no union of that candidate's members can represent , because any member not contained in would add a forbidden element. Testing every therefore verifies a candidate in time polynomial in .
The preprocessing is polynomial in the original input length, and the remaining search depends only on . Hence the set basis problem is fixed-parameter tractable with respect to . Empty input families and are covered by the same empty-union convention.
Write and . If is a basis for the original instance, replace each member by . Deletion commutes with unions, so the resulting family generates every member of and has at most members.
Conversely, take a basis for the reduced instance. Lift each of its members by
If is represented as a union of reduced basis sets, the same union of their lifts agrees with on . It contains exactly when one of the selected reduced basis sets contains , namely exactly when . By the assumed incidence equivalence in a set family, this occurs exactly when . Thus the lifted union is precisely , and the lifted basis has no more members.
Therefore deleting preserves the yes/no answer with the same parameter . The reverse construction does not require a reduced basis set to be an input set.
If the basis has members, it has subsets, each specifying a possible union. Different subsets can produce the same union, so the number of distinct generated sets is at most . Consequently,
Here is a set family of distinct sets. If a representation lists duplicate input sets, discard those duplicates before applying this bound. The empty union is included.
The point satisfies dual feasibility and supplies an upper bound of by weak duality. Directly, take one copy of the first constraint and four copies of the second:
Since , the original objective function is at most . The feasible point attains . Hence
There are also nonvertex optima. In terms of the slack variables, the exact objective function identity is
Equality requires , leaving the entire optimal face
Negative or on this ray are allowed. This illustrates why the single vertex of a linear polyhedron does not imply a unique optimum.
Use the standard maximum form of a linear program convention subject to and . Split the unrestricted variables as and , with all four new variables nonnegative. The resulting linear program is
If equality-constraint standard form is preferred, add a nonnegative slack variable to each inequality.
Give the two inequalities nonnegative dual variables . The dual linear program is
The paired inequalities encode equalities for the two original unrestricted variables. Equivalently, the dual linear program has , , , and . Thus its only feasible point is , of objective function value .
Only have printed nonnegativity restrictions; are unrestricted. In four-dimensional space, a vertex of a linear polyhedron needs four independent active constraints. There are exactly four available constraints, so all must be active. Solving them gives
and therefore the only possible vertex of a linear polyhedron is . It is feasible, and its four active normals are independent, so it is indeed a vertex of a linear polyhedron.
One can also see uniqueness geometrically from the slack variables and . The feasible region is in affine bijection with the nonnegative orthant in :
That orthant has only the origin as an extreme point, giving the same unique vertex of a linear polyhedron.
No. For the linear polyhedron , take and . The maximum of is one, attained at . Yet
so is not an extreme point, hence not a vertex of a linear polyhedron. An optimal face can contain many points; an arbitrary maximizer need not be one of its vertices of a linear polyhedron.
Let be a vertex of a linear polyhedron and choose independent active constraints, written , with invertible. Suppose , where and . Each selected inequality has and , while
Since both weights are positive, equality in this weighted upper bound forces for every selected row. Hence , and invertibility gives . Therefore every vertex of a linear polyhedron is an extreme point.

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