Optimal lower bounds for quantum automata and random access codes

Consider the finite regular language L/sub n/={w0|w/spl isin/{0,1}*,|w|/spl les/n}. A. Ambainis et al. (1999) showed that while this language is accepted by a deterministic finite automaton of size O(n), any one-way quantum finite automaton (QFA) for it has size 2/sup /spl Omega/(n/logn)/. This was based on the fact that the evolution of a QFA is required to be reversible. When arbitrary intermediate measurements are allowed, this intuition breaks down. Nonetheless, we show a 2/sup /spl Omega/(n)/ lower bound for such QFA for L/sub n/, thus also improving the previous bound. The improved bound is obtained from simple entropy arguments based on A.S. Holevo's (1973) theorem. This method also allows us to obtain an asymptotically optimal (1-H(p))n bound for the dense quantum codes (random access codes) introduced by A. Ambainis et al. We then turn to Holevo's theorem, and show that in typical situations, it may be replaced by a tighter and more transparent in-probability bound.

• Publication year

  1999

• Venue

  40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)

• Publication date

  1999-04-27

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1109/SFFCS.1999.814608arXiv quant-ph/9904093
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Elements of Information Theory

  2005influential reference
• 1-way quantum finite automata: strengths, weaknesses and generalizations

  1998influential reference
• Dense quantum coding and a lower bound for 1-way quantum automata

  1998cited by this paper
• The quantum communication complexity of sampling

  1998cited by this paper
• Quantum circuits with mixed states

  1998cited by this paper
• Quantum theory: Concepts and methods

  1997cited by this paper
• Quantum automata and quantum grammars

  1997cited by this paper
• Quantum Entanglement and the Communication Complexity of the Inner Product Function

  1997cited by this paper
• On the power of quantum finite state automata

  1997influential reference
• Private information retrieval

  1995influential reference
• Quantum Circuit Complexity

  1993influential reference
• General properties of entropy

  1978cited by this paper

• Analytical construction of $(n, n-1)$ quantum random access codes saturating the conjectured bound

  2026cites this paper
• Quantum Sketches, Hashing, and Approximate Nearest Neighbors

  2026cites this paper
• Enhanced quantum state discrimination under general measurements with entanglement and nonorthogonality restrictions

  2026cites this paper
• Communication complexity bounds from information causality

  2026cites this paper
• Magic and communication complexity

  2025cites this paper
• Authenticated sublinear quantum private information retrieval

  2025cites this paper
• Unbounded entanglement-sustaining sequential local quantum state discrimination

  2025cites this paper
• Demonstrating an unconditional separation between quantum and classical information resources

  2025cites this paper
• Theory and Applications of Quantum Hashing

  2025cites this paper
• Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances

  2025cites this paper
• Non-variational quantum random access optimization with alternating operator ansatz

  2025cites this paper
• Getting almost all the bits from a quantum random access code

  2025cites this paper
• Combinatorial Optimization with Few Qubits

  2025cites this paper
• Quantum inputs in the prepare-and-measure scenario and stochastic teleportation

  2025cites this paper
• Information capacity of quantum communication under natural physical assumptions

  2024cites this paper
• Port-Based State Preparation and Applications

  2024cites this paper
• Prepare-and-Measure Scenarios with Photon-Number Constraints.

  2024cites this paper
• Fully Quantum Hash Function

  2024cites this paper
• Recursive Quantum Relaxation for Combinatorial Optimization Problems

  2024cites this paper
• Consumable Data via Quantum Communication

  2024cites this paper
• Binarization of multioutcome measurements in high-dimensional quantum correlation experiments

  2024cites this paper
• Testing and Learning Structured Quantum Hamiltonians

  2024cites this paper
• Self-testing of semisymmetric informationally complete measurements in a qubit prepare-and-measure scenario

  2023cites this paper
• Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions

  2023cites this paper
• Simple and general bounds on quantum random access codes

  2023cites this paper
• Chapter Ten - Qubit representation of a binary tree and its operations in quantum computation

  2023cites this paper
• A probabilistic model of quantum states for classical data security

  2023cites this paper
• Expanding the sharpness parameter area based on sequential $$3{\rightarrow }1$$ 3 → 1 parity-oblivious quantum random access code

  2023cites this paper
• Higher-dimensional symmetric informationally complete measurement via programmable photonic integrated optics

  2023cites this paper
• Almost Qudits in the Prepare-and-Measure Scenario.

  2022cites this paper
• Testing and Learning Quantum Juntas Nearly Optimally

  2022cites this paper
• Quantum Algorithms for Learning a Hidden Graph

  2022cites this paper
• Privacy and correctness trade-offs for information-theoretically secure quantum homomorphic encryption

  2022cites this paper
• Quantum Random Access Codes with Mutually Unbiased Bases in Three-Dimensional Hilbert Space

  2022cites this paper
• Quantum hashing on the high-dimensional states

  2022cites this paper
• Private learning implies quantum stability

  2021cites this paper
• Approximate Solutions of Combinatorial Problems via Quantum Relaxations

  2021cites this paper
• Information-Theoretic Limits of Quantum Learning via Data Compression

  2021cites this paper
• Private learning implies quantum stability

  2021cites this paper
• Probably approximately correct quantum source coding

  2021cites this paper
• Matrix discrepancy from Quantum communication

  2021cites this paper
• The geometry of Bloch space in the context of quantum random access codes

  2021cites this paper
• Instantiation of quantum point obfuscation

  2021cites this paper
• Quantum Random Access Codes for Boolean Functions

  2020cites this paper
• Efficient Discrete Feature Encoding for Variational Quantum Classifier

  2020cites this paper
• Quantum algorithms for learning graphs and beyond

  2020cites this paper
• Efficient Discrete Feature Encoding for Variational Quantum Classifier

  2020cites this paper
• Simulations of Quantum Finite Automata

  2020cites this paper
• Two-way Nanoscale automata

  2020cites this paper
• Security Analysis Based on Quantum Random Oracle Model

  2020cites this paper
• Revisiting Online Quantum State Learning

  2020cites this paper
• Implementing Remote-State Preparation on a Noisy-Intermediate Size Quantum Device

  2020cites this paper
• Chain-rules for channel capacity. (arXiv:quant-ph/0507088v3 UPDATED)

  2020cites this paper
• Quantum hashing and Fourier transform

  2020cites this paper
• Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations

  2020cites this paper
• Experimental demonstration of sequential quantum random access codes

  2020cites this paper
• Quantum Immune One-Time Memories

  2020cites this paper
• The Limitations of Few Qubits: One-way and Two-way Quantum Finite Automata and the Group Word Problem

  2019cites this paper
• Quantum Random Oracle Model with Auxiliary Input

  2019cites this paper
• Self-testing of quantum systems: a review

  2019cites this paper
• Experimentos usando qudits de camino en altas dimensiones para información cuántica = Experiments using high dimensional path qudits for quantum information.

  2019cites this paper
• Quantum finite automata: survey, status and research directions

  2019cites this paper
• The Power of a Single Qubit: Two-way Quantum/Classical Finite Automata and the Word Problem for Linear Groups

  2019cites this paper
• On Quantum Advantage in Information Theoretic Single-Server PIR

  2019influential citation
• Constructions of Quantum Random Access Codes

  2018cites this paper
• The Power of One Clean Qubit in Communication Complexity

  2018cites this paper
• A general bound for the dimension of quantum behaviours in the prepare-and-measure scenario

  2018cites this paper
• On Quantum Chosen-Ciphertext Attacks and Learning with Errors

  2018influential citation
• Characterising the correlations of prepare-and-measure quantum networks

  2018cites this paper
• The Theory of Quantum Information

  2018cites this paper
• Online learning of quantum states

  2018cites this paper
• A quantum homomorphic encryption scheme for polynomial-sized circuits

  2018cites this paper
• Classical and Quantum Computations with Restricted Memory

  2018cites this paper
• Computing quantum hashing in the model of quantum branching programs

  2018cites this paper
• High-Dimensional Quantum Communication Complexity beyond Strategies Based on Bell's Theorem.

  2018cites this paper
• On Quantum Fingerprinting and Quantum Cryptographic Hashing

  2018cites this paper
• Information-theoretically secure quantum homomorphic encryption and its limitations

  2018cites this paper
• Further Limitations on Information-Theoretically Secure Quantum Homomorphic Encryption

  2018influential citation
• Efficient Branching Programs for Quantum Hash Functions Generated by Small-Biased Sets

  2018cites this paper
• Semi-device-independent quantum money

  2018influential citation
• Characterising the behaviour of classical-quantum broadcast networks

  2018cites this paper
• On non-adaptive quantum chosen-ciphertext attacks and Learning with Errors

  2018cites this paper
• Interactive Leakage Chain Rule for Quantum Min-entropy

  2018cites this paper
• Quantum advantage for probabilistic one-time programs

  2017cites this paper
• High-dimensional similarity search and sketching: algorithms and hardness

  2017cites this paper
• Conditional Disclosure of Secrets via Non-linear Reconstruction

  2017cites this paper
• Overlapping Qubits

  2017cites this paper
• One-way Quantum Communication Complexity with Inner Product

  2017cites this paper
• Single Photon Sources and Single Quantum System enabled Communication

  2017cites this paper
• Strong supremacy of quantum systems as communication resource

  2017cites this paper
• Limitations on transversal computation through quantum homomorphic encryption

  2017influential citation
• On statistically-secure quantum homomorphic encryption

  2017cites this paper
• Quantum Communication-Query Tradeoffs

  2017cites this paper
• $n$-fold unbiased bases: an extension of the MUB condition

  2017cites this paper
• New Protocols for Conditional Disclosure of Secrets (and More)

  2017cites this paper
• On the balanced quantum hashing

  2016cites this paper
• Quantum-Proof Extractors: Optimal up to Constant Factors

  2016cites this paper
• 1-Way Multihead Quantum Finite State Automata

  2016cites this paper
• Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication.

  2016cites this paper
• Certifying Equality With Limited Interaction

  2016cites this paper