REVIEW
Deutsch and Jozsa's Algorithm Revisited
Quantum Physics · Submitted 27 Mar 2006 · 7 references
Pith's 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.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
A three-way switch wiring carries a parity bit that solves Deutsch-Jozsa in one observation.
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.
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.
Original abstract
A classical analogue of Deutsch and Jozsa's algorithm is given and its implications on quantum computing is discussed
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
A classical analogue of Deutsch and Jozsa's algorithm is given and its implications on quantum computing is discussed
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | A classical analogue of Deutsch and Jozsa's algorithm is given and its implications on quantum computing is discussed | contribution 1.00 | 0.85 | 0.35 | asserted 0.99 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.