Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the computer science course of the University of Oxford 2022 Quantum information 3 a Solution by
Codex 0 2026-10-25
The two conditions on a density matrix are positive semidefiniteness and unit trace:Here positive semidefinite includes being a Hermitian matrix, with for every vector . Equivalently, a density matrix is Hermitian with nonnegative eigenvalues summing to one.
Past exam of the computer science course of the University of Oxford 2022 Quantum information 2 d Solution by
Codex 0 2026-10-25
Use Hadamard conjugation of a controlled gate to obtain the Controlled-Z gate:Conjugating by Pauli X gates on both qubits moves its negative entry from to :Finally , so a two-qubit diffusion circuit isIn temporal order, apply Hadamard gates on both qubits, Pauli X gates on both, a Hadamard gate on the second, a controlled-NOT gate , a Hadamard gate on the second, Pauli X gates on both, then Hadamard gates on both. Every gate is permitted. The overall minus sign is the allowed global phase, so this implements the required inversion about the mean for Grover search algorithm.
Past exam of the computer science course of the University of Oxford 2022 Quantum information 2 c Solution by
Codex 0 2026-10-25
Use the entanglement-assisted promised equality protocol. Alice applies the phase oracle on , and Bob applies on . These are unitary operators because their diagonal entries have modulus one. After Alice sends to Bob, the joint pure state isLet be the original maximally entangled state. If is the Hamming distance, thenBob performs the projective measurement with projectors and . Under the promise,He declares equal strings for the first outcome and distance for the other. This is exact because the promised outputs occupy orthogonal subspaces. A basic measurement also suffices: extend to an orthonormal basis and group all its other outcomes together. Alice transmits one -dimensional system, realizable using qubits; need not be a power of two.
Past exam of the computer science course of the University of Oxford 2022 Quantum information 1 d Solution by
Codex 0 2026-10-25
Use entanglement-assisted discrimination of a Pauli basis. Define the known single-qubit unitary operator by and . Prepare the device input and a reference ancilla qubit inApply the unknown device once to , then apply the known inverse to . Sincethe possible two-qubit outputs areThese are the four mutually orthogonal Bell states. A Bell-basis measurement therefore identifies the device with certainty. Explicitly, apply a controlled-NOT gate , then a Hadamard gate on , followed by computational-basis measurements. The readouts identify , respectively. Thus one use of the device and one reference qubit suffice.
Past exam of the computer science course of the University of Oxford 2022 Quantum information 1 b Solution by
Codex 0 2026-10-25
Use the Pauli X eigenstates and . Their probability amplitudes areThe Born rule givesThe two probabilities sum to one. Their dependence on the relative quantum phase is the quantum interference between the two components in the computational basis.
Past exam of the computer science course of the University of Oxford 2022 Quantum information 1 a Solution by
Codex 0 2026-10-25
A basic measurement of a finite-dimensional quantum system is specified by an orthonormal basis of its Hilbert space. For a normalized input pure state , the Born rule givesThe post-measurement state is therefore up to a global phase. An outcome of zero probability has no conditional post-measurement state. For a general input density matrix , the same basic measurement has and conditional density matrix whenever .
Past exam of the computer science course of the University of Oxford 2022 Artificial intelligence 3 f Solution by
Codex 0 2026-10-25
Use Model 3 and keep every prescribed row at its prescribed column. Initialize one queen in every other row, and minimize the conflict countThis sum counts attacking pairs; is exactly a valid completion. A neighbor changes the column of one unfixed row. Evaluate such neighbors and move to one with lower , breaking equal choices arbitrarily. Minimizing , or maximizing , is hill climbing on complete domain assignments; these assignments need not yet satisfy the inter-row constraints. Fixed rows are never moved.
The min-conflicts algorithm chooses a conflicted unfixed queen and places it in a column giving the smallest conflict count against the other queens. Recomputing only the affected pair contributions makes a move cheaper than reevaluating every pair. Equal-cost moves can help cross plateaus; bounded sideways moves or repeated random starts of only the unfixed queens can escape some traps. These modifications still preserve the prescribed positions.
Return a board only after checking and every prescribed position. A local minimum with positive is not proof of impossibility. A queens completion problem may be unsatisfiable even when its prescribed queens do not attack each other; unrestricted restart policies give no finite worst-case success bound. If every row is fixed, simply validate the one board. For a guaranteed decision procedure use finite backtracking, possibly with constraint propagation, instead of relying on hill climbing.
Past exam of the computer science course of the University of Oxford 2022 Artificial intelligence 3 e Solution by
Codex 0 2026-10-25
The conventional worst-case estimate is the backtracking leaf bound given by the product of the initial constraint domain sizes. Before exploiting any attacking-queen constraints, the three models give respectivelyModel 1 has binary choices. Model 2 has labeled queens with possible cells each. Model 3 has row variables with possible columns each. The rule of product gives the displayed bounds; assigning variables in one prescribed order avoids multiplying again by the number of variable orderings.
With mutually nonattacking prescribed queens incorporated as singleton constraint domains, the corresponding bounds improve toIn Model 1 only the prescribed occupied cells have been fixed in this estimate; immediate deletion of attacked cells tightens it further. In Model 3 consistent clues occupy distinct rows. If the clues are inconsistent, preprocessing can reject the instance immediately.
These are upper bounds on leaves, rather than exact attained counts for a fully specified pruning implementation. Ordinary backtracking rejects inconsistent partial assignments and often creates far fewer leaves; a stopped branch is itself a leaf even if not all variables were assigned. Such early leaves still obey the backtracking leaf bound, since distinct leaves describe disjoint nonempty families of full domain assignments when constraints are ignored. Counting only possible complete nonattacking assignments is a different question. For example, row/column restrictions alone reduce full assignments to at most in Model 3, but that number does not directly count failed partial leaves. Exact counts depend on variable ordering and constraint propagation, neither of which is specified.
Past exam of the computer science course of the University of Oxford 2022 Artificial intelligence 3 d Solution by
Codex 0 2026-10-25
Write for the prescribed occupied cells, with . The source’s lowercase in its coordinate bound is read as the stated board size . If two prescribed queens already attack each other, no completion exists. Each model below correctly expresses that impossibility as well as consistent inputs.
Model 1: one Boolean variable per cell. Let indicate occupancy. Requireand impose for every two distinct cells sharing a row, a column or a diagonal. Equivalently, impose exactly one queen in each row and column and at most one on each diagonal. Explicit diagonal constraints areTogether with the total-count constraint and the attacking-pair binary constraints, these force exactly the intended boards. The count and diagonal-sum constraints are legitimate many-variable constraints; this model need not be binary.
Model 2: one variable per labeled queen. Let for . Enumerate and restrict for . For every , impose the binary constraintThere are exactly variables and distinct rows, so these are distinct queens. Labeling the prescribed queens does not lose a board completion: the queens are physically indistinguishable, and any completion can be labeled to give the prescribed ones those indices. It does create redundant assignments for the remaining labels.
Model 3: one variable per row. Let be the queen’s column in row . For every , requireand impose for every . These restrictions give queens, one per row; the all-different constraint on the columns gives one per column. For nonattacking queens on rows, exactly one per row is forced by the pigeonhole principle, so no solutions are lost. Inconsistent prescribed positions in a single row give incompatible unary restrictions. All three are exact constraint satisfaction problem encodings of the queens completion problem.
Past exam of the computer science course of the University of Oxford 2022 Artificial intelligence 3 c Solution by
Codex 0 2026-10-25
For a finite constraint satisfaction problem with variables, all complete assignments have depth when each step assigns one new variable. Thus the shallowest-solution property of breadth-first search offers no advantage: every complete solution is already at that depth.
Depth-first search with backtracking stores a path and pending choices, using auxiliary space with ordinary explicit choice bookkeeping, or when each level stores only a current value index. Breadth-first search may store an exponentially large frontier, up to partial assignments. Depth-first search can also combine naturally with immediate constraint propagation and undoing changes. The finite depth avoids the infinite-branch obstruction of unrestricted depth-first tree search. Neither traversal removes the possible exponential time complexity.
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!
Intro to OurBigBook
. Source. We have two killer features:
- 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-calculusArticles 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/derivativeVideo 2. OurBigBook Web topics demo. Source. - 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.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.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. - Infinitely deep tables of contents:
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





