REVIEW 3 major objections 5 minor 7 references
Deutsch and Jozsa's Algorithm Revisited
T0 review · 3 major / 5 minor · reviewed 2026-08-28 · deepseek-v4-flash
Pith's one-line read A three-way switch wiring carries a parity bit that solves Deutsch-Jozsa in one observation.
desk verdict A charming allegory that accidentally shows why Deutsch-Jozsa needs a black-box oracle; the one-observation 'solution' reads the wiring, not the function. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is the second switch of a three-way lighting circuit, treated as a parity register. The rule 'start in the up position and flip once for every wire connected to the lower terminal' encodes the parity of the number of lower-terminal connections in the final switch position. Reading that position turns the balanced-versus-constant decision into a single parity measurement: down means an odd number of lower connections, hence balanced; up means an even number, hence constant. The switch thereby acts as a classical ancilla that makes the mapping reversible and supplies the information the quantum oracle is supposed to hide.
What would settle it
Rewire a three-way switch circuit many times using a different construction procedure, such as starting the second switch down or flipping it for upper-terminal connections, and have an observer classify balanced versus constant by reading only the final switch position; the one-observation accuracy will drop to chance. Equivalently, hide the wiring procedure from the observer and the claimed parity readout ceases to carry information.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that, for the single-bit Deutsch-Jozsa problem, a classical observer can solve the balanced-versus-constant decision with one observation if she is allowed to read the physical state of the second switch after wiring. The switch position is a parity bit: starting up and flipping once for each wire attached to the lower terminal leaves the switch down exactly when one of the two wires is on the lower terminal (balanced wiring) and up when zero or two wires are on the lower terminal (constant wiring). Alice's classification is therefore not a black-box query but a readout of a parity value that the construction procedure deliberately encodes. The paper further claims that this parity reading extends to N wires, yielding a classical circuit that solves the parity problem with a single final reading, and that the balanced/constant distinction itself is convention-dependent because swapping the 0/1 labels transforms the four wiring diagrams in pairs.
Load-bearing premise
Alice's one-observation classification rests entirely on the premise that the electrician wired the second switch by the standard procedure of starting it up and flipping it once for each wire connected to the lower terminal; the paper never derives that procedure from the abstract black-box problem.
Editorial extensions
If this is right
- If the parity-encoding solution is accepted, the one-bit Deutsch-Jozsa problem is not intrinsically two-query classically; the number of observations needed depends on whether the oracle's construction state is readable.
- The balanced/constant classification depends on a labeling convention for 0 and 1, since rotating the right switch converts balanced diagrams into balanced diagrams and constant diagrams into constant diagrams, so query-based comparisons must fix that convention.
- For constant wiring only one wire carries information, so 'balanced' and 'constant' are not defined for a single wire; the two-wire comparison is essential to the distinction.
- The N-wire generalization gives a classical one-reading parity solution that mirrors the parity problem studied for quantum computation, tying the algorithm's power to parity rather than to entanglement.
Reading between the lines
- If the electrician's procedure is unknown, Alice's single observation fails; a fair classical/quantum comparison must either hide the construction state from the classical solver or allow it to be read, so the one-observation advantage is an oracle-modeling choice rather than a fundamental speedup.
- The allegory suggests a general design principle: any physical oracle built from cumulative toggles or phase shifts leaves a parity trace, and a classical algorithm that reads that trace can match the quantum query count, so query complexity alone does not capture the power of physical oracles.
- The optical-interferometer analogy points to a concrete test: run the parity-encoded classical circuit with controlled phase errors and compare its error rate with an interferometric implementation of Deutsch-Jozsa; the paper's own discussion implies phase correction will be the shared bottleneck.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper presents a classical allegory, involving two hotel light switches, as a purported classical analogue of Deutsch and Jozsa's algorithm. Bob identifies four possible wirings, classifies two as balanced and two as constant, and notes that two switch observations are needed classically. Alice wins a bet by identifying balanced versus constant wiring in a single observation, not by looking at the light, but by exploiting the electrician's standard procedure: the right switch starts up and is flipped once for each wire connected to the lower terminal. The final switch position then encodes the parity of the connections to the lower terminal. The paper argues that this procedure corresponds closely to reversible quantum computation, discusses parity and phase-shifter analogies, and claims an N-wire generalization that solves Deutsch's problem for many inputs.
Significance. If the central claim were correct, the paper would show that a classical system can solve the one-bit Deutsch-Jozsa problem in one observation, contradicting the usual black-box separation. However, the claim is correct only under a side-channel assumption that the oracle's internal wiring procedure is visible and governed by an externally imposed rule, which is incompatible with the black-box model. The one-bit observation is a readout of the oracle's construction, not a query of the function f. The N-wire generalization is unsound because balanced multi-bit functions need not have odd parity. The paper is an interesting expository discussion of how Deutsch's one-bit problem can be trivialized when construction information is leaked, but it does not establish a classical analogue of the quantum algorithm under any standard oracle model.
major comments (3)
- [Alice's explanation (paragraph beginning "It was easy")] The one-observation protocol depends on an unproven premise: that Mr. Oracle always starts with the right switch up and flips it once for every wire connected to the lower terminal. This rule is part of the oracle's wiring procedure, not part of the function evaluation f(x). Reading the final switch position therefore reveals construction information that a black-box oracle is required to hide. The paper explicitly acknowledges that "oracles are not supposed to devolve information" but does not resolve the objection; the remark that Alice's method "corresponds rather closely" to the quantum algorithm does not supply a missing oracle model in which one classical query to f distinguishes balanced from constant.
- [N-wire generalization (final paragraphs)] The claim that counting lower-terminal connections via switch parity solves Deutsch's algorithm for a large number of inputs is false for n >= 2. A balanced function on n input bits need not have odd Hamming-weight parity over its truth table; for example, a balanced function whose truth table contains exactly two 1s and two 0s has even parity. The final switch position can therefore not separate balanced from constant functions in the multi-bit Deutsch-Jozsa promise problem, even under the visible-construction assumption.
- [Quantum correspondence (paragraphs beginning "The mapping of the algorithm may be viewed")] The claimed equivalence between Alice's switching technique and the tensor product or controlled-NOT operation is not made precise. The text asserts that flipping the switch on connecting to "1>" is equivalent to computing the tensor product of initial and final states, but no mapping from the four wiring configurations to two-qubit states or unitary transformations is defined. The subsequent remark about amplitudes ±√2/2 is also disconnected from the deterministic promise problem of Deutsch and Jozsa, so the main stated implication for quantum computing is unsupported.
minor comments (5)
- [Figure and truth table] The ASCII diagram of the four wiring configurations is garbled in the manuscript rendering, making it difficult to verify the association of cases (a)–(d) with the rows of the truth table; the figure should be redrawn clearly.
- [Parity definition] In the paragraph defining parity, "devisable" should read "divisible".
- [Conventions] The truth table would be easier to follow if the convention for up/down versus 0/1 and the meaning of the light-on/light-off columns were stated before the table, rather than after it.
- [References] Reference 6 lacks a title, and reference 8 is a 1935 engineering textbook; for a quantum-computing audience, a more accessible reference for the Mach–Zehnder interferometer analogy would help.
- [Grammar] There are several typographical and grammatical errors, such as "it's relationship" near the end, which should be corrected in revision.
Circularity Check
The one-observation 'classical analogue' reduces by construction: the second switch position is defined by the electrician's flip rule to equal the parity of connections, so the balanced/constant answer is read off from the rule rather than from a query of f; the N-wire parity extension repeats the same self-definition.
-
self definitional
[This occurs in Alice's explanation of her method in the hotel room scene.]
"The rule was that when an electrician wired the second switch (i.e., the right one) he would always start with the switch in the up position and every time he connected a wire to the lower terminal he would flip the switch. That way all the inspector had to do was to see whether the switch was in the down position, meaning one wire was connected to the down terminal or in the up position, meaning that either two wires were connected to the down terminal or none were."
The rule is stipulated so that the final switch position is exactly the parity (mod 2) of the number of wires attached to the lower terminal. Under the paper's own definitions, a 'balanced' wiring has exactly one lower-terminal connection while a 'constant' wiring has zero or two, so the visible switch position is the answer by construction. Alice's single observation is therefore not an evaluation of the function realized by the wiring; it is a readout of construction metadata that the rule encodes. In the Deutsch-Jozsa black-box model the internal wiring procedure is hidden, and without the assumed convention the switch position carries no information about f. The one-observation 'solution' is equivalent to the input convention, not derived from f.
-
self definitional
[This occurs in the parity-based N-wire generalization near the end of the paper.]
"When he finished he would have connected N wires and N/2 cables and the position of the switch would indicate the parity of the mapping. The situation is completely analogous to that discussed in (7) and represents a classical solution to the parity problem without using a computer. It is also a solution of Deutsch's algorithm where the problem is to determine whether a function is 'constant' or 'balanced' for a large number of inputs."
The N-wire step is the same construction repeated, not a generalization: the flipping procedure defines the switch position to equal the parity of lower-terminal connections, so saying that the switch 'would indicate the parity of the mapping' restates the rule rather than predicting anything. The further claim that this solves Deutsch's algorithm for many inputs is also forced by an incorrect identification, because a balanced function on n inputs has 2^(n-1) ones, which need not be odd, so parity alone cannot separate balanced from constant. The cited parity result [7] does not supply the encoding; the encoding is the paper's own stipulation. Thus the 'classical solution' is a renaming of the stipulated readout, not a derivation.
full rationale
The paper's central claim is Alice's one-observation method for distinguishing balanced from constant wiring. That method is self-definitional: the electrician's standard procedure is defined so that the final position of the second switch equals the parity of lower-terminal connections, and the balanced/constant distinction is then read off from that same parity. No equation is needed to see the reduction; the rule and the readout are the same statement. The manuscript itself flags the black-box objection: 'oracles are not supposed to devolve information as to how they performed transformations.' That acknowledged limitation confirms, rather than repairs, the circularity, because the only response offered is the assertion that Alice's evaluation 'corresponds rather closely' to the quantum mechanical algorithm. The N-wire/parity generalization is the same reduction in larger type, and it also imports a parity result from reference [7] while assuming the very switch-position encoding that makes the readout look informative. There is no self-citation chain here; the issue is internal definitional circularity. Because the central 'prediction' is guaranteed by the stipulated wiring convention, the score is high: 8 on the 0-10 scale, reflecting a result forced by definition rather than by derivation from the Deutsch-Jozsa oracle model.
Assumptions & free parameters
assumptions (4)
- ad hoc to paper The electrician starts with the right switch up and flips it once for each wire connected to the lower terminal.
- domain assumption The oracle's internal wiring state is visible to the observer after the computation.
- standard math Parity of a function f(x)=±1 as defined by Farhi et al. (ref 7) is the relevant notion for the qubit case.
- domain assumption Representing the problem reversibly requires an extra control bit, and this control bit is equivalent to Alice's second switch.
Cite this review
Pith. "Pith review of Deutsch and Jozsa's Algorithm Revisited." pith.science (2026). https://pith.science/paper/HVKOL3RE
@misc{pith2026quant-ph0603231,
author = {Pith},
title = {Pith review of: Deutsch and Jozsa's Algorithm Revisited},
year = {2026},
howpublished = {\url{https://pith.science/paper/HVKOL3RE}},
note = {Machine review of arXiv:quant-ph/0603231}
}
read the original abstract
A classical analogue of Deutsch and Jozsa's algorithm is given and its implications on quantum computing is discussed
Reference graph
Works this paper leans on
-
[1]
Quantum algorithms and the Fourier Transform
R. Jozsa , “Quantum algorithms and the Fourier Transform.” LANL preprint quant- phy 9707033
-
[2]
R. Cleve, A. Ekert, L. Henderson, C. Macchiavello and M. Mosca, “ ON Quantum Algorithms ” LANL preprint quant phy 9903061
-
[3]
Experimental realization of a quantum algorithm
I. Chuang, L. Vandersypen, X. Zhou, D. Leung and S. Lloyd, “Experimental realization of a quantum algorithm”, LANL preprint quant-phy 9801037
-
[4]
A. Jones and M. Mosca, “ Implementation of a Quantum Algorithm to Solve Deutsch’s Problem on a Nuclear Magnetic Rosonance Quantum Computer”, LANL preprint quant-phy 9801027. 5.V. Vedral and M. Plenio, Basics of Quantum Computation”, LANL preprint Quant-phy 9802065
-
[6]
D. Collins, K. Kim and W. Holton, “Deutsch-Jozsa algorithm as a test of quantum computation “, Phys Rev.A58,R1633 (1998)
work page 1998
-
[7]
Limit of the Speed of Quantum Computation in Determining Parity
E. Farhi, J Goldstone, S. Gutmann an M. Sipser, “Limit of the Speed of Quantum Computation in Determining Parity”, Phys. Rev. Lttrs. 81 5542 (1998)
work page 1998
-
[8]
See for example “Communication Networks, Vol II “by E. A. Guillemin Wiley and Sons, New York 1935 p56
work page 1935
Reviewed August 28, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.