--- _id: '4550' abstract: - lang: eng text: 'In 2-player non-zero-sum games, Nash equilibria capture the options for rational behavior if each player attempts to maximize her payoff. In contrast to classical game theory, we consider lexicographic objectives: first, each player tries to maximize her own payoff, and then, the player tries to minimize the opponent''s payoff. Such objectives arise naturally in the verification of systems with multiple components. There, instead of proving that each component satisfies its specification no matter how the other components behave, it sometimes suffices to prove that each component satisfies its specification provided that the other components satisfy their specifications. We say that a Nash equilibrium is secure if it is an equilibrium with respect to the lexicographic objectives of both players. We prove that in graph games with Borel winning conditions, which include the games that arise in verification, there may be several Nash equilibria, but there is always a unique maximal payoff profile of a secure equilibrium. We show how this equilibrium can be computed in the case of ω-regular winning conditions, and we characterize the memory requirements of strategies that achieve the equilibrium.' author: - first_name: Krishnendu full_name: Krishnendu Chatterjee id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Thomas A full_name: Thomas Henzinger id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Marcin full_name: Jurdziński, Marcin last_name: Jurdziński citation: ama: Chatterjee K, Henzinger TA, Jurdziński M. Games with secure equilibria. Theoretical Computer Science. 2006;365(1-2):67-82. doi:10.1016/j.tcs.2006.07.032 apa: Chatterjee, K., Henzinger, T. A., & Jurdziński, M. (2006). Games with secure equilibria. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2006.07.032 chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Marcin Jurdziński. “Games with Secure Equilibria.” Theoretical Computer Science. Elsevier, 2006. https://doi.org/10.1016/j.tcs.2006.07.032. ieee: K. Chatterjee, T. A. Henzinger, and M. Jurdziński, “Games with secure equilibria,” Theoretical Computer Science, vol. 365, no. 1–2. Elsevier, pp. 67–82, 2006. ista: Chatterjee K, Henzinger TA, Jurdziński M. 2006. Games with secure equilibria. Theoretical Computer Science. 365(1–2), 67–82. mla: Chatterjee, Krishnendu, et al. “Games with Secure Equilibria.” Theoretical Computer Science, vol. 365, no. 1–2, Elsevier, 2006, pp. 67–82, doi:10.1016/j.tcs.2006.07.032. short: K. Chatterjee, T.A. Henzinger, M. Jurdziński, Theoretical Computer Science 365 (2006) 67–82. date_created: 2018-12-11T12:09:26Z date_published: 2006-08-07T00:00:00Z date_updated: 2021-01-12T07:59:38Z day: '07' doi: 10.1016/j.tcs.2006.07.032 extern: 1 intvolume: ' 365' issue: 1-2 month: '08' page: 67 - 82 publication: Theoretical Computer Science publication_status: published publisher: Elsevier publist_id: '164' quality_controlled: 0 status: public title: Games with secure equilibria type: journal_article volume: 365 year: '2006' ... --- _id: '4549' abstract: - lang: eng text: We present a compositional theory of system verification, where specifications assign real-numbered costs to systems. These costs can express a wide variety of quantitative system properties, such as resource consumption, price, or a measure of how well a system satisfies its specification. The theory supports the composition of systems and specifications, and the hiding of variables. Boolean refinement relations are replaced by real-numbered distances between descriptions of a system at different levels of detail. We show that the classical Boolean rules for compositional reasoning have quantitative counterparts in our setting. While our general theory allows costs to be specified by arbitrary cost functions, we also consider a class of linear cost functions, which give rise to an instance of our framework where all operations are computable in polynomial time. acknowledgement: Supported in part by the NSF grants CCR-0234690, CCR-0208875, and CCR-0225610; by the NSF grant CCR-0132780 and ARP grant SC20051123. author: - first_name: Krishnendu full_name: Krishnendu Chatterjee id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Luca full_name: de Alfaro, Luca last_name: De Alfaro - first_name: Marco full_name: Faella, Marco last_name: Faella - first_name: Thomas A full_name: Thomas Henzinger id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Ritankar full_name: Majumdar, Ritankar S last_name: Majumdar - first_name: Mariëlle full_name: Stoelinga, Mariëlle last_name: Stoelinga citation: ama: 'Chatterjee K, De Alfaro L, Faella M, Henzinger TA, Majumdar R, Stoelinga M. Compositional quantitative reasoning. In: IEEE; 2006:179-188. doi:10.1109/QEST.2006.11' apa: 'Chatterjee, K., De Alfaro, L., Faella, M., Henzinger, T. A., Majumdar, R., & Stoelinga, M. (2006). Compositional quantitative reasoning (pp. 179–188). Presented at the QEST: Quantitative Evaluation of Systems, IEEE. https://doi.org/10.1109/QEST.2006.11' chicago: Chatterjee, Krishnendu, Luca De Alfaro, Marco Faella, Thomas A Henzinger, Ritankar Majumdar, and Mariëlle Stoelinga. “Compositional Quantitative Reasoning,” 179–88. IEEE, 2006. https://doi.org/10.1109/QEST.2006.11. ieee: 'K. Chatterjee, L. De Alfaro, M. Faella, T. A. Henzinger, R. Majumdar, and M. Stoelinga, “Compositional quantitative reasoning,” presented at the QEST: Quantitative Evaluation of Systems, 2006, pp. 179–188.' ista: 'Chatterjee K, De Alfaro L, Faella M, Henzinger TA, Majumdar R, Stoelinga M. 2006. Compositional quantitative reasoning. QEST: Quantitative Evaluation of Systems, 179–188.' mla: Chatterjee, Krishnendu, et al. Compositional Quantitative Reasoning. IEEE, 2006, pp. 179–88, doi:10.1109/QEST.2006.11. short: K. Chatterjee, L. De Alfaro, M. Faella, T.A. Henzinger, R. Majumdar, M. Stoelinga, in:, IEEE, 2006, pp. 179–188. conference: name: 'QEST: Quantitative Evaluation of Systems' date_created: 2018-12-11T12:09:26Z date_published: 2006-09-01T00:00:00Z date_updated: 2021-01-12T07:59:37Z day: '01' doi: 10.1109/QEST.2006.11 extern: 1 month: '09' page: 179 - 188 publication_status: published publisher: IEEE publist_id: '163' quality_controlled: 0 status: public title: Compositional quantitative reasoning type: conference year: '2006' ... --- _id: '4552' abstract: - lang: eng text: 'A concurrent reachability game is a two-player game played on a graph: at each state, the players simultaneously and independently select moves; the two moves determine jointly a probability distribution over the successor states. The objective for player 1 consists in reaching a set of target states; the objective for player 2 is to prevent this, so that the game is zero-sum. Our contributions are two-fold. First, we present a simple proof of the fact that in concurrent reachability games, for all epsilon > 0, memoryless epsilon-optimal strategies exist. A memoryless strategy is independent of the history of plays, and an epsilon-optimal strategy achieves the objective with probability within epsilon of the value of the game. In contrast to previous proofs of this fact, which rely on the limit behavior of discounted games using advanced Puisieux series analysis, our proof is elementary and combinatorial. Second, we present a strategy-improvement (a.k.a. policy-iteration) algorithm for concurrent games with reachability objectives.' author: - first_name: Krishnendu full_name: Krishnendu Chatterjee id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Luca full_name: de Alfaro, Luca last_name: De Alfaro - first_name: Thomas A full_name: Thomas Henzinger id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 citation: ama: 'Chatterjee K, De Alfaro L, Henzinger TA. Strategy improvement for concurrent reachability games. In: IEEE; 2006:291-300. doi:10.1109/QEST.2006.48' apa: 'Chatterjee, K., De Alfaro, L., & Henzinger, T. A. (2006). Strategy improvement for concurrent reachability games (pp. 291–300). Presented at the QEST: Quantitative Evaluation of Systems, IEEE. https://doi.org/10.1109/QEST.2006.48' chicago: Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “Strategy Improvement for Concurrent Reachability Games,” 291–300. IEEE, 2006. https://doi.org/10.1109/QEST.2006.48. ieee: 'K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “Strategy improvement for concurrent reachability games,” presented at the QEST: Quantitative Evaluation of Systems, 2006, pp. 291–300.' ista: 'Chatterjee K, De Alfaro L, Henzinger TA. 2006. Strategy improvement for concurrent reachability games. QEST: Quantitative Evaluation of Systems, 291–300.' mla: Chatterjee, Krishnendu, et al. Strategy Improvement for Concurrent Reachability Games. IEEE, 2006, pp. 291–300, doi:10.1109/QEST.2006.48. short: K. Chatterjee, L. De Alfaro, T.A. Henzinger, in:, IEEE, 2006, pp. 291–300. conference: name: 'QEST: Quantitative Evaluation of Systems' date_created: 2018-12-11T12:09:26Z date_published: 2006-01-01T00:00:00Z date_updated: 2021-01-12T07:59:39Z day: '01' doi: 10.1109/QEST.2006.48 extern: 1 month: '01' page: 291 - 300 publication_status: published publisher: IEEE publist_id: '162' quality_controlled: 0 status: public title: Strategy improvement for concurrent reachability games type: conference year: '2006' ... --- _id: '4574' abstract: - lang: eng text: Many software model checkers are based on predicate abstraction. If the verification goal depends on pointer structures, the approach does not work well, because it is difficult to find adequate predicate abstractions for the heap. In contrast, shape analysis, which uses graph-based heap abstractions, can provide a compact representation of recursive data structures. We integrate shape analysis into the software model checker Blast. Because shape analysis is expensive, we do not apply it globally. Instead, we ensure that, like predicates, shape graphs are computed and stored locally, only where necessary for proving the verification goal. To achieve this, we extend lazy abstraction refinement, which so far has been used only for predicate abstractions, to three-valued logical structures. This approach does not only increase the precision of model checking, but it also increases the efficiency of shape analysis. We implemented the technique by extending Blast with calls to Tvla. alternative_title: - LNCS author: - first_name: Dirk full_name: Beyer, Dirk last_name: Beyer - first_name: Thomas A full_name: Thomas Henzinger id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Grégory full_name: Théoduloz, Grégory last_name: Théoduloz citation: ama: 'Beyer D, Henzinger TA, Théoduloz G. Lazy shape analysis. In: Vol 4144. Springer; 2006:532-546. doi:10.1007/11817963_48' apa: 'Beyer, D., Henzinger, T. A., & Théoduloz, G. (2006). Lazy shape analysis (Vol. 4144, pp. 532–546). Presented at the CAV: Computer Aided Verification, Springer. https://doi.org/10.1007/11817963_48' chicago: Beyer, Dirk, Thomas A Henzinger, and Grégory Théoduloz. “Lazy Shape Analysis,” 4144:532–46. Springer, 2006. https://doi.org/10.1007/11817963_48. ieee: 'D. Beyer, T. A. Henzinger, and G. Théoduloz, “Lazy shape analysis,” presented at the CAV: Computer Aided Verification, 2006, vol. 4144, pp. 532–546.' ista: 'Beyer D, Henzinger TA, Théoduloz G. 2006. Lazy shape analysis. CAV: Computer Aided Verification, LNCS, vol. 4144, 532–546.' mla: Beyer, Dirk, et al. Lazy Shape Analysis. Vol. 4144, Springer, 2006, pp. 532–46, doi:10.1007/11817963_48. short: D. Beyer, T.A. Henzinger, G. Théoduloz, in:, Springer, 2006, pp. 532–546. conference: name: 'CAV: Computer Aided Verification' date_created: 2018-12-11T12:09:33Z date_published: 2006-08-08T00:00:00Z date_updated: 2021-01-12T07:59:49Z day: '08' doi: 10.1007/11817963_48 extern: 1 intvolume: ' 4144' month: '08' page: 532 - 546 publication_status: published publisher: Springer publist_id: '133' quality_controlled: 0 status: public title: Lazy shape analysis type: conference volume: 4144 year: '2006' ... --- _id: '573' abstract: - lang: eng text: 'Mitchison and Jozsa recently suggested that the "chained-Zeno" counterfactual computation protocol recently proposed by Hosten et al. is counterfactual for only one output of the computer. This claim was based on the existing abstract algebraic definition of counterfactual computation, and indeed according to this definition, their argument is correct. However, a more general definition (physically adequate) for counterfactual computation is implicitly assumed by Hosten et. al. Here we explain in detail why the protocol is counterfactual and how the "history tracking" method of the existing description inadequately represents the physics underlying the protocol. Consequently, we propose a modified definition of counterfactual computation. Finally, we comment on one of the most interesting aspects of the error-correcting protocol. ' article_processing_charge: No author: - first_name: Onur full_name: Hosten, Onur id: 4C02D85E-F248-11E8-B48F-1D18A9856A87 last_name: Hosten orcid: 0000-0002-2031-204X - first_name: Matthew full_name: Rakher, Matthew last_name: Rakher - first_name: Julio full_name: Barreiro, Julio last_name: Barreiro - first_name: Nicholas full_name: Peters, Nicholas last_name: Peters - first_name: Paul full_name: Kwiat, Paul last_name: Kwiat citation: ama: Hosten O, Rakher M, Barreiro J, Peters N, Kwiat P. Counterfactual computation revisited. 2006. apa: Hosten, O., Rakher, M., Barreiro, J., Peters, N., & Kwiat, P. (2006). Counterfactual computation revisited. ArXiv. chicago: Hosten, Onur, Matthew Rakher, Julio Barreiro, Nicholas Peters, and Paul Kwiat. “Counterfactual Computation Revisited.” ArXiv, 2006. ieee: O. Hosten, M. Rakher, J. Barreiro, N. Peters, and P. Kwiat, “Counterfactual computation revisited.” ArXiv, 2006. ista: Hosten O, Rakher M, Barreiro J, Peters N, Kwiat P. 2006. Counterfactual computation revisited. mla: Hosten, Onur, et al. Counterfactual Computation Revisited. ArXiv, 2006. short: O. Hosten, M. Rakher, J. Barreiro, N. Peters, P. Kwiat, (2006). date_created: 2018-12-11T11:47:16Z date_published: 2006-08-06T00:00:00Z date_updated: 2020-05-12T08:23:52Z day: '06' extern: '1' external_id: arxiv: - '0607101' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/quant-ph/0607101 month: '08' oa: 1 oa_version: Preprint page: '12' publication_status: published publisher: ArXiv publist_id: '7241' status: public title: Counterfactual computation revisited type: preprint user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2006' ... --- _id: '574' abstract: - lang: eng text: 'Vaidman, in a recent article adopts the method of ''quantum weak measurements in pre- and postselected ensembles'' to ascertain whether or not the chained-Zeno counterfactual computation scheme proposed by Hosten et al. is counterfactual; which has been the topic of a debate on the definition of counterfactuality. We disagree with his conclusion, which brings up some interesting aspects of quantum weak measurements and some concerns about the way they are interpreted. ' article_processing_charge: No author: - first_name: Onur full_name: Hosten, Onur id: 4C02D85E-F248-11E8-B48F-1D18A9856A87 last_name: Hosten orcid: 0000-0002-2031-204X - first_name: Paul full_name: Kwiat, Paul last_name: Kwiat citation: ama: Hosten O, Kwiat P. Weak measurements and counterfactual computation. 2006. apa: Hosten, O., & Kwiat, P. (2006). Weak measurements and counterfactual computation. ArXiv. chicago: Hosten, Onur, and Paul Kwiat. “Weak Measurements and Counterfactual Computation.” ArXiv, 2006. ieee: O. Hosten and P. Kwiat, “Weak measurements and counterfactual computation.” ArXiv, 2006. ista: Hosten O, Kwiat P. 2006. Weak measurements and counterfactual computation. mla: Hosten, Onur, and Paul Kwiat. Weak Measurements and Counterfactual Computation. ArXiv, 2006. short: O. Hosten, P. Kwiat, (2006). date_created: 2018-12-11T11:47:16Z date_published: 2006-12-19T00:00:00Z date_updated: 2020-05-12T08:18:01Z day: '19' extern: '1' external_id: arxiv: - '0612159' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/quant-ph/0612159 month: '12' oa: 1 oa_version: Preprint page: '2' publication_status: published publisher: ArXiv publist_id: '7240' status: public title: Weak measurements and counterfactual computation type: preprint user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2006' ... --- _id: '578' abstract: - lang: eng text: A source of single photons allows secure quantum key distribution, in addition, to being a critical resource for linear optics quantum computing. We describe our progress on deterministically creating single photons from spontaneous parametric downconversion, an extension of the Pittman, Jacobs and Franson scheme [Phys. Rev A, v66, 042303 (2002)]. Their idea was to conditionally prepare single photons by measuring one member of a spontaneously emitted photon pair and storing the remaining conditionally prepared photon until a predetermined time, when it would be "deterministically" released from storage. Our approach attempts to improve upon this by recycling the pump pulse in order to decrease the possibility of multiple-pair generation, while maintaining a high probability of producing a single pair. Many of the challenges we discuss are central to other quantum information technologies, including the need for low-loss optical storage, switching and detection, and fast feed-forward control. alternative_title: - Proc. SPIE author: - first_name: Nicholas full_name: Peters, Nicholas A last_name: Peters - first_name: Keith full_name: Arnold, Keith J last_name: Arnold - first_name: Aaron full_name: VanDevender, Aaron P last_name: Vandevender - first_name: Evan full_name: Jeffrey, Evan R last_name: Jeffrey - first_name: Radhika full_name: Rangarajan, Radhika last_name: Rangarajan - first_name: Onur full_name: Onur Hosten id: 4C02D85E-F248-11E8-B48F-1D18A9856A87 last_name: Hosten orcid: 0000-0002-2031-204X - first_name: Julio full_name: Barreiro, Julio T last_name: Barreiro - first_name: Joseph full_name: Altepeter, Joseph B last_name: Altepeter - first_name: Paul full_name: Kwiat, Paul G last_name: Kwiat citation: ama: 'Peters N, Arnold K, Vandevender A, et al. Towards a quasi-deterministic single-photon source. In: Vol 6305. SPIE; 2006. doi:10.1117/12.684702' apa: Peters, N., Arnold, K., Vandevender, A., Jeffrey, E., Rangarajan, R., Hosten, O., … Kwiat, P. (2006). Towards a quasi-deterministic single-photon source (Vol. 6305). Presented at the Quantum Communications and Quantum Imaging, SPIE. https://doi.org/10.1117/12.684702 chicago: Peters, Nicholas, Keith Arnold, Aaron Vandevender, Evan Jeffrey, Radhika Rangarajan, Onur Hosten, Julio Barreiro, Joseph Altepeter, and Paul Kwiat. “Towards a Quasi-Deterministic Single-Photon Source,” Vol. 6305. SPIE, 2006. https://doi.org/10.1117/12.684702. ieee: N. Peters et al., “Towards a quasi-deterministic single-photon source,” presented at the Quantum Communications and Quantum Imaging, 2006, vol. 6305. ista: Peters N, Arnold K, Vandevender A, Jeffrey E, Rangarajan R, Hosten O, Barreiro J, Altepeter J, Kwiat P. 2006. Towards a quasi-deterministic single-photon source. Quantum Communications and Quantum Imaging, Proc. SPIE, vol. 6305. mla: Peters, Nicholas, et al. Towards a Quasi-Deterministic Single-Photon Source. Vol. 6305, SPIE, 2006, doi:10.1117/12.684702. short: N. Peters, K. Arnold, A. Vandevender, E. Jeffrey, R. Rangarajan, O. Hosten, J. Barreiro, J. Altepeter, P. Kwiat, in:, SPIE, 2006. conference: name: Quantum Communications and Quantum Imaging date_created: 2018-12-11T11:47:17Z date_published: 2006-01-01T00:00:00Z date_updated: 2020-07-14T12:47:11Z day: '01' doi: 10.1117/12.684702 extern: 1 intvolume: ' 6305' month: '01' publication_status: published publisher: SPIE publist_id: '7234' quality_controlled: 0 status: public title: Towards a quasi-deterministic single-photon source type: conference volume: 6305 year: '2006' ... --- _id: '577' abstract: - lang: eng text: Visible light photon counters (VLPCs) and solid-state photomultipliers (SSPMs) are high-efficiency single-photon detectors which have multi-photon counting capability. While both the VLPCs and the SSPMs have inferred internal quantum efficiencies above 93%, the actual measured values for both the detectors were in fact limited to less than 88%, attributed to in-coupling losses. We are currently improving this overall detection efficiency via a) custom anti-reflection coating the detectors and the in-coupling fibers, b) implementing a novel cryogenic design to reduce transmission losses and, c) using low-noise electronics to obtain a better signal-to-noise ratio. alternative_title: - Proceedings of SPIE author: - first_name: Radhika full_name: Rangarajan, Radhika last_name: Rangarajan - first_name: Joseph full_name: Altepeter, Joseph B last_name: Altepeter - first_name: Evan full_name: Jeffrey, Evan R last_name: Jeffrey - first_name: Micah full_name: Stoutimore, Micah J last_name: Stoutimore - first_name: Nicholas full_name: Peters, Nicholas A last_name: Peters - first_name: Onur full_name: Onur Hosten id: 4C02D85E-F248-11E8-B48F-1D18A9856A87 last_name: Hosten orcid: 0000-0002-2031-204X - first_name: Paul full_name: Kwiat, Paul G last_name: Kwiat citation: ama: 'Rangarajan R, Altepeter J, Jeffrey E, et al. High-efficiency single-photon detectors. In: Vol 6372. SPIE; 2006. doi:10.1117/12.686117' apa: Rangarajan, R., Altepeter, J., Jeffrey, E., Stoutimore, M., Peters, N., Hosten, O., & Kwiat, P. (2006). High-efficiency single-photon detectors (Vol. 6372). Presented at the Unknown (978-081946470-5), SPIE. https://doi.org/10.1117/12.686117 chicago: Rangarajan, Radhika, Joseph Altepeter, Evan Jeffrey, Micah Stoutimore, Nicholas Peters, Onur Hosten, and Paul Kwiat. “High-Efficiency Single-Photon Detectors,” Vol. 6372. SPIE, 2006. https://doi.org/10.1117/12.686117. ieee: R. Rangarajan et al., “High-efficiency single-photon detectors,” presented at the Unknown (978-081946470-5), 2006, vol. 6372. ista: Rangarajan R, Altepeter J, Jeffrey E, Stoutimore M, Peters N, Hosten O, Kwiat P. 2006. High-efficiency single-photon detectors. Unknown (978-081946470-5), Proceedings of SPIE, vol. 6372. mla: Rangarajan, Radhika, et al. High-Efficiency Single-Photon Detectors. Vol. 6372, SPIE, 2006, doi:10.1117/12.686117. short: R. Rangarajan, J. Altepeter, E. Jeffrey, M. Stoutimore, N. Peters, O. Hosten, P. Kwiat, in:, SPIE, 2006. conference: name: Unknown (978-081946470-5) date_created: 2018-12-11T11:47:17Z date_published: 2006-01-01T00:00:00Z date_updated: 2020-07-14T12:47:11Z day: '01' doi: 10.1117/12.686117 extern: 1 intvolume: ' 6372' month: '01' publication_status: published publisher: SPIE publist_id: '7233' quality_controlled: 0 status: public title: High-efficiency single-photon detectors type: conference volume: 6372 year: '2006' ... --- _id: '579' abstract: - lang: eng text: 'The logic underlying the coherent nature of quantum information processing often deviates from intuitive reasoning, leading to surprising effects. Counterfactual computation constitutes a striking example: the potential outcome of a quantum computation can be inferred, even if the computer is not run 1. Relying on similar arguments to interaction-free measurements 2 (or quantum interrogation3), counterfactual computation is accomplished by putting the computer in a superposition of ''running'' and ''not running'' states, and then interfering the two histories. Conditional on the as-yet-unknown outcome of the computation, it is sometimes possible to counterfactually infer information about the solution. Here we demonstrate counterfactual computation, implementing Grover''s search algorithm with an all-optical approach4. It was believed that the overall probability of such counterfactual inference is intrinsically limited1,5, so that it could not perform better on average than random guesses. However, using a novel ''chained'' version of the quantum Zeno effect6, we show how to boost the counterfactual inference probability to unity, thereby beating the random guessing limit. Our methods are general and apply to any physical system, as illustrated by a discussion of trapped-ion systems. Finally, we briefly show that, in certain circumstances, counterfactual computation can eliminate errors induced by decoherence. ' author: - first_name: Onur full_name: Onur Hosten id: 4C02D85E-F248-11E8-B48F-1D18A9856A87 last_name: Hosten orcid: 0000-0002-2031-204X - first_name: Matthew full_name: Rakher, Matthew T last_name: Rakher - first_name: Julio full_name: Barreiro, Julio T last_name: Barreiro - first_name: Nicholas full_name: Peters, Nicholas A last_name: Peters - first_name: Paul full_name: Kwiat, Paul G last_name: Kwiat citation: ama: Hosten O, Rakher M, Barreiro J, Peters N, Kwiat P. Counterfactual quantum computation through quantum interrogation. Nature. 2006;439(7079):949-952. doi:10.1038/nature04523 apa: Hosten, O., Rakher, M., Barreiro, J., Peters, N., & Kwiat, P. (2006). Counterfactual quantum computation through quantum interrogation. Nature. Nature Publishing Group. https://doi.org/10.1038/nature04523 chicago: Hosten, Onur, Matthew Rakher, Julio Barreiro, Nicholas Peters, and Paul Kwiat. “Counterfactual Quantum Computation through Quantum Interrogation.” Nature. Nature Publishing Group, 2006. https://doi.org/10.1038/nature04523. ieee: O. Hosten, M. Rakher, J. Barreiro, N. Peters, and P. Kwiat, “Counterfactual quantum computation through quantum interrogation,” Nature, vol. 439, no. 7079. Nature Publishing Group, pp. 949–952, 2006. ista: Hosten O, Rakher M, Barreiro J, Peters N, Kwiat P. 2006. Counterfactual quantum computation through quantum interrogation. Nature. 439(7079), 949–952. mla: Hosten, Onur, et al. “Counterfactual Quantum Computation through Quantum Interrogation.” Nature, vol. 439, no. 7079, Nature Publishing Group, 2006, pp. 949–52, doi:10.1038/nature04523. short: O. Hosten, M. Rakher, J. Barreiro, N. Peters, P. Kwiat, Nature 439 (2006) 949–952. date_created: 2018-12-11T11:47:18Z date_published: 2006-02-23T00:00:00Z date_updated: 2021-01-12T08:03:29Z day: '23' doi: 10.1038/nature04523 extern: 1 intvolume: ' 439' issue: '7079' month: '02' page: 949 - 952 publication: Nature publication_status: published publisher: Nature Publishing Group publist_id: '7235' quality_controlled: 0 status: public title: Counterfactual quantum computation through quantum interrogation type: journal_article volume: 439 year: '2006' ... --- _id: '583' abstract: - lang: eng text: Visible light photon counters (VLPCs) and solid-state photomultipliers (SSPMs) facilitate efficient single-photon detection. We are attempting to improve their efficiency, previously limited to < 88% by coupling losses, via anti-reflection coatings, better electronics and cryogenics. author: - first_name: Radhika full_name: Rangarajan, Radhika last_name: Rangarajan - first_name: Nicholas full_name: Peters, Nicholas A last_name: Peters - first_name: Onur full_name: Onur Hosten id: 4C02D85E-F248-11E8-B48F-1D18A9856A87 last_name: Hosten orcid: 0000-0002-2031-204X - first_name: Joseph full_name: Altepeter, Joseph B last_name: Altepeter - first_name: Evan full_name: Jeffrey, Evan R last_name: Jeffrey - first_name: Paul full_name: Kwiat, Paul G last_name: Kwiat citation: ama: 'Rangarajan R, Peters N, Hosten O, Altepeter J, Jeffrey E, Kwiat P. Improved single-photon detection. In: IEEE; 2006. doi:10.1109/CLEO.2006.4628641' apa: 'Rangarajan, R., Peters, N., Hosten, O., Altepeter, J., Jeffrey, E., & Kwiat, P. (2006). Improved single-photon detection. Presented at the CLEO/QELS: Conference on Lasers and Electro-Optics / Quantum Electronics and Laser Science Conference, IEEE. https://doi.org/10.1109/CLEO.2006.4628641' chicago: Rangarajan, Radhika, Nicholas Peters, Onur Hosten, Joseph Altepeter, Evan Jeffrey, and Paul Kwiat. “Improved Single-Photon Detection.” IEEE, 2006. https://doi.org/10.1109/CLEO.2006.4628641. ieee: 'R. Rangarajan, N. Peters, O. Hosten, J. Altepeter, E. Jeffrey, and P. Kwiat, “Improved single-photon detection,” presented at the CLEO/QELS: Conference on Lasers and Electro-Optics / Quantum Electronics and Laser Science Conference, 2006.' ista: 'Rangarajan R, Peters N, Hosten O, Altepeter J, Jeffrey E, Kwiat P. 2006. Improved single-photon detection. CLEO/QELS: Conference on Lasers and Electro-Optics / Quantum Electronics and Laser Science Conference.' mla: Rangarajan, Radhika, et al. Improved Single-Photon Detection. IEEE, 2006, doi:10.1109/CLEO.2006.4628641. short: R. Rangarajan, N. Peters, O. Hosten, J. Altepeter, E. Jeffrey, P. Kwiat, in:, IEEE, 2006. conference: name: 'CLEO/QELS: Conference on Lasers and Electro-Optics / Quantum Electronics and Laser Science Conference' date_created: 2018-12-11T11:47:19Z date_published: 2006-01-01T00:00:00Z date_updated: 2021-01-12T08:03:43Z day: '01' doi: 10.1109/CLEO.2006.4628641 extern: 1 month: '01' publication_status: published publisher: IEEE publist_id: '7232' quality_controlled: 0 status: public title: Improved single-photon detection type: conference year: '2006' ...